מסכים הניסוח שלי דורש שיפור (אני כבר נכנסתי למימוש עצמו)
amirbd,
הפיתרון שלך עדיין נשמע לי כמו N logN
אלא אם כן לא הבנתי משהו
אנא הסבר שוב
שירשור החידות הגדול
זה אכן לינארי (כנו שמשה כתב), עם זאת, לדעתי מכיון ש-osherov נתן את פתרון בית הספר שאליו התכוון המשורר (ולא פתר בעיה יותר מורכבת כמוני), השרביט צריך לעבור אליו - מסכימים?
בנוסף יהיה נחמד אם נחזור לחוד חידות שלא מצריכות דוקטורט במדעי המחשב (או אפילו לא מצריכות תואר ראשון, או קורס ערב בסיוון).
בנוסף יהיה נחמד אם נחזור לחוד חידות שלא מצריכות דוקטורט במדעי המחשב (או אפילו לא מצריכות תואר ראשון, או קורס ערב בסיוון).
להלן שאלה לא פשוטה:
מטע בננות ממוקם סמוך למדבר.
לבעל מטע הבננות יש 3,000 בננות שאותם הוא רוצה להעביר לשוק ע"י סחיבה על גמל.
השוק נמצא במרחק 1,000 ק"מ ממטע הבננות.
לבעל המטע יש רק גמל אחד, שמסוגל לסחוב 1,000 בננות בכל רגע נתון.
כמו כן כדי לשרוד הגמל הזה חייב לאכול בננה אחת כל קילומטר הליכה (גמל מפונק)
שאלה:
מה מספר הבננות המרבי שניתן להעביר לשוק ? נא לפרט את תשובתכם
מטע בננות ממוקם סמוך למדבר.
לבעל מטע הבננות יש 3,000 בננות שאותם הוא רוצה להעביר לשוק ע"י סחיבה על גמל.
השוק נמצא במרחק 1,000 ק"מ ממטע הבננות.
לבעל המטע יש רק גמל אחד, שמסוגל לסחוב 1,000 בננות בכל רגע נתון.
כמו כן כדי לשרוד הגמל הזה חייב לאכול בננה אחת כל קילומטר הליכה (גמל מפונק)
שאלה:
מה מספר הבננות המרבי שניתן להעביר לשוק ? נא לפרט את תשובתכם
שאלה, הגמל אוכל את הבננה לפני היציאה לדרך או תוך כדי?
אם מרחק השוק היה ק"מ אחד בלבד, אז זה מבדיל בין יכולת העברת 1000 (בנגלה אחת) לבין יכולת העברת 999 בלבד.
באותו עיניין, האם בחצי ק"מ הוא אוכל חצי בננה? כלומר , הבבנות זה דלק רציף, או בדיד ?
אם מרחק השוק היה ק"מ אחד בלבד, אז זה מבדיל בין יכולת העברת 1000 (בנגלה אחת) לבין יכולת העברת 999 בלבד.
באותו עיניין, האם בחצי ק"מ הוא אוכל חצי בננה? כלומר , הבבנות זה דלק רציף, או בדיד ?
משה
שאלה שמחזירה אותי שנים אחורה...
הנה הרעיון שלי, מודה שלא חשבתי על זה יותר מדי, וזה די בשליפה, אז אם אני מדבר שטויות - נא לייחס את זה לטיסה.
שלב ראשון - נעבור של שתי הרשימות ונספור כמה איברים יש בכל רשימה. - סיבוכיות לינארית.
שלב שני - נניח ש-P1 מצביע על הרשימה הארוכה ו-P2 על הקצרה. נקדם את X P1 צעדים (כאשר X הוא הפרש האורכים בין הרשימות). סיבוכיות לינארית.
שלב שלישי - נקדם כל שלב את P1 ו-P2 צעד אחד קדימה ונשווה ביניהם.
סה"כ - שימוש בזיכרון קבוע שאינו תלוי באורך הרשימות, וסיבוכיות לינארית.
הסבר לדרך (או איך חשבתי על זה):
נסתכל על שני מקרי קיצון:
1. רשימה 1 מוכלת בתוך רשימה 2 כולה (כלומר, ה"חיבור" הוא כבר באיבר הראשון של רשימה 1).
2. הרשימות מתחברות רק באיבר האחרון.
מתוך מבט על שני המקרים האלה, ברור לנו שדבר ראשון צריך "לזרוק" את ה"איברים העודפים" - כלומר האיברים שברור לנו שבהם לא יכולה להתרחש התחברות.
ברגע שזרקנו אותם - אנחנו יכולים להתקדם צעד צעד עד שמגיעים לשוויון.
הנה הרעיון שלי, מודה שלא חשבתי על זה יותר מדי, וזה די בשליפה, אז אם אני מדבר שטויות - נא לייחס את זה לטיסה.
שלב ראשון - נעבור של שתי הרשימות ונספור כמה איברים יש בכל רשימה. - סיבוכיות לינארית.
שלב שני - נניח ש-P1 מצביע על הרשימה הארוכה ו-P2 על הקצרה. נקדם את X P1 צעדים (כאשר X הוא הפרש האורכים בין הרשימות). סיבוכיות לינארית.
שלב שלישי - נקדם כל שלב את P1 ו-P2 צעד אחד קדימה ונשווה ביניהם.
סה"כ - שימוש בזיכרון קבוע שאינו תלוי באורך הרשימות, וסיבוכיות לינארית.
הסבר לדרך (או איך חשבתי על זה):
נסתכל על שני מקרי קיצון:
1. רשימה 1 מוכלת בתוך רשימה 2 כולה (כלומר, ה"חיבור" הוא כבר באיבר הראשון של רשימה 1).
2. הרשימות מתחברות רק באיבר האחרון.
מתוך מבט על שני המקרים האלה, ברור לנו שדבר ראשון צריך "לזרוק" את ה"איברים העודפים" - כלומר האיברים שברור לנו שבהם לא יכולה להתרחש התחברות.
ברגע שזרקנו אותם - אנחנו יכולים להתקדם צעד צעד עד שמגיעים לשוויון.
טעות שלי - הצלחתי להעביר רק 533 בננות - לא יודע למה חשבתי שאפשר 866, אולי אכלתי בננה מקולקלת...
יש שלושה שלבים לפתרון.
בשלב הראשון, הגמל מעמיס 1000 בננות, צועד 200 ק"מ, משאיר 600 בננות וחוזר אחורה. ( 400 בננות נאכלות בתהליך).
התהליך חוזר על עצמו עוד פעם - מביא עוד 600 בננות למרחק 200 ק"מ, וחוזר לנקודת ההתחלה.
הגמל לוקח את ה-1000 האחרונים, מקדם אותם 200 מטרת ושם את ה-800 בנקודת ה-200.
בסןף שלה זה יש לנו 2000 בננות (600+600+800) במרחק 200 ק"מ.
בשלב השני הגמל מעמיס בננות, צועד 333 ק"מ, מוריד 334 בננות וחוזר לנקודת ה-200 מטר.
כעת הגמל לוקח את ה-1000 שנ'ארו בנקודת ה-200, ומגיע עם 666 בננות למרחק 333 ק"מ.
בסוף שלב זה יש לנו 1000 בננות במרחק כולל של 533 ק"מ מנקודת ההתחלה, שזה 467 ק"מ מהסוף.
בשלב השלישי, הגמל מעמיס את 1000 הבננות, וצועד לנקודת הסיום עם 533 בננות.
יש שלושה שלבים לפתרון.
בשלב הראשון, הגמל מעמיס 1000 בננות, צועד 200 ק"מ, משאיר 600 בננות וחוזר אחורה. ( 400 בננות נאכלות בתהליך).
התהליך חוזר על עצמו עוד פעם - מביא עוד 600 בננות למרחק 200 ק"מ, וחוזר לנקודת ההתחלה.
הגמל לוקח את ה-1000 האחרונים, מקדם אותם 200 מטרת ושם את ה-800 בנקודת ה-200.
בסןף שלה זה יש לנו 2000 בננות (600+600+800) במרחק 200 ק"מ.
בשלב השני הגמל מעמיס בננות, צועד 333 ק"מ, מוריד 334 בננות וחוזר לנקודת ה-200 מטר.
כעת הגמל לוקח את ה-1000 שנ'ארו בנקודת ה-200, ומגיע עם 666 בננות למרחק 333 ק"מ.
בסוף שלב זה יש לנו 1000 בננות במרחק כולל של 533 ק"מ מנקודת ההתחלה, שזה 467 ק"מ מהסוף.
בשלב השלישי, הגמל מעמיס את 1000 הבננות, וצועד לנקודת הסיום עם 533 בננות.
אמיר.
amirbd,
א. כמעט מדויק תזכור שהגמל אוכל בצורה רציפה, כלומר הפיתרון לא חייב להיות מספר שלם של בננות
ב. איך אמרה לי פעם המורה בכיתה י (וגם moco) על תשובה בלי הוכחה לא מקבלים ניקוד
Shed,
אתה לא בחו"ל עכשיו ?
זה מה שאתה עושה שם ? פותר בעיות על רשימות מקושרות
א. כמעט מדויק תזכור שהגמל אוכל בצורה רציפה, כלומר הפיתרון לא חייב להיות מספר שלם של בננות
ב. איך אמרה לי פעם המורה בכיתה י (וגם moco) על תשובה בלי הוכחה לא מקבלים ניקוד
Shed,
אתה לא בחו"ל עכשיו ?
זה מה שאתה עושה שם ? פותר בעיות על רשימות מקושרות
בחו"ל בחו"ל... אבל מה לעשות ובסנט פטרסבורג (שהיא עיר מדהימה!) יורד גשם והטמפ' הגיעה היום לשיא של שמונה מעלות צלזיוס...osherov כתב:amirbd,
Shed,
אתה לא בחו"ל עכשיו ?
זה מה שאתה עושה שם ? פותר בעיות על רשימות מקושרות...
לא מספיק לקחו לי את השעון קיץ ביום שבת, עכשיו אני בכלל בחורף... לפחות אני יודע שזה זמני
OK, אם מותר שברי בננה אזי אפשר להעביר עוד שליש בננה.
השלב הראשון ללא שינוי - מועברים 2000 בננות למרחק 200 ק"מ
בשלב השנית הגמל לוקח 333.333 בננות ועוד שליש בננה, למרחק של 333 ושליש ק"מ.
אח"כ הגמל לוקח 666 ו2/3 בננות למרחק 333 ושליש ק"מ.
סוף שלב זה יש לנו 1000 בננות במרחק 533 ו-שליש מההתחלה.
בשלב השלישי הגמל מעביר 533 ושליש בננה לנקודת הסיום.
מדוע זה אופטימאלי -
נבחיו כי כל עוד יש יותר מ-2000 בננות כדי להעבירם מרחק x יש צורך ללכת 5x ק"מ, ולצרוך 5x בננות. עוד יש יותר מ-1000 בננות כדי לקדמם מרחק y יש צורך ב-3y בננות, וכשיש לכל היותר 1000 בננות, עולה z בננות כדי לקדמם z ק"מ.
כעת נרשום את מערכת המשוואות :
5x = 1000 (כל עוד יש בין 3000 ל-2000) ==> בשלב א' התקדמנו 200 מטר
3y = 1000 (כל עוד יש בין 1000 ל-2000) ==> בשלב ב' התקדמנו 333.33 מטר
ובשלב השלישי התקדמנו בנגלה אחת עד הסוף
השלב הראשון ללא שינוי - מועברים 2000 בננות למרחק 200 ק"מ
בשלב השנית הגמל לוקח 333.333 בננות ועוד שליש בננה, למרחק של 333 ושליש ק"מ.
אח"כ הגמל לוקח 666 ו2/3 בננות למרחק 333 ושליש ק"מ.
סוף שלב זה יש לנו 1000 בננות במרחק 533 ו-שליש מההתחלה.
בשלב השלישי הגמל מעביר 533 ושליש בננה לנקודת הסיום.
מדוע זה אופטימאלי -
נבחיו כי כל עוד יש יותר מ-2000 בננות כדי להעבירם מרחק x יש צורך ללכת 5x ק"מ, ולצרוך 5x בננות. עוד יש יותר מ-1000 בננות כדי לקדמם מרחק y יש צורך ב-3y בננות, וכשיש לכל היותר 1000 בננות, עולה z בננות כדי לקדמם z ק"מ.
כעת נרשום את מערכת המשוואות :
5x = 1000 (כל עוד יש בין 3000 ל-2000) ==> בשלב א' התקדמנו 200 מטר
3y = 1000 (כל עוד יש בין 1000 ל-2000) ==> בשלב ב' התקדמנו 333.33 מטר
ובשלב השלישי התקדמנו בנגלה אחת עד הסוף
יפה מאוד 
להלן הסבר זהה אך מפורט קצת יותר (כתבתי אותו עוד לפני התשובה של amirbd אז חבל לי לרשום אותה)
הכדור שוב אצלך amirbd (למי שאין כח לקרוא את הכל)
הוכחה:
מכיוון שיש 3000 בננות והגמל יכול לסחוב רק 1000 בננות הגמל צריך לעשות את הדרך הזאת לפחות 5 פעמים מנקודה A (מטע) לנקודה B כדי להעביר את כל הבננות (3 פעמים מ A ל B ו 2 פעמים חזור מ B ל A)
A-------->B
A<--------B
A-------->B
A<--------B
A-------->B
נקודה B בתרשים לא יכולה להיות השוק מכיוון שהגמל לא יכול לנוע יותר מ 500 ק"מ אם הוא מתכנן לחזור למטע (הוא אוכל כל קילומטר בננה)
ולכן נקודה B נמצאת היכן שהוא בין המטע לשוק (נסמן את השוק כנקודה M)
מנקודה B לנקודה הבאה C ידרשו פחות מ 5 רכיבות גמל להעביר את כל הבננות
וכך אנחנו מגיעים לפיתרון הגלובלי שמתואר בתרשים הבא:
א. העברת כל הבננות מ A ל B
A-------->B
A<--------B
A-------->B
A<--------B
A-------->B
ב. העברת כל הבננות מ B ל C
B-------->C
B<--------C
B-------->C
ג. העברת כל הבננות מ C ל M (לשוק)
C-------->M
נכון לעכשיו החלק של A-B חייב להיות כלול בפתרון אך החלק B-C והחלק C-M יכולים להיות במרחק 0 ק"מ
בו נבחן את המחיר של שלושת החלקים:
* כל ק"מ הליכה של הגמל מקטע A ל B צורך 5 בננות !
* כל ק"מ הליכה של הגמל מקטע B ל C צורך 3 בננות
* כל ק"מ הליכה של הגמל מקטע C ל M צורך רק בננה אחת !
ולכן כדי לחסוך בבננות אנחנו צריכים להבטיח ש AB<BC<CM
מכיוון שידוע ש AB>0 נובע שגם BC ו CM גדולים מ 0
נמשיך (לא נשאר עוד הרבה):
הגמל יכול לקחת מקסימום 2000 בננות מנקודה B ל C (עושה את הדרך מ B ל C פעמיים)
ולכן המרחק שנקבע בין A ל B חייב להיבחר כך שבדיוק יגיעו 2000 בננות לנקודה B (פחות מ 2000 והפיתרון לא אופטימלי)
עכשיו סוף סוף אפשר לחשב את AB:
3000-5xAB=2000 כלומר AB שווה ל 200 ק"מ.
את הדרך מ B ל C נחשב בצורה דומה:
הגמל לא יכול לסחוב יותר מ 1000 בננות מנקודה C ל M (עושה את הדרך רק פעם אחת)
ולכן המרחק שנקבע בין B ל C חייב להיבחר כך שבדיוק 1000 בננות יגיעו לנקודה C.
נחשב את BC:
2000-3xBC=1000 כלומר BC שווה ל 333.333 ק"מ.
מכך נובע שהמרחק C ל M הוא CM=1000-200-333.333 כלומר CM שווה ל 466.6667 ק"מ.
כתוצאה מכל זה אנו מגיעים למסקנה שהגמל יכול להעביר מקסימום 1000-466.666=533.333 בננות !!!!
כלומר 533 ו 1/3 בננות
מ.ש.ל
נקווה שלא איבדתם אותי בדרך
להלן הסבר זהה אך מפורט קצת יותר (כתבתי אותו עוד לפני התשובה של amirbd אז חבל לי לרשום אותה)
הכדור שוב אצלך amirbd (למי שאין כח לקרוא את הכל)
הוכחה:
מכיוון שיש 3000 בננות והגמל יכול לסחוב רק 1000 בננות הגמל צריך לעשות את הדרך הזאת לפחות 5 פעמים מנקודה A (מטע) לנקודה B כדי להעביר את כל הבננות (3 פעמים מ A ל B ו 2 פעמים חזור מ B ל A)
A-------->B
A<--------B
A-------->B
A<--------B
A-------->B
נקודה B בתרשים לא יכולה להיות השוק מכיוון שהגמל לא יכול לנוע יותר מ 500 ק"מ אם הוא מתכנן לחזור למטע (הוא אוכל כל קילומטר בננה)
ולכן נקודה B נמצאת היכן שהוא בין המטע לשוק (נסמן את השוק כנקודה M)
מנקודה B לנקודה הבאה C ידרשו פחות מ 5 רכיבות גמל להעביר את כל הבננות
וכך אנחנו מגיעים לפיתרון הגלובלי שמתואר בתרשים הבא:
א. העברת כל הבננות מ A ל B
A-------->B
A<--------B
A-------->B
A<--------B
A-------->B
ב. העברת כל הבננות מ B ל C
B-------->C
B<--------C
B-------->C
ג. העברת כל הבננות מ C ל M (לשוק)
C-------->M
נכון לעכשיו החלק של A-B חייב להיות כלול בפתרון אך החלק B-C והחלק C-M יכולים להיות במרחק 0 ק"מ
בו נבחן את המחיר של שלושת החלקים:
* כל ק"מ הליכה של הגמל מקטע A ל B צורך 5 בננות !
* כל ק"מ הליכה של הגמל מקטע B ל C צורך 3 בננות
* כל ק"מ הליכה של הגמל מקטע C ל M צורך רק בננה אחת !
ולכן כדי לחסוך בבננות אנחנו צריכים להבטיח ש AB<BC<CM
מכיוון שידוע ש AB>0 נובע שגם BC ו CM גדולים מ 0
נמשיך (לא נשאר עוד הרבה):
הגמל יכול לקחת מקסימום 2000 בננות מנקודה B ל C (עושה את הדרך מ B ל C פעמיים)
ולכן המרחק שנקבע בין A ל B חייב להיבחר כך שבדיוק יגיעו 2000 בננות לנקודה B (פחות מ 2000 והפיתרון לא אופטימלי)
עכשיו סוף סוף אפשר לחשב את AB:
3000-5xAB=2000 כלומר AB שווה ל 200 ק"מ.
את הדרך מ B ל C נחשב בצורה דומה:
הגמל לא יכול לסחוב יותר מ 1000 בננות מנקודה C ל M (עושה את הדרך רק פעם אחת)
ולכן המרחק שנקבע בין B ל C חייב להיבחר כך שבדיוק 1000 בננות יגיעו לנקודה C.
נחשב את BC:
2000-3xBC=1000 כלומר BC שווה ל 333.333 ק"מ.
מכך נובע שהמרחק C ל M הוא CM=1000-200-333.333 כלומר CM שווה ל 466.6667 ק"מ.
כתוצאה מכל זה אנו מגיעים למסקנה שהגמל יכול להעביר מקסימום 1000-466.666=533.333 בננות !!!!
כלומר 533 ו 1/3 בננות
מ.ש.ל
נקווה שלא איבדתם אותי בדרך
(amirbd,shed,moco,osherov)אחלה חידה ופתרון !
רק שאלה אחת: האם לא צריך גם לפסול בצורה מפורשת את ויתור על שלב AB? כלומר, אולי היה כדאי פשוט לוותר מראש על כמה בננות ולא לעשות את AB. או שפספסתי משהו בהוכחה או שהתיחסת לזה כמובן מאליו.
יש עוד אנשים. בכל מקרה, זה עדיף בהרבה, על החודשים שלא הייתה פעילות כלל.
גם בחידון הסרטים זה פחות או יותר מסתובב סביב אותה חבורה (שאומנם קצת יותר גדולה) של פותרים. אני למשל ואני בטוח שאחרים, בכל זאת נמצא שם כל הזמן כקורא מהצד , ולעיתים נדירות מצליח להשחיל משהו.
רק שאלה אחת: האם לא צריך גם לפסול בצורה מפורשת את ויתור על שלב AB? כלומר, אולי היה כדאי פשוט לוותר מראש על כמה בננות ולא לעשות את AB. או שפספסתי משהו בהוכחה או שהתיחסת לזה כמובן מאליו.
יש עוד אנשים. בכל מקרה, זה עדיף בהרבה, על החודשים שלא הייתה פעילות כלל.
גם בחידון הסרטים זה פחות או יותר מסתובב סביב אותה חבורה (שאומנם קצת יותר גדולה) של פותרים. אני למשל ואני בטוח שאחרים, בכל זאת נמצא שם כל הזמן כקורא מהצד , ולעיתים נדירות מצליח להשחיל משהו.
משה
