רוטר - חידה חמודה.

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"חידה חמודה."

גירסת הדפסה

קבוצות דיון פיתוח, תיכנות ובניית אתרים נושא #15431	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 15431

Deuce
חבר מתאריך 1.9.08
6225 הודעות

07:59 08.08.09

חידה חמודה.

ערכתי לאחרונה בתאריך 08.08.09 בשעה 18:42 בברכה, Deuce

נגדיר פרמוטציה מסדר (n,m) באופן הבא:
• מסדרים את המספרים 1,2,3,...,n במעגל בסדר עוקב, ומצביעים על המספר 1.
• מבצעים m צעדים לאורך המספרים שנותרו על המעגל.
• מדפיסים את המספר אליו הגענו, ומוחקים אותו מהמעגל. אם נותרו מספרים חוזרים לב', ולא עוצרים. מספר שנמחק, אינו נספר במניין הצעדים בשלב ב'.
לדוגמא: הפרמוטציה מסדר (7,3) היא 4,7,3,1,6,2,5.
תארו אלגוריתם יעיל המקבל מספר n, ומחזיר את הפרמוטציה מסדר (n,n/2).

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
להלהלה.	Deuce	10.08.09 13:56	1
כמה זה יעיל? ומה קורה עם אי-זוגיים? עיגול מטה או מעלה?	ldan192	10.08.09 19:07	2
עיגול מטה אם כי לא כזה משנה לי.	Deuce	10.08.09 23:50	3
זה לא כזה קשה :\	Deuce	15.08.09 06:18	4
יאפ(:	akoka	16.08.09 06:07	5
רמז: מבנה נתונים מאוזן יכול לייעל את האלגוריתם.	Deuce	22.08.09 18:42	6
- פתרון -	Deuce	27.08.09 20:19	7

Deuce
חבר מתאריך 1.9.08
6225 הודעות

13:56 10.08.09

1. להלהלה.
בתגובה להודעה מספר 0

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95119 הודעות

19:07 10.08.09

2. כמה זה יעיל? ומה קורה עם אי-זוגיים? עיגול מטה או מעלה?
בתגובה להודעה מספר 0

בברכה,
עידן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות

23:50 10.08.09

3. עיגול מטה אם כי לא כזה משנה לי.
בתגובה להודעה מספר 2

בחרתי ב-n/2 כדי שפתרון לא יעיל יעלה סדר גודל של n^2.
יעיל זה nlog n, אם אתה יכול יותר טוב אז בכיף.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות

06:18 15.08.09

4. זה לא כזה קשה :\
בתגובה להודעה מספר 0

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

akoka

06:07 16.08.09

5. יאפ(:
בתגובה להודעה מספר 4

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות

18:42 22.08.09

6. רמז: מבנה נתונים מאוזן יכול לייעל את האלגוריתם.
בתגובה להודעה מספר 0

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות

20:19 27.08.09

7. - פתרון -
בתגובה להודעה מספר 0

זה באמת לא כזה קשה.
נתחזק את הנתונים בעץ מאוזן, למשל עץ אדום שחור או AVL, כאשר כל הערכים האמיתיים 1,...,n יהיו בעלים. כמו כן לכל צומת יהיה שדה האומר כמה עלים יש בעץ ששורשו הוא אותו צומת. בניית העץ כאמור עולה לנו O(nlog n).
כעת ניגש לצומת 1, נמחוק אותו.
בהנתן צומת שמספרו i ו-k צמתים שנותרו בעץ, נחפש צומת שמספרו i+n/2 mod k. נוכל למצוא אותו ב-log n באמצעות המספור שעשינו לכל צומת, נמחק אותו ונמשיך כך רקורסיבית.
בנייה - nlog n
מציאת איבר הבא - log n
מחיקה - log n
סה"כ:

3nlog n = O(nlog n).

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד