Чегой-то тихо стало на форуме, скучно... Предлагаю вашему вниманию еще несколько задачек задававшихся в свое время на собеседованиях в Интеле, IBM, и т.д. Может будут полезны будущим соискателям, а те кто сами проводят собеседования могут взять их на вооружение.

Сразу предупреждаю, что задачи не на знание языка/умение программировать, а на создание эффективных алгоритмов решения - писать код в них обычно не нужно. Ну и, разумеется, решения ко всем задачам можно найти в и-нете, если кто сам не осилит.

Задача 2:

У вас имеется 100-этажный дом и два яйца (куриных). На каждом этаже дома есть окно, из которого можно эти яйца бросить на прохожих. Известно что яйцо разбивается при падении, начиная с определенной высоты бросания. Т.е. если оно сброшено с высоты Х или больше, то яйцо разбивается, если с высоты меньше Х - остается целым.

Нужно придумать алгоритм, позволяющий, имея только два яйца, определить этаж, начиная с которого яйца бьются, за наименьшее число попыток.
Важно:
- если после падения яйцо осталось целым, его можно поднять и бросить снова.
- сложность алгоритма определяется худшим случаем, т.е. случаем при котором алгоритм требует наибольшее число шагов.

Пример:
Пусть будет такой алгоритм - кидаем яйцо с первого этажа: если оно разбилось - ответ найден; если осталось целым - подбираем и кидаем со второго. И т.д. до тех пор пока не разобьется.
При таком алгоритме если яйцо разбивается начиная с первого этажа, то ответ будет найден за 1 попытку (лучший случай), однако если оно разбивается начиная с 100-го, то нам потребуется 100 попыток, чтобы придти к ответу. Значит для этого алгоритма МАХ = 100.

Удачи !


Другие задачи:
Задача 1
Задача 3

Метод половинчатого деления пока только в голову пришел)))

_____________
Если вам недостаточно собственных заблуждений, можно расширить их мнениями экспертов.

Нужно уважать мнение оппонета. Ведь заблуждаться - его святое право.

Настаивал, настаиваю и буду настаивать на своем. На кедровых орешках.

twin, it may come as a surprise, но у тебя только два яйца

если ты бросишь первое с 50-го этажа и оно разобьется - у тебя останется не так много вариантов.

На ум приходит только теория вероятности.

Alchemist

Если не разобъется кстати, его же с 75-го надо запулить))). Но это кагбэ в формулу не укладываецо. Тут придется действительно теорию веротности юзать)

_____________
Если вам недостаточно собственных заблуждений, можно расширить их мнениями экспертов.

Нужно уважать мнение оппонета. Ведь заблуждаться - его святое право.

Настаивал, настаиваю и буду настаивать на своем. На кедровых орешках.

Первым пришел в голову метод простого перебора! Причем сначала опробовать одно яйцо бросая его и вероятнее всего получая случайным образом результат целое или нет. Потом по тем этажам на которых не разбилось первое яйцо пробежаться со вторым. Если второе яйцо будет целым до того этажа на котором разбилось первое то за результат принять этаж на котором разбилось первое яйцо, если второе яйцо разбилось раньше то за результат принять этаж на котором разбилось второе яйцо.

Для того чтобы получить статистически достоверный результат наверное надо 2000 яиц. Тогда с минимальной погрешностью можно будет определить этот самый этаж. А при имеющихся данных пока только метод простого перебора. Подумаю на досуге про еще какой-то метод.

_____________
Трус не играет в хокей

Через один можно попробовать... Только как посчитать не соображу.

_____________
Если вам недостаточно собственных заблуждений, можно расширить их мнениями экспертов.

Нужно уважать мнение оппонета. Ведь заблуждаться - его святое право.

Настаивал, настаиваю и буду настаивать на своем. На кедровых орешках.

Почему бы не швырять яйца с кратных 10 этажей, т.е. с 10, 20, 30 и так далее. Тогда max = 20. Или не?

_____________
Свои мозги еще никто не отменял.
Телепатов нету.

waldicom

С 100-го нет смысла кидать.

_____________
Если вам недостаточно собственных заблуждений, можно расширить их мнениями экспертов.

Нужно уважать мнение оппонета. Ведь заблуждаться - его святое право.

Настаивал, настаиваю и буду настаивать на своем. На кедровых орешках.