Две задачи

[Evgeniy Sklyarevskiy]

вышло сегодня на ИнфоБуме, копирую (без картинки). Особо обращаю внимание преподавателей информатики и любителей программировать - хороший повод для разминки мозга.

Парочка красивых задач


— В моем мире люди умирают, а у меня еще не построен загробный мир! И я не знаю с чего начать!
Петр Бормор, Игры демиургов


Придворные и король с сайта www.travelnews.com.ua/article.php?article=405 Красивые задачи это не те, которые быстро решил, а которые имеют красивое условие, к которым сразу не знаешь с какого конца подступиться. Сам процесс решения приятен и неоднозначен, такие задачи запоминаются, к ним периодически возвращаешься, подбрасываешь их близким друзьям на десерт. Красивые задачи блистают, как жемчужины посреди проходных неинтересных, находка их и рассуждения над ними превращаются в небольшой персональный праздник. Сегодня предлагаю как изысканный деликатес парочку красивых задач.

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

Первая задача необычайной красоты найдена на «Хабрахабре». Король не доверяет своим придворным. Он составил полный список всех придворных и приказал каждому из них следить за кем-нибудь одним из остальных. При этом, первый придворный из списка следит за тем, кто следит за вторым. Второй следит за тем, кто следит за третьим, и так далее. Предпоследний следит за тем, кто следит за последним. Последний следит за тем, кто следит за первым. Вопрос: четное или нечетное число придворных у короля?

Попробуем построить модель для случая из двух придворных. Первый следит за вторым, это противоречит условию, так как первый должен следить за тем, который следит за вторым, то есть, за собой. Для трех придворных все строится идеально — первый за третьим, третий за вторым, второй за первым, все условия соблюдены. Для четырех придворных никак не получается — если первый следит за третьим, то на трех все и замыкается, четвертый лишний. Если первый следит за четвертым, четвертый за вторым… а вот за кем следить второму не ясно, ибо за третьим ни первый, ни четвертый следить не могут, так как уже «при исполнении». Для пятерых участников схема работает только в том случае, если первый следит за четвертым (далее проследите сами). А если первый следит за пятым, пятый за вторым, для второго остается только четвертый (так как второй сам не может следить за третьим), четвертый за третьим… и конец, третий должен следить за пятым, но пятый уже занят. Вообще говоря, легче рисовать диаграммки со связями, чем описывать все словами. Отличное занятие для скучной лекции или официального заседания. Если кто-то напишет всеобъемлющий тракт по теории слежки, то опубликую с удовольствием.

Вторая задача. Напишите число, у которого первая цифра показывает количество единиц в числе, вторая — количество двоек,… десятая — количество нулей в этом числе.

Как задачка? Не правда ли хороша? С чего начать. Если написать, к примеру, десять единиц и начать постепенно приводить число к указанному закону — сколько итераций потребуется? А если с двоек — получим ли тот же самый результат? За то же число итераций? А если написать ряд натуральных чисел — не пойдет ли процесс быстрее? Отличное упражнение для начинающих программистов, можно использовать рекурсию, то есть, функцию, вызывающую самое себя. Кто справится — присылайте листинги программ с распечаткой итераций, забавно видеть, как процесс подбирается к результату.

21.05.2008

[netklon]

Сообщение от Evgeniy Sklyarevskiy

Вторая задача. Напишите число, у которого первая цифра показывает количество единиц в числе, вторая — количество двоек,… десятая — количество нулей в этом числе.

Над этой задачей даже думать не надо. Первое что приходит в голову: 1 000 000 000

[Timur Naimov]

Сообщение от netklon

Над этой задачей даже думать не надо. Первое что приходит в голову: 1 000 000 000

Невернo, т.к. из условия "десятая — количество нулей в этом числе", а их у Вас 9...
Подходит 1 000 001 007

[Timur Salikhov]

Все неправильно поняли..... 2 цифра кол-во двоек, 3 цифра количество троек и тд.....

[Timur Salikhov]

99999999911111111122222222233333333344444444455555 55556666666667777777778888888880
такое будет число

[Игорь Бронников]

Сообщение от Timur Naimov

Невернo, т.к. из условия "десятая — количество нулей в этом числе", а их у Вас 9...
Подходит 1 000 001 007

единиц 2, так что первая должна быть двойка.
Один из правильных ответов есть тут

[Timur Salikhov]

Ссори.. сам не правильно понял.. )
Красиво!

[netklon]

Сообщение от Timur Naimov

Невернo, т.к. из условия "десятая — количество нулей в этом числе", а их у Вас 9...
Подходит 1 000 001 007

Точно. Но ваше тоже не подходит (-;

[Timur Naimov]

По первой задаче ответ - нечетное.

Увидел следующую закономерность (-> обозначает кто за кем следит, т.е. 1->3 значит первый за третьим)

1->3->2->1
1->4->2->5->3->1
1->5->2->6->3->7->4->1
1->6->2->7->3->8->4->9->5->1

Таким образом общий вид можно написать так:
пусть x - массив всех придворных, n - общее количество придворных, а k - индекс предыдущего придворного, тогда решение следующее

x[1] -> x[(n+1)/2+k] -> x[2] -> x[(n+1)/2+k] -> ......... -> x[(n+1)/2] -> x[1].

Т.к. имеем в решении (n+1)/2 - соотвественно число придворных может быть только нечетным.

Поправте если где ошибся...

[Игорь Бронников]

Сообщение от Timur Naimov

По первой задаче ответ - нечетное.

Увидел следующую закономерность (-> обозначает кто за кем следит, т.е. 1->3 значит первый за третьим)

1->3->2->1
1->4->2->5->3->1
1->5->2->6->3->7->4->1
1->6->2->7->3->8->4->9->5->1

Таким образом общий вид можно написать так:
пусть x - массив всех придворных, n - общее количество придворных, а k - индекс предыдущего придворного, тогда решение следующее

x[1] -> x[(n+1)/2+k] -> x[2] -> x[(n+1)/2+k] -> ......... -> x[(n+1)/2] -> x[1].

Т.к. имеем в решении (n+1)/2 - соотвественно число придворных может быть только нечетным.

Поправте если где ошибся...

Вы нашли решение.
Но нет доказательства, что оно единственно возможное...