Древний холивар о том, нужна ли программисту математика, получил неожиданное продолжение в спорах о ЕГЭ. Активно начала продвигаться идея о том, что вообще не надо проверять знания, а надо проверять умение быстро искать ответы. Ну и как вывод – замена ЕГЭ на чемпионат по поиску в Гугле/Яндексе. На мой взгляд, с тем же успехом можно проводить экзамен в виде поиска по школьной библиотеке. Почему-то никто не замечает такой очевидной истины, что быстро находит ответы те, кто знают, что искать, то есть как раз обладают знаниями. Для подтверждения этой идеи я составил 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. Во время хода второго игрока стол еще пуст, поэтому он не заберет ни одной монеты и проиграет.
Задача 2: остовное дерево
Задача 3: числа Каталана
Автор: ElGatoAhuecado
