11 років ми вчимо математику в школі з думкою: “А чи знадобляться ці обчислення і дроби мені в житті?
Як виявляється, знадобляться.
Доведемо вам це за допомогою задачки, яку пропонують на співбесіді у Googlе на посаду менеджера з інфопродуктів. Тобто людини, яка керує програмістами, проектами. Вона відповідає за розробку і успішність поставлених цілей.
Якщо ви зібрались працювати в ІТ-компанії, то зверніть увагу на задачі такого типу.
А от і сама задача.
Вам дано два яйця невідомого походження і доступ до 100-поверхового хмарочоса. Яйця можуть бути надзвичайно крихкими і розбитись, впавши з 1 поверху, а можуть бути настільки міцними, що і не розіб’ються пролетівши зі сотого поверху.
На вигляд вони однакові за міцністю. Вам потрібно дізнатись з якого максимально високого поверху можуть впасти яйця і не розбитись. Зробити це потрібно за мінімальну кількість спроб( у вашому випадку усних обчислень).
Вирахуйте поверх!
Таку задачку колись пропонували і дітям в радянських школах. Можливо, хтось пам’ятає розв’язок?
Якщо, ні, то ловіть!
Розв’язання
Задачі такого типу розв’язуються за одним і тим же принципом. Тому може тренуватись!
Перший – найпростіший варіант
І найочевидніший. Але найнеефективніший! Вам потрібно піднятись на перший поверх і вкинути яйце, якщо розбилось, то іти на третій, на четвертий і аж до сотого. В кращому випадку вам знадобиться одна спроба, а в гіршому 100.
Але ж нам потрібно використати найменше число спроб. Тому такий варіант не для нас.
Другий варіант
Можна розпочати з середини. Тобто, тепер кидаємо яйце з 50-ого поверху. Якщо розбилось, то спускаємось на поверх нижче і аж до першого. Яко не розбилось, то піднімаємось почергового до 100. Тепер максимально нам знадобиться 50 спроб. Вже краще, але до оптимального вирішення ще далеко!
Третій варіант
А що якщо розділити 100 поверхів на 10 секторів по 10 поверхів? Перший раз кидаємо з 10 поверху. Якщо яйце розбилось, йдемо кидати його з першого, другого і так далі.
Якщо з 10 не розбилось, то піднімаємось на 20 поверх. Якщо розбилось, йдемо на 11, 12… Якщо ні піднімаємось на 30. Думаю, принцип ви зрозуміли.
Тут у гіршому випадку у нас вийде 19 спроб. Набагато менше, ніж у першому варіанті, чи не так?
Четвертий – оптимальний варіант
Можна ще більше подробити 100 поверховий будинок. Наприклад, 20 частин по 5 поверхів.
Давайте, зробимо підранку для різних варіацій.
Якщо 2 поверхи, потрібно кидати через один поверх, щоб була найменша кількість кидків.
Якщо 4 поверхи, то кидати вперше потрібно на другому.
Якщо 8 поверхів, то треба кидати на третьому! Так, саме на третьому, а не на четвертому, бо якщо кинути спочатку на четвертому, то в найгіршому випадку доведеться зробити 5 кидків, а не 4.
І тут знадобилося б знання логарифму, тому що тут є збільшення числа. Виходить, що кинути яйце треба з такого поверху, щоб кількість кидків усередині цього кроку була не більшою за найгірший варіант.
Таким чином, якщо N — це кількість поверхів, а k — кількість кидків, виходить k•(k+1)/2≥N. Вирішуємо цю нерівність для N=100 поверхів та отримуємо k=14.
Перевірка
Перший кидок робимо з 14-го поверху. Другий, якщо яйце не розбилося, з 14+13=27 поверху. Третій, якщо яйце ще не розбилося, з 27+12=39 поверху. І так далі.
Суть проста: щоразу ми додаємо поверхів на одиницю менше, щоб сумарна кількість кидків не перевищила 14 за найгіршого результату. Тому кидаємо з 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99.
Припустимо перше яйце розбилося при кидку з 50-го поверху. Виходить, що ми зробили вже 4 кидки. За решту 10 (або раніше) ми точно зрозуміємо, починаючи з якого поверху яйця битимуться. Друге яйце ми спробуємо розбити спочатку з 40 (бо з 39-го вже пробували), потім з 41, 42, …, 49 поверхів. Або друге яйце розіб’ється на одному з цих поверхів, чи ні. В останньому випадку буде рівно 14 кидків (найгірший сценарій).
Така задачка надзвичайно проста для програмістів. Це ази.
А чи впорались ви з цією задачкою?
