Две задачи

[Evgeniy Sklyarevskiy]

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


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


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


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

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

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

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

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

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

21.05.2008

[netklon]

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

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

[Timur Naimov]

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

[Timur Salikhov]

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

[Timur Salikhov]

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

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

Над этой задачей даже думать не надо. Первое что приходит в голову: 1 000 000 000
Невернo, т.к. из условия "десятая — количество нулей в этом числе", а их у Вас 9...
Подходит 1 000 001 007 :)
единиц 2, так что первая должна быть двойка.
Один из правильных ответов есть тут (http://fvat.uz/blog/sklyarevskiy/index.php?ELEMENT_ID=295)

[Timur Salikhov]

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

[netklon]

Над этой задачей даже думать не надо. Первое что приходит в голову: 1 000 000 000
Неверн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 - соотвественно число придворных может быть только нечетным.

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

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

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

Увидел следующую закономерность (-> обозначает кто за кем следит, т.е. 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]

Вы нашли решение.
Но нет доказательства, что оно единственно возможное...
Не совсем так - я нашел закономерность, по которой задача решаема, выразил эту закономерность через x,n и пр. ерунду и увидел что только при нечетном количестве придворных закономерность работает :)
Вполне возможно что существуют другие решения.
Можно сказать по другому - не так чтобы прям доказательство, но мысли в продолжении темы:
Из условия задачи следует что между двумя идущими по порядку придворными всегда есть кто-то третий. Между 1 и 2 тот кто следит за 2-м и т.д. Таким образом можно записать так:
x[1] -> ? -> x[2] -> ? -> x[3] -> ..... -> x[1]
Общее количество придворных равно сумме уникальных X-ов и ?-ов в этой записи. Убираем последний x[1] потому что он повторяется, получаем что кол-во X-ов всегда на 1 больше кол-ва ?-ов. Следовательно общее количество это сумма четного и нечетного числа, а это всегда нечетное число.

[Leonid Khrisanfov]

Решил задачку про придворных иначе, рассуждая больше логически.
Первое - из условия понятно, что придворные связаны круговой порукой, то бишь каждый следит за кем-то одним, но и за ним следит кто-то один.
Если не заморачиваться порядком придворных в списке, то схема слежки - это многоугольник, где вершины - придворные, а стороны - слежка. За направление слежки (связи) можно принять движение часовой стрелки.
А вот теперь, нарисуем, например, пятиугольник и пронумеруем его вершины с 1 до 5, начиная с любой из вершин, по часовой стрелке, с пропуском соседней вершины.
И... опа! Все вершины пронумерованы, т.е. условие выполнено.
В развернутом виде выглядит так:
1->4->2->5->3->1


При этом, первый придворный из списка следит за тем, кто следит за вторым. Второй следит за тем, кто следит за третьим, и так далее. Предпоследний следит за тем, кто следит за последним. Последний следит за тем, кто следит за первым.



Если будет квадрат, шестиугольник и проч. "четноугольник", то пронумеровать таким образом все вершины не получится (на половине пути мы вернемся в первую вершину).
Значит любое нечетное от 5-ти и более - будет решением.
На самом деле, мне кажется, что и 3 - тоже годится.
1->3->2->1
Почему 2-ой не может быть предпоследним, а 3-ий, соответственно, последним?
Спасибо ЕС за задачку, а Тимуру за математическое доказательство :)

[Rustam Khamidov]

2100010006

[Evgeniy Sklyarevskiy]

2100010006

Точно. Единственный ли вариант? За сколько итераций находится?

[Rustam Khamidov]

2100010006

Точно. Единственный ли вариант? За сколько итераций находится?

Я сначало неправильно прогу написал (-;
девятки, восьмерки, семерки ... единицы, нули. Для этого случая - единственный.
Итераций не считал, хотя мелкую оптимизацию для глупого перебора делал. Скрипт работал несколько часов (точно не знаю отходил от этого компа).

Для случая
единицы, двойки ... девятки, нули.
Сейчас скрипт переписал и запустил еще раз, чтобы определить время исполнения.

[Evgeniy Sklyarevskiy]

2100010006

Точно. Единственный ли вариант? За сколько итераций находится?

Я сначало неправильно прогу написал (-;
девятки, восьмерки, семерки ... единицы, нули. Для этого случая - единственный.
Итераций не считал, хотя мелкую оптимизацию для глупого перебора делал. Скрипт работал несколько часов (точно не знаю отходил от этого компа).

Для случая
единицы, двойки ... девятки, нули.
Сейчас скрипт переписал и запустил еще раз, чтобы определить время исполнения.

Рустам, хорошо бы иметь листинг процесса приближения... или там очень много строк?

[netklon]

Решение для первой задачи все-таки можно найти и без перебора.

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

Скрипт работал несколько часов (точно не знаю отходил от этого компа).

Видимо алгоритм не очень оптимальный получился.
У меня код на PHP за пару секунд выдал единственный результат

<?
echo "<p>Start</p>";
flush();
for ($a[0]=0; $a[0]<=9; $a[0]++) {
for ($a[1]=0; $a[1]<=10-$a[0]; $a[1]++) {
for ($a[2]=0; $a[2]<=10-($a[0]+$a[1]); $a[2]++) {
for ($a[3]=0; $a[3]<=10-($a[0]+$a[1]+$a[2]); $a[3]++) {
for ($a[4]=0; $a[4]<=10-($a[0]+$a[1]+$a[2]+$a[3]); $a[4]++) {
for ($a[5]=0; $a[5]<=10-($a[0]+$a[1]+$a[2]+$a[3]+$a[4]); $a[5]++) {
for ($a[6]=0; $a[6]<=10-($a[0]+$a[1]+$a[2]+$a[3]+$a[4]+$a[5]); $a[6]++) {
for ($a[7]=0; $a[7]<=10-($a[0]+$a[1]+$a[2]+$a[3]+$a[4]+$a[5]+$a[6]); $a[7]++) {
for ($a[8]=0; $a[8]<=10-($a[0]+$a[1]+$a[2]+$a[3]+$a[4]+$a[5]+$a[6]+$a[7]); $a[8]++) {
for ($a[9]=0; $a[9]<=10-($a[0]+$a[1]+$a[2]+$a[3]+$a[4]+$a[5]+$a[6]+$a[7]+$a[8]); $a[9]++) {
if (array_sum($a)==10) {
for ($i=0; $i<10; $i++)
$sum[$i]=0;
for ($i=0; $i<10; $i++)
@$sum[$a[$i]]++;
$good=true;
for ($i=0; $i<10; $i++)
if ($a[$i]!=$sum[$i])
$good=false;
if ($good) {
echo "<p>", $a[1], $a[2], $a[3], $a[4], $a[5], $a[6], $a[7], $a[8], $a[9], $a[0], "</p>";
flush();
}
}
}
}
}
}
}
}
}
}
}
}
echo "<p>Done</p>";
?>

[German Stimban]

Не удержался, написал программу по второй задаче. Она авторитетно заявила, что среди 10 значных чисел ответ всего один, как и указывал Рустам Хамидов:
2100010006.
На С++ работала минут 5. Просто не занимался оптимизацией алгоритма

[Evgeniy Sklyarevskiy]

Не удержался, написал программу по второй задаче. Она авторитетно заявила, что среди 10 значных чисел ответ всего один, как и указывал neod1n:
2100010006

На каком языке? какой алгоритм? Сколько минут работает?

[German Stimban]

С оптимизацией - 2 секунды.
Язык С++.
Алгоритм такой же, как у Игоря Бронникова

[Djalolatdin Rakhimov]

хоть чемпионат по программированию проводи - кто быстреет напишет алгоритм :)

[Nadir Zaitov]

Вторая задача. Напишите число, у которого первая цифра показывает количество единиц в числе, вторая — количество двоек,… десятая — количество нулей в этом числе.
Задачка кстати решалась и логически:
Сначала нужно заметить, что нулей в числе должно быть больше 4-х. Иначе швах - сумма цифр превысит 10 (общее число цифр).

Раз много нулей, то дальше строим:

1234567890
_________Х

мы знаем, что Х>4, значит Х встречается ровно 1 раз.
Ставим, где-то после "5" 1 единичку, где точно потом разберемся:

1234567890
______1__Х

Значит единичка есть, а значит их не менее двух (в поле 1 не может быть опять "1", так как она ссылалась бы на себя и на Х). Если единиц три и более, то проблема с числом цифр (10). X (минимум 5) у нас уже есть, плюс 3 в поле единиц, плюс три единицы - итого цифр более 11. Следовательно картинка такая:

1234567890
2_____1__Х

Если есть 2, то также не сложно доказать, что двойка тоже одна! картинка такая

1234567890
21____1__Х

Ясно, что больше цифр значащих (отличных от нуля) нет, иначе опять получаем переполнение. следовательно X=10-2-1-1=6 и та условно поставленная единичка стоит на шестом месте. Число единственно и вот оно:

2100010006, что у всех и получилось.

[Igor9669]

А если не учитывать, что число должно быть 10 значным, то еще подойдут:
21000010070
210000010800
2100000019000