|
|
Арбузный ломтик по средам № 167
Парочка красивых задач
| |
— В моем мире люди умирают, а у меня еще не построен загробный мир! И я не знаю с чего начать!
Петр Бормор, Игры демиургов |
Красивые задачи это не те, которые быстро решил, а которые имеют красивое условие, к которым сразу не знаешь с какого конца подступиться. Сам процесс решения приятен и неоднозначен, такие задачи запоминаются, к ним периодически возвращаешься, подбрасываешь их близким друзьям на десерт. Красивые задачи блистают, как жемчужины посреди проходных неинтересных, находка их и рассуждения над ними превращаются в небольшой персональный праздник. Сегодня предлагаю как изысканный деликатес парочку красивых задач.
Если среди читателей есть программисты — будущие, настоящие, несостоявшиеся, хороший повод размяться. Подумайте, как бы вы решали эти задачи на любимом языке программирования — какие переменные, какие циклы, как организовать проверку условия и еще много чего для размышления. Итак, поехали.
Первая задача необычайной красоты найдена на «Хабрахабре». Король не доверяет своим придворным. Он составил полный список всех придворных и приказал каждому из них следить за кем-нибудь одним из остальных. При этом, первый придворный из списка следит за тем, кто следит за вторым. Второй следит за тем, кто следит за третьим, и так далее. Предпоследний следит за тем, кто следит за последним. Последний следит за тем, кто следит за первым. Вопрос: четное или нечетное число придворных у короля?
Попробуем построить модель для случая из двух придворных. Первый следит за вторым, это противоречит условию, так как первый должен следить за тем, который следит за вторым, то есть, за собой. Для трех придворных все строится идеально — первый за третьим, третий за вторым, второй за первым, все условия соблюдены. Для четырех придворных никак не получается — если первый следит за третьим, то на трех все и замыкается, четвертый лишний. Если первый следит за четвертым, четвертый за вторым… а вот за кем следить второму не ясно, ибо за третьим ни первый, ни четвертый следить не могут, так как уже «при исполнении». Для пятерых участников схема работает только в том случае, если первый следит за четвертым (далее проследите сами). А если первый следит за пятым, пятый за вторым, для второго остается только четвертый (так как второй сам не может следить за третьим), четвертый за третьим… и конец, третий должен следить за пятым, но пятый уже занят. Вообще говоря, легче рисовать диаграммки со связями, чем описывать все словами. Отличное занятие для скучной лекции или официального заседания. Если кто-то напишет всеобъемлющий тракт по теории слежки, то опубликую с удовольствием.
Вторая задача. Напишите число, у которого первая цифра показывает количество единиц в числе, вторая — количество двоек,… десятая — количество нулей в этом числе.
Как задачка? Не правда ли хороша? С чего начать. Если написать, к примеру, десять единиц и начать постепенно приводить число к указанному закону — сколько итераций потребуется? А если с двоек — получим ли тот же самый результат? За то же число итераций? А если написать ряд натуральных чисел — не пойдет ли процесс быстрее? Отличное упражнение для начинающих программистов, можно использовать рекурсию, то есть, функцию, вызывающую самое себя. Кто справится — присылайте листинги программ с распечаткой итераций, забавно видеть, как процесс подбирается к результату.
21.05.2008
Теги: задачки
|
Ваш отзыв автору
|
|
|
