שאלה לדוגמא: נתונות 2 מנורות ובניין בן 100 קומות. צריך בעזרת מספר מינימלי של זריקות מנורה למצוא את הקומה ממנה המנורה תשבר אם נזרוק אותה (כל המנורות נשברות החל מקומה מסויימת). מהו המספר המינימלי של זריקות שניתן לבצע כדי לגלות את מספר הקומה הנ"ל?
תשובות
הוסף תשובה
|
לצפיה בתשובות
פברואר 2019
מבחינת האלגוריתם: נחפש בקפיצות של X קומות את הקומה שממנה הנורה הראשונה תישבר. ברגע שמצאנו קומה כזו נחזור לקומה הקודמת שבה הנורה לא נשברה. כעת נעלה קומה קומה עד שהנורה השנייה תישבר.
מבחינת X: ה-X האופטימלי (עבור 100 קומות) יהיה 10. מכיוון שיהיו לנו לכל היותר 19 זריקות.
כל X אחר ייתן מספר גבוה יותר של קפיצות.
דוגמה: הקומה שבה הנורה נשברת היא 99
נבדוק את
10, 20, 30, 40, 50, 60, 70, 80, 90, 100
בקומה 100 הנורה הראשונה נשברה, כעת עם הנורה השנייה:
91, 92, 93, 94, 95, 96, 97, 98, 99
ומצאנו ש-99 היא הקומה שבה הנורה נשברת. סה"כ 19 זריקות.
מרץ 2019
יותר מדויק 18 זריקות מקסימום הזריקה לקומה 100 בסט הראשון של בזריקות לא נצרך .אם זרקת ל90 ולא נשבר אפשר להמשיך משם ישר ל91 והלאה עד 99 לא נשבר ב99 ידוע שב100 יישבר בלי לזרוק
מאי 2019
אני חושבת שאפשר כמו חיפוש בינארי. ואז אם זה בקומה 99 אז מגלים את זה תוך 7-8 זריקות
ספטמבר 2019
חיפוש בינארי log(100) במקרה הגרוע.
דצמבר 2019
עץ חיפוש בינארי לא יעבוד במקרה שהקומה היא הקומה הראשונה ואז אחרי 2 זריקות 2 המנרות ישברו
דצמבר 2019
מסכים שמדובר בחיפוש בינארי (לא עץ חיפוש בינארי כפי שאמר קודמי).
Log(n).
ינואר 2020
הקטע של השאלה הוא שיש שתי מנורות, ואם אחת נשברה אז עם השניה צריך לברר באיזה קומה מינימלית היא נשברת. חיפוש בינארי הוא לא מוצלח כי אם בקומה 50 המנורה נשברת אז נצטרך לזרוק מקומה 1 עד במקרה הגרוע 49 כדי לגלות באיזה קומה המנורה נשברת. (50 זריקות)
הטכניקה הנכונה היא לבצע חישוב לאיזה קומה כדאי ללכת.
וזה מתבצע על ידי החישוב:
100 = x(x-1) /2
x = 13.6 בערך אז 14 זאת התשובה. (גם של כמות הזריקות המקסימלית)
זורקים בקומה 14, אם המנורה נשברת אז יש 13 קומות נוספות לבדוק (נמוכות מ14) במקרה הגרוע - 14 זריקות
אם המנורה לא נשברת עולים ב13 קומות לקומה 27. אם שם היא נשברת אז שוב יש סך הכל 14 זריקות... פעם אחת ב14, פעם אחת ב27 ועוד 12 במקרה הגרוע אם המנורה נשברה בקומה 26.
וכן הלאה... עולים 12 קומות מ27....
עוסקת בפיתוח, תכנות, שיווק ומתן זיכיונות למערכות הפעלה למחשבים, פתרונות תוכנה למגזר הפרטי והעסקי ומגוון פלטפורמות משולבות חומרה ותוכנה. בתחום המוצרים ללקוחות משווקת החברה מערכות הפעלה לשרתים, מחשבים אישיים ומחשבי כף יד.
ראיון לתפקיד 
