Решение задачек

7. У вас есть 8 с виду одинаковых монет, одна из которых, тем не менее, фальшивая. Фальшивая монета чуть тяжелее, но во всем остальном идентична настоящим. У вас также есть, в лучших традициях жанра, весы с чашечками, как у богини правосудия. За какое минимальное число взвешиваний можно определить фальшивку? (популярная задача)

Решение Разбиваем монеты на три группы: 1 и 2 группы по три монеты, 3 группа - две. Взвешиваем 1 и 2 группу, если они равны, то фальшивая монета в группе 3, она находится еще за одно взвешивание (итого 2 взвешивания) Если 1 и 2 группы не равны по весу, то выбираем ту, в которой фальшивая монета (эта группа будет тяжелее), выбираем любые две монеты из группы и взвешиваем их, если получили равенство, то фальшивая монета та, которую мы не выбрали, если не получили равенства, то все просто)) итого 2 взвешивания

10. Есть три урны из тех, что содержат шары в задачках по теории вероятности. На первой написано «ЧЕРНЫЕ», на второй - «БЕЛЫЕ», на третьей - «ЧЕРНЫЕ И БЕЛЫЕ». В одной лежат белые шары, в другой - черные, в оставшейся - и черные и белые. Все надписи заведомо ложны. Разрешается достать один шар из только одной урны. Как определить в какой урне что лежит? (Microsoft)

Решение Выбираем урну с надписью “ЧЕРНЫЕ И БЕЛЫЕ” и тянем из нее шар, если вытянули белый, то в этой урне на самом деле лежат белые шары, а в урне с надписью “ЧЕРНЫЕ” лежат черные и белые шары, если вытащили черный, то в урне лежат черные шары, а в урне с надписью “БЕЛЫЕ” лежат черные и белые шары.

12. Обойти двоичное дерево, НЕ используя рекурсию. (Michael Abrash)

Решение Если в задаче разрешено использовать дополнительную память, то решение простое, с помощью стека. Пришли в вершину заносим в стек (что имено заносим и в каком порядке зависит от того, какой обход нужен: КЛП, ЛКП и т.д.)

23. Есть круглый бассейн. От его бортика в направлении точно на север отплыла рыба. Проплыв 6 метров, она опять столкнулась с бортиком. Тогда рыба повернула на восток, проплыла еще 8 метров и опять столкнулась с бортиком. Найти диаметр бассейна. (опять Мартин Гарднер)

Решение Тут все просто, если соединить начальную и конечную точку, то получится прямоугольный треугольник с катетами 6 и 8 метров, а гипотенуза будет являться диаметром (я не помню как называется этот угол образованный катетами, но этот угол в два раза меньше центрального угла опирающегося на ту же дугу, а так как он равен 90 градусов, то центральный угол 180 градусов, а следовательно дуга - полуокружность, а гипотенуза - диаметр)

25. У вас есть зажигалка и веревка. Если веревку поджечь с конца, то она вся сгорит за полчаса. Как отмерить, при помощи этих двух предметов 15 минут? Важное обстоятельство: Веревка горит неравномерно, где-то быстрее, где-то медленнее. (очень популярная задача)

Решение Поджечь с двух сторон, наверно

27. Вы стоите посреди замерзшего озера на идеально скользком льду. Трения нет вообще. Придумайте как можно больше способов добраться до берега. (Physics Mountain)

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