חידת אלגוריתמית/מתמטית

[דניאל ק]

היא די מוכרת, אז מי שכבר יודע מה הפתרון, שלא יגיב…
הפעם הראשונה שראיתי את החידה הייתה באיזה חידון של חיל הקשר
(בתערוכת טלקום), אז אני מניח שאני חייב להם את הקרדיט, למרות שזאת שאלה שדי נפוצה באינטרנט..

א. ישנו בניין בן 100 קומות, בעזרת 2 בקבוקי זכוכית, צריך למצוא את הקומה המקסימלית ממנה ניתן לזרוק בקבוק, ושהוא לא ישבר.
צריך למצוא אלגוריתם אופטימלי, כאשר אלגוריתם אופטימלי זה אלגוריתם שבו מספר הזריקות במקרה הכי גרוע, הוא הקטן ביותר.
(חשוב לזכור, בשניה שנשבר בקבוק, אי אפשר להשתמש בו שוב פעם).

ב. תן פתרון כללי עבור בניין בן N קומות(זאת תוספת שלי).

[CodeGuru]

כותרת: ואחרי שתפתרו – הכללה של השאלה
ומה אם מותר לזרוק שלושה כדורים?
או K-כדורים באופן כללי?

[דניאל ק]

כותרת: אני לא בטוח שאפשר באופן כללי…

[דניאל ק]

כותרת: נמחק לי התוכן…
אני לא בטוח שאפשר באופן כללי…
החל מ K מסוים(K = LOG2 N ומעלה), השיטה הכי יעילה זה פשוט חיפוש בינארי, ללא קשר לK.
טוב, אז אולי כן אפשר באופן כללי, לכל המספרים שקטנים מ
LOG2 N.

[דניאל ק]

כותרת: נמחק לי התוכן…
אני לא בטוח שאפשר באופן כללי…
החל מ K מסוים(K = LOG2 N ומעלה), השיטה הכי יעילה זה פשוט חיפוש בינארי, ללא קשר לK.
טוב, אז אולי כן אפשר באופן כללי, לכל המספרים שקטנים מ
LOG2 N.

[אורן בקר]

כותרת: פתרון
אוקיי, עבור שני כדורים אני מציע את הפתרון הבא:

יהי n מספר הקומות בבניין:

אם n=1, האלגוריתם מסתיים, מצאנו את הקומה ה"קריטית".
אחרת:
חשב את
p=(1+sqrt(8*h-15))/2
(עגל כלפי מטה)
זרוק בקבוק מקומה p.
אם הוא נשבר, הבעיה יורדת למציאת הקומה הקריטית עבור בניין בעל pקומות עם בקבוק אחד (אין ברירה אלא לבצע סריקה ליניארית).
אם הוא לא נשבר, הבעיה יורדת למציאת הקומה הקריטית עבור בניין בעל n-p קומות עם שני בקבוקים (ע"י שימוש רקורסיבי באלגוריתם זה).

האלגוריתם הוא אופטימלי ומספר הזריקות המירבי שעלול להידרש הוא p (עבור מספר הקומות המקורי).

אציין שלפתרון זה קשר הדוק לפתרון הפשוט לחידת הדחיסה שפרסמתי קודם (זה שמשתמש בשורש)

עבור יותר משני בקבוקים הנוסחה למציאת p מסתבכת, אם היא בכלל קיימת:
עבור שלושה בקבוקים למשל, מציאת p דורשת את פתרון המשוואה:
n^3 – 3n^2 +5n = 6h

[אמרי גולדברג]

כותרת: גרסה יותר מעניינת
כאשר לבניין יש אינסוף קומות (ממוספרות 0 1 2 … ),
כאשר אלגוריתם אופטימלי הוא אלגוריתם בו סיבוכיות מספר הזריקות במקרה הגרוע ביותר היא מינימלית.

[דניאל ק]

כותרת: פתרון כללי לK זריקות
אז ככה. העקרון הוא די בסיסי – הקפיצות כל הזמן משתנות, מתוך נקודת הנחה שמספר הזריקות במקרה הכי גרוע צריך להיות קבוע.
הדוגמה של 2 כדורים – על כל פעם שזורקים את הכדור הראשון, מספר הזריקות שאפשר לעשות עם הכדור השני במקרה שהוא נשבר הולך וקטן.
בכמה הוא קטן? בכמות הקומות אליו ניתן להגיע עם K כדורים בT זריקות.

את כל זה אפשר לנסח עם נוסחה רקורסיבית יחסית פשוטה:

N = G(K,t( – הקומה המירבית אליה ניתן להגיע, כפונקציה של מספר הזריקות ומספר הכדורים.
כאשר G מוגדר ככה:
G(K,t) = G(K-1,T-1) + 1 + G(K, T-1)
(הפורום מקשה בכתיבת נוסחאות ).
פחות או יותר, מה שזה אומר זה ככה: הקומה המירבית שאליה ניתן להגיע עם K כדורים ב T זריקות, הוא כמו מספר הקומות אליו ניתן להגיע עם T-1 זריקות, בתוספת מספר הקומות שאליהם אפשר יהיה להגיע אם הכדור נשבר, ונותרו לנו רק K-1 כדורים.

הדרך מהנוסחה הזאת ועד איזה קומות בדיוק צריך לזרוק מהם קצרה מאוד, אפילו כתבתי תכנית קטנה שתעשה את זה, ביום ראשון אני אפרסם אותה. (או

ולגבי הקטע שמספר הזריקות מגיע ל LOG N, מסתבר שכאשר מגיעים לLOG N, האלגוריתמים(חיפוש כזה וחיפוש בינארי) הם יעילים באותה מידה, אז שיטת הפתרון עדיין נשארת בסדר.

אמרי – לא שמעת על מגדל בבל?? זה לא קצת התגרות באלוהים לבנות בניין בן אינסוף קומות??

[דניאל ק]

כותרת: "אציין שלחידה יש קשר ברור לחידת הדחיסה שפרסמתי"
מדהים, אה? 2 שיכורים זורקים בקבוקי בירה מאיזה בניין, ובסופו של דבר מגיעים לאלגוריתם דחיסה.

[דניאל ק]

כותרת: קטע הקוד
לא אופטימלי במיוחד, אבל בכל זאת עובד.
int MaxFloor(int throws, int balls);
int main(int argc, char* argv[])
{
int Height, balls, throws;
printf("Enter height N: ");
scanf("%d", &Height);
printf("Enter number of balls K: ");
scanf("%d", &balls);
for(throws = 0; true; throws++)
{
if(MaxFloor(throws, balls) >= Height)
break;
}
printf("Worst case number of throws: %dn", throws);
int Max = MaxFloor(throws, balls);
for(int i = 0; i < throws; i++)
{
int Floor = Max – MaxFloor(i, balls);
if(Floor < Height)
printf("%d -> %dn", throws – i, Floor);
}
return 0;
}

int MaxFloor(int throws, int balls)
{
if(!throws || !balls)
return 0;
return MaxFloor(throws – 1, balls – 1) + 1 + MaxFloor(throws – 1, balls);
}

[אמרי גולדברג]

כותרת: מה, אף פעם לא יצא לך לבקר במלון של הילברט?

[אמרי גולדברג]

כותרת: פתרון: שני כשלונות לכל היותר, בניין אינסופי.
ראשית, אני חייב לציין שזו קצת רמאות, נתנו לי את השאלה הזו בקורס מבני נתונים.
אך מי שמעוניין לקרוא את אחד הפתרונות:

נתחיל בקומה הראשונה. בכל פעם נגדיל את המרחק מהניסוי הקודם באחד.
אם נשבר כדור, נעבור על כל הקומות מהניסוי הקודם אחת אחת, עד שנמצא.
לכן, אם N היא הקומה הקריטית, ומספר הניסויים הוא n, נקבל משהו בסגנון
n*(n+1)/2+ n=N
פלוס מינוס 1 לאחד האגפים. (לא ממש משנה). מכיוון שזו משוואה ריבועית, נקבל שסיבוכיות מספר הניסויים היא ב – O(sqrt(n))+0 (הוספתי את +0 כדי שזה יראה טוב).

הערה משעשעת – השאלה ניתנה לי בצורה קצת אחרת, להלן הסיפור:
מסופר על החתול המפורסם של שרודינגר (שהיינלין טען שמזמן כבר ברח מהקופסא), ששמים בתוך הקופסא. אך הפעם, זאת קופסא רגילה, והחתול נחנק. הנחה: כל החתולים נחנקים באותו זמן. אנו רוצים למצוא את הרגע הקריטי בדיוק של דקות. טוב אמרו אנשי מדעי המחשב, נששתמש בשיטת ההכפלה, ובעזרת O(logn)+0 חתולים (כאשל n היא הדקה הקריטית) נמצא את הדקה.

עד כאן טוב ויפה, אך לפתע ועדת הלסינקי אמרה, רק רגע, אמנם למצוא את הדקה הקריטית זו אכן מטרה נעלה, אבל O(logn)+0 חתולים זה יותר מדי. תשתמשו לכל היותר בשני חתולים. הפתרון למעלה.

זאת הכתובת של האתר של המרצה שהעביר את הקורס במבני נתונים: (גיא קינדלר)
http://www.math.tau.ac.il/~puzne/

[מאת]

תגובות