Pull to refresh

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

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


UPD. Важно


Задача состояла не в том, чтобы решить эти задачи любой ценой (они очень простые), а в том, чтобы найти готовое решение или описание алгоритма в интернете. Я верю, что тут все умные и решат эти задачки десятком способов без всякой математики. Я всего лишь пытался доказать, что отсутствие знаний заставит вас изобретать велосипед, вместо того, чтобы найти готовый алгоритм или ответ.

UPD2. Убейтесь


Для тех, кто считает, что задачи высосаны из пальца:

Если результат решения ваших «прикладных» задач видело больше людей, чем решение этой «высосанной из пальца» задачи — можете собой гордиться.
Tags:
Hubs:
Total votes 172: ↑114 and ↓58+56
Comments212

Articles