Question

Марійка задумала число від 1 до 100. Яку найменшу кількість спроб має зробіти Андрій щоб відгадати число?

Answer 1

Андрій має зробити 50 спроб

Answer 2

Як відгадати число, задумане Марійкою?

Щоб відгадати число, задумане Марійкою від 1 до 100, Андрію потрібно використати стратегію, яка дозволить йому зробити найменшу кількість спроб. Одним з можливих підходів є використання методу "дихотомічного пошуку" або "бінарного пошуку".

Дихотомічний пошук (Бінарний пошук)

1. Андрій починає з середнього числа діапазону, тобто 50. 2. Він запитує Марійку, чи задумане число більше, менше або дорівнює 50. 3. Якщо Марійка відповідає, що задумане число більше 50, Андрій знає, що число може бути від 51 до 100. 4. Якщо Марійка відповідає, що задумане число менше 50, Андрій знає, що число може бути від 1 до 49. 5. Якщо Марійка відповідає, що задумане число дорівнює 50, Андрій відгадав число і процес завершується. 6. Андрій повторює кроки 2-5 з новим діапазоном чисел, скорочуючи його наполовину на кожному кроці. 7. Процес продовжується до тих пір, поки Андрій не відгадає число.

Кількість спроб

За допомогою дихотомічного пошуку, Андрій зможе відгадати число, задумане Марійкою, за максимум 7 спроб. Це випливає з того, що кожна спроба дозволяє Андрію скоротити діапазон чисел наполовину. Починаючи з діапазону від 1 до 100, Андрій зможе знайти задумане число за наступними кроками:

1. Спроба 1: Андрій запитує, чи задумане число більше 50. 2. Спроба 2: Андрій запитує, чи задумане число більше 75. 3. Спроба 3: Андрій запитує, чи задумане число більше 87. 4. Спроба 4: Андрій запитує, чи задумане число більше 93. 5. Спроба 5: Андрій запитує, чи задумане число більше 96. 6. Спроба 6: Андрій запитує, чи задумане число більше 98. 7. Спроба 7: Андрій запитує, чи задумане число більше 99.

На сьомій спробі Андрій відгадує число, оскільки діапазон стає таким малим, що включає лише одне число.

Отже, Андрій зможе відгадати число, задумане Марійкою, за найменшу кількість спроб - 7 спроб.