חידה

[רסיסי]

../images/Emo36.gif חידה../images/Emo70.gif ../images/Emo26.gif

יש ברשותכם 1000 תפוחים ו-10 ארגזים. אתם צריכים לסדר את כל התפוחים בעשרת הארגזים באופן שבו תוכלו לתת למישהו כל מספר של תפוחים שיבקש (בין 1 ל-1000) ע"י חיבור של כמה ארגזים (אסור להעביר תפוחים מארגז לארגז) לדוגמא: אם אני מבקש מכם 783 תפוחים, עליכם לתת לי כמה ארגזים שסה"כ יתנו לי 783 תפוחים.

 

[Fingertip]

../images/Emo62.gifאני יודע!

נחדד טיפה את הבעיה: בסופו של דבר, תהיה לנו שורה של ארגזים כך שאם מישהו יבוא אלינו, נוכל לבחור או לא לבחור כל ארגז עד שנקבל קבוצה שמכילה בדיוק את מספר התפוחים שהוא רוצה. טיפה מזכיר ספירה בבסיס 2: יש לנו רשימה של ספרות, כאשר 1 במקום ה-i מבטא "לקחנו את הארגז ה-i", ו-0 מבטא "לא לקחנו". המשקל של כל ספרה תלוי במיקום שלה. המיקום הראשון שוקל 1. השני שוקל 2, השלישי 4, הרביעי 8 וכך הלאה. לכן, בארגז ה-i נשים 2 בחזקת i-1 תפוחים, ובארגז ה-10 נשים את כל התפוחים שנשארו לנו. ככה, אם מישהו בא אלינו ומבקש תפוח, אז אם הוא יבקש 511 או פחות, נייצג את המספר בבינרי וניתן לו את הארגזים המתאימים, ואם הוא יבקש יותר, אז ניתן לו את הארגז העשירי, ונחשב את מספר התפוחים שהוא עוד צריך, וניתן לו אותם שוב באמצעות ספירה בינרית. אהד.

 

[djdror]

../images/Emo62.gif אני אוהב תפוחים

1,2,4,8,16,32,64,128,256,489