Вчера прочитал историю №981590 mathematicus про площадь треугольника (подленькая задача) и напомнило.
Сам информатик. Сдавал недавно диагностику в формате ЕГЭ в МЦКО.
27 заданий. 3 часа 50 минут. Задача №26. Состоит из 3-х подзадач.
Во второй подзадаче требуется нарисовать (в виде дерева или таблицы) выигрышную стратегию игрока, выигрывающего СВОИМ ЧЕТВЕРТЫМ ХОДОМ.
Начинаю рисовать дерево и обнаруживается, что один из игроков может выиграть СВОИМ ТРЕТЬИМ ХОДОМ! Начинается ступор: либо игрок идиот, и имея возможность выиграть на третьем ходе специально игнорирует такую возможность и продолжает играть дальше, либо авторы ошиблись с номером выигрышного хода. Чтобы проверить первую гипотезу надо строить дерево дальше, а оно и так уже о-го-го! Поэтому расписываю стратегию выигрыша третьим ходом.
Приходят результаты - идиот похоже я. Пишу программу рекурсивной генерации дерева вариантов и сохраняю дерево в Excel. У дерева на 8-м уровне 22 листа! Прохожу (внимательно) по дереву и действительно нахожу выигрышную стратегию этого игрока на 4-м ходу! НО! Для этого надо было построить полное дерево! Без ошибок! Застрелиться! Я им что, компьютер?!
В общем, задача подлая (с подвохом) трудоемкая (минут 40-50 на нее точно уйдет, если считать с переписыванием в чистовик)
Если кому интересно, может засечь время, за которое он построит это дерево игры. Вот условие задачи:
Петя и Вася играют в игру. На столе имеется 8 костей (как у домино), только вместо цифр –буквы. Это кости АА, АБ, АВ, БА, ББ, БВ, ВА, ВБ. Из костей игроки строят цепочку, беря по очереди кость из кучи, и добавляя ее справа к уже имеющимся, если совпадают буквы на концах костей (как в домино). Переворачивать кость нельзя, то есть АБ не может быть добавлена как БА. Проигрывает тот, кто не может добавить очередной кости в цепочку.
Требуется:
1. Составить самую короткую игровую цепочку (если их несколько – то любую)
2. Первый ход Пети АА. Найти выигрышную стратегию игрока, выигрывающего своим четвертым ходом и нарисовать дерево (или таблицу) стратегии.
3. Убрать из кучи 2 кости, так чтобы в любом случае выигрывал не тот игрок, который побеждает в задании 2. Тоже нарисовать дерево (таблицу)
Вот такая задача. Я преподаю информатику 30 лет, но у меня сложилось четкое ощущение, что это задача с конкретной целью – завалить. Интересно, у кого получится решить эту задачу быстрее чем за 40 минут? Только без использования компа.
Кстати, не только половина математиков «завалила» экзамен. Половина информатиков тоже