Три задачи для программистов, которым не нужна математика

Древний холивар о том, нужна ли программисту математика, получил неожиданное продолжение в спорах о ЕГЭ. Активно начала продвигаться идея о том, что вообще не надо проверять знания, а надо проверять умение быстро искать ответы. Ну и как вывод – замена ЕГЭ на чемпионат по поиску в Гугле/Яндексе. На мой взгляд, с тем же успехом можно проводить экзамен в виде поиска по школьной библиотеке. Почему-то никто не замечает такой очевидной истины, что быстро находит ответы те, кто знают, что искать, то есть как раз обладают знаниями. Для подтверждения этой идеи я составил 3 задачки для программистов, алгоритмы решения которых я нашел бы за пару минут.

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

Задача 1: Охранник на предприятии должен отработать за апрель 6 суток (с 00:00 по 23:59). Выведите все способы расстановки этих 6 суток в формате 00100111000, где 0 – выходной, 1 – рабочий день. Охранник может работать и 6 суток подряд.

Задача 2: Директор компании Мелкософт поставил перед вами задачу написать скринсейвер, в котором имитируется обход лабиринта по правилу левой руки из случайной точки. Второй программист написал функцию, которая генерирует связанные лабиринты (можно от любой точки дойти до любой), но в некоторых случаях обход по правилу левой становится обходом по кругу вокруг стенки. Необходимо добавить в лабиринт новые стенки, чтобы он остался связанным, но в нем не осталось бы круговых маршрутов, при которых обходится не весь лабиринт.

Задача 3: У первого игрока есть N монет, а у второго их нет совсем. Игроки решают чей ход бросанием монетки. Если ходить выпало первому, то он кладет на стол 1 монету. Если второму – он забирает со стола 1 монету, если стол не пустой. Как только один игрок сделал N ходов, дальше ходит только другой, пока тоже не сделает N ходов. Сколько существует последовательностей выпадения монетки, при которых второй игрок заберет все монеты?

Пример 1: N=4. 11112222. При такой последовательности ходов сначала первый выложит N монет, а потом второй их все заберет. Второй победил.

Пример 2: N=1. 21. Во время хода второго игрока стол еще пуст, поэтому он не заберет ни одной монеты и проиграет.

Что бы искал я? После небольших размышлений я бы вбил в поисковик:

Задача 1: генерация сочетаний

Задача 2: остовное дерево

Задача 3: числа Каталана

This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at fivefilters.org/content-only/faq.php#publishers. Five Filters recommends: 'You Say What You Like, Because They Like What You Say' - http://www.medialens.org/index.php/alerts/alert-archive/alerts-2013/731-you-say-what-you-like-because-they-like-what-you-say.html