צטט: אופק_כהן 2011-12-20 10:50:24

צטט: pbhba 2011-12-20 10:18:14

בהנחה שאכן מתעלמים מהנזק המצטבר לכדור - בשביל מה צריך 2 כדורים - אם אפשר להמשיך ולבדק את אותו כדור כאילו לא קרה לו נזק?

 

כדי לחסוך בדיקות,

עם כדור אחד יש צורך ב 100 בדיקות 

ועם 2 כדורים? כמה פעמים יש צורך לבדוק כדי לסגור את כל האפשרויות במספר הקטן ביותר של בדיקות

כבר הובהר פה שיש אפשרות לבדק את כל 100 הקומות עם כדור אחד במקסימום של 50 בדיקות בלבד - בהנחה שבטוח שהוא אמור להתנפץ באחת מהן.

מה מוריד הכדור השני?

נתחיל בלבדוק כל קומה עשירית.

נניח שהכדור התנפץ בקומה 60, נשאר לנו לבדוק את הקומות 51 עד 59.

במקרה הגרוע ביותר הכדור הראשון יתנפץ בקומה 100 (10 בדיקות), והשני ב 99 (עוד 9 בדיקות) סה"כ 19.

אם מובטח לנו שהכדור יתנפץ בקומה כלשהי אז אפשר לוותר על הבדיקה של קומה 100 ונשארנו עם 18 בדיקות.

למה דוקא קפיצות של 10?

מספר הבדיקות בשיטה הזו הוא 100 חלקי גודל הקפיצה (מעוגל כמובן) + גודל הקפיצה פחות 1.

קפיצות של 10 (וגם 9 ו 11) יתנו מינימום כיוון שיש כמעט שוויון בין מספר המדידות המקסימלי בכדור הראשון לבין מספר המדידות המקסימלי בכדור השני.

נפל לי האסימון השני.

צטט: השכן ממול 2011-12-20 15:45:24

נתחיל בלבדוק כל קומה עשירית.

נניח שהכדור התנפץ בקומה 60, נשאר לנו לבדוק את הקומות 51 עד 59.

במקרה הגרוע ביותר הכדור הראשון יתנפץ בקומה 100 (10 בדיקות), והשני ב 99 (עוד 9 בדיקות) סה"כ 19.

אם מובטח לנו שהכדור יתנפץ בקומה כלשהי אז אפשר לוותר על הבדיקה של קומה 100 ונשארנו עם 18 בדיקות.

למה דוקא קפיצות של 10?

מספר הבדיקות בשיטה הזו הוא 100 חלקי גודל הקפיצה (מעוגל כמובן) + גודל הקפיצה פחות 1.

קפיצות של 10 (וגם 9 ו 11) יתנו מינימום כיוון שיש כמעט שוויון בין מספר המדידות המקסימלי בכדור הראשון לבין מספר המדידות המקסימלי בכדור השני.

זה לא נכון. אם הכדור יתפוצץ בקומה התשיעית, לפי השיטה שלך עשינו 1 + 9 = 10 בדיקות

לפי השיטה שלי (נבדוק כל קומה שניה) יש רק 5 + 1 = 6 בדיקות.

אולי כדאי שתתפשרו על כל עשרת ואח"כ חיתוך בשישית או ברביעת מתוך העשרת הזו ומשם להתנווט למעלה או מלמטה בתוך העשרת.

זה בטח יחסוך משהו.

צטט: השכן ממול 2011-12-20 15:45:24

נתחיל בלבדוק כל קומה עשירית.

נניח שהכדור התנפץ בקומה 60, נשאר לנו לבדוק את הקומות 51 עד 59.

במקרה הגרוע ביותר הכדור הראשון יתנפץ בקומה 100 (10 בדיקות), והשני ב 99 (עוד 9 בדיקות) סה"כ 19.

אם מובטח לנו שהכדור יתנפץ בקומה כלשהי אז אפשר לוותר על הבדיקה של קומה 100 ונשארנו עם 18 בדיקות.

למה דוקא קפיצות של 10?

מספר הבדיקות בשיטה הזו הוא 100 חלקי גודל הקפיצה (מעוגל כמובן) + גודל הקפיצה פחות 1.

קפיצות של 10 (וגם 9 ו 11) יתנו מינימום כיוון שיש כמעט שוויון בין מספר המדידות המקסימלי בכדור הראשון לבין מספר המדידות המקסימלי בכדור השני.

הדרך חשיבה נכונה אך ניתן לבצע בפחות מ 19 בדיקות

אם ניקח לדוגמא אפשרות של שבר בקומה 7 בעשרת הרשאונה, הרי בשיטה שאני הצעתי יש לבדוק את הקומות 10, 6, 8 ,7.

וזה פחות בדיקות מאשר בכל אחת משתי השיטות הקודמות שהוצעו:

2.4.6.8.7. [=5בדיקות]

10, 2, 4, 6, 8, 7,  [= 6בדיקות]

ובוודאי אם חוזרים מסוף העשרת מההתחלה קומה קומה עד שמגיעים ל7  שאז נגיע ל8 בדיקות בתוך העשרת הזו.

צטט: pbhba 2011-12-20 20:40:12

אם ניקח לדוגמא אפשרות של שבר בקומה 7 בעשרת הרשאונה, הרי בשיטה שאני הצעתי יש לבדוק את הקומות 10, 6, 8 ,7.

 

וזה פחות בדיקות מאשר בכל אחת משתי השיטות הקודמות שהוצעו:

2.4.6.8.7. [=5בדיקות]

10, 2, 4, 6, 8, 7,  [= 6בדיקות]

ובוודאי אם חוזרים מסוף העשרת מההתחלה קומה קומה עד שמגיעים ל7  שאז נגיע ל8 בדיקות בתוך העשרת הזו.

החכמה לסגור את כל האפשרויות של התנפצויות הכדור מקומה 1 עד קומה 100

במספר הבדיקות הקטן ביותר.

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

צטט: pbhba 2011-12-20 20:40:12

אם ניקח לדוגמא אפשרות של שבר בקומה 7 בעשרת הרשאונה, הרי בשיטה שאני הצעתי יש לבדוק את הקומות 10, 6, 8 ,7.

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

צטט: אופק_כהן 2011-12-20 20:25:25

צטט: השכן ממול 2011-12-20 15:45:24

נתחיל בלבדוק כל קומה עשירית.

נניח שהכדור התנפץ בקומה 60, נשאר לנו לבדוק את הקומות 51 עד 59.

במקרה הגרוע ביותר הכדור הראשון יתנפץ בקומה 100 (10 בדיקות), והשני ב 99 (עוד 9 בדיקות) סה"כ 19.

אם מובטח לנו שהכדור יתנפץ בקומה כלשהי אז אפשר לוותר על הבדיקה של קומה 100 ונשארנו עם 18 בדיקות.

למה דוקא קפיצות של 10?

מספר הבדיקות בשיטה הזו הוא 100 חלקי גודל הקפיצה (מעוגל כמובן) + גודל הקפיצה פחות 1.

קפיצות של 10 (וגם 9 ו 11) יתנו מינימום כיוון שיש כמעט שוויון בין מספר המדידות המקסימלי בכדור הראשון לבין מספר המדידות המקסימלי בכדור השני.

 

 

הדרך חשיבה נכונה אך ניתן לבצע בפחות מ 19 בדיקות

צודק.

אפשר לשפר את השיטה ולהגיע למקסימום של 14 בדיקות.

הסבר בלבן

באמצעות הכדור ראשון נבדוק (עד שיתנפץ) את הקומות לפי הסדר: 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99 (אם הוא לא התנפץ ב 99 אז נבדוק את 100).

הרעיון הוא להתחיל ב 14 לעלות 13 קומות ואחרי זה 12 קומות וכן הלאה.

ובכל צעד מקטינים את הקפיצה ב 1.

אם הכדור הראשון התנפץ בבדיקה n יש לבדוק בעזרת הכדור השני את כל הקומות שבין הקומה שנבדקה בבדיקה n-1 לבדיקה שבה הכדור נשבר.

מספר הבדיקות שנבצע עם הכדור הראשון עד שיתנפץ + מספר הקומות בין הבדיקה שבה התנפץ הכדור הראשון לבדיקה שלפניה יהיה תמיד 14.

למשל אם הכדור יתנפץ בקומה 84, יוצא שעשינו 8 בדיקות עם הכדור הראשון. עם הכדור השני נצטרך במקרה הגרוע ביותר לבדוק את 6 הקומות שבין 78 (את 77 כבר בדקנו עם הכדור הראשון) עד 83 (כולל)ככה שסה"כ בדקנו 14.

למה דוקא 14?

כי אם היינו מתחילים מ 15 התוצאה במקרה הגרוע הייתה 15. ואם היינו מתחילים מ 13 לא היינו מצליחים לכסות את כל הבניין.

צטט: stormsurfer 2011-12-20 18:40:20

צטט: השכן ממול 2011-12-20 15:45:24

נתחיל בלבדוק כל קומה עשירית.

נניח שהכדור התנפץ בקומה 60, נשאר לנו לבדוק את הקומות 51 עד 59.

במקרה הגרוע ביותר הכדור הראשון יתנפץ בקומה 100 (10 בדיקות), והשני ב 99 (עוד 9 בדיקות) סה"כ 19.

אם מובטח לנו שהכדור יתנפץ בקומה כלשהי אז אפשר לוותר על הבדיקה של קומה 100 ונשארנו עם 18 בדיקות.

למה דוקא קפיצות של 10?

מספר הבדיקות בשיטה הזו הוא 100 חלקי גודל הקפיצה (מעוגל כמובן) + גודל הקפיצה פחות 1.

קפיצות של 10 (וגם 9 ו 11) יתנו מינימום כיוון שיש כמעט שוויון בין מספר המדידות המקסימלי בכדור הראשון לבין מספר המדידות המקסימלי בכדור השני.

זה לא נכון. אם הכדור יתפוצץ בקומה התשיעית, לפי השיטה שלך עשינו 1 + 9 = 10 בדיקות

לפי השיטה שלי (נבדוק כל קומה שניה) יש רק 5 + 1 = 6 בדיקות.

לכל שתי שיטות שונות ניתן למצוא מקרה פרטי שבו אחת מהן יותר יעילה מהשניה.

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

צטט: stormsurfer 2011-12-21 01:00:56

צטט: pbhba 2011-12-20 20:40:12

אם ניקח לדוגמא אפשרות של שבר בקומה 7 בעשרת הרשאונה, הרי בשיטה שאני הצעתי יש לבדוק את הקומות 10, 6, 8 ,7.

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

זה נכון.