חידה

[Yoava333]

חידה

היום עשיתי מבחן של "אולפיאדית מדעי המחשב", והייתה שם שאלה שאני לא בטוח בתשובה שלה, אז הנה היא: בלוח של 2 על N(שתי שורות N עמודות), N>2, מסדרים שלושה אבני דומינו בגוגל 1*2, 2*1 ו-2*2, כמה אפשרויות של סידור יש, לדוגמא ל-N=3 יש 5 אפשרויות 1. 2*2, 2*1 2. 2*1, 2*1, 2*1 3. 1*2, 1*2, 2*1 4. 2*1, 1*2, 2*1 5. 2*1, 2*2

 

[ש ב ו ז]

תשובה...

שים לב שתחת אבן מאוזנת 2*1 חייבת לבוא אבן כזאת נוספת ממש מתחתיה אחרת נשארת משבצת מיותמת תמיד (מדוע? שים לב לאיך מושפע יחס הזוגיות של רצפי משבצות ריקות סמוכות מלמעלה כתוצעה משימת אבן.) לכן f=f(n-1)+2*f(n-2)l

 

[gil levi]

עוד חידה

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

 

[yossiea]

שמעתי על חידה מאוד דומה...

והפתרון כנראה קרוב. זה הולך ככה יש לך 64 מדרגות ושני כדורים. אם תזרוק כדור על אחת מהמדרגות הכדור ירד ויתגלגל במורד המדרגות. ידוע שמדרגה מסויימת גורמת לכדור להתפוצץ (למשל מסמר בולט). אנחנו לא יכולים לראות פיזית באיזה מדרגה התפוצץ הכדור. כמה נסיונות נעשה עד שנמצא את המדרגה הקלוקלת? למיטב זכרוני הפתרון נמצא ברעיון של טור חשבוני. אני לא בטוח אבל נראה לי לפתור את השאלה שלך ככה, זורקים את הכדור בקומות: 14,27,39,50,60,69,77,84,90,95,99 מלמטה כלפי מעלה. בכל שלב מנצלים את הכדור הראשון כדי לדעת האם הכדור נשבר בקבוצת קומות נתונה ואת השני כדי למצוא את הקומה הנכונה בתוך הקבוצה הזו בחיפוש סדרתי רגיל מלמטה כלפי מעלה. עבור הקבוצה הראשונה זה 1 + 13, עבור השנייה 2 + 12 וכו'. צריך להיות מינימום 14 בדיקות אם אני לא טועה. אני קרוב?

 

[DadleFish]

כן, זו התשובה הנכונה.