Horn писал(а):Что-то темка заглохла, надо поправить.
Я вообще-то в алгоритмах не спец, а тут понадобилось добыть несколько задач по алгоритмизации для студентов-вечерников (второе высшее). Поскольку книжки нет под рукой, в инете копаться времени жалко, решил насочинять сам.

Вот одна из тех, что придумались:
Домино.
a) Написать функцию, проверяющую, можно ли из нескольких доминошек (массив на входе) составить цепочку, прикладывая их друг к другу одинаковыми числами.
b) Написать процедуру, которая распечатывает эту цепочку (если она есть). Пример:
(4,5) — (5,1) — (1,1) — (1,3) — (3,5) — (5,6) — (6,0)
Поначалу мне эта задача показалась тривиальной. Но после выдачи ее студентам ("до того" - не мой стиль

) стал думать, а как же ее объяснять... оказалось не все так просто. Потом даже нашел ее в списке задач какой-то олимпиады по программированию. Тем не менее я ее решил, можете и вы попробовать.

Не уверен, что это математика, и тем не менее.
Рассмотрим граф, где числа от 0 до 6 - вершины. А доминошки которые у нас есть - ребра (тут можно и одинаковые использовать). Тогда их можно сложить в цепочку если есть Эйлеров путь. А критерий этого простой.
1. Граф без пустых вершин связный.
2. Количество вершин нечетной степени не более двух. (В случае менее двух даже Эйлеров цикл есть).
Это проверятеся очень легко

Далее алгоритм построения цепочки.
1. Берем вершину нечетной степени (если нет - любую) и идем по ребрам графа пока можно. В итоге мы упремся во вторую вершину нечетной степени (или вернемся в исходную).
2. Теперь берем любое не взятое ребро (из вершины, через которую уже проходили) и идем как в пункте 1. В итоге прийдем в себя же. Склеиваем этот цикл с нашим путем (что нетрудно вставляя в соответствующееся место цепочки этот цикл).
3. Повторяем операцию два, пока есть ребра.
Получили довольно простой линейный алгоритм (при правильной реализации) от числа доминошек.