Рекурсия с возвратом. Рекурсия с возвратом

• Название: Рекурсия с возвратом
• Дата: 05.07.2022
• Размер: 16.01 Kb.
• Имя файла: Рекурсия с возвратом.docx
• Тип: Документы; #624855

Рекурсия с возвратом

1. 
   Реализуйте рекурсивный алгоритм, позволяющий получать все перестановки чисел от 1 до n по одному разу.
   
2. 
   Реализуйте рекурсивный алгоритм, позволяющий получать все возрастающие последовательности длины m, элементами которых являются натуральные числа от 1 до n (m ≤ n).
   
3. 
   Реализуйте рекурсивный алгоритм, позволяющий получать все представления положительного целого числа n в виде суммы последовательных невозрастающих целых положительных слагаемых.
   
4. 
   Дана доска n x n. Конь, который ходит согласно шахматным правилам, помещается на поле с начальными координатами х0, у0. Реализуйте рекурсивный алгоритм, позволяющий покрыть всю доску ходами коня, т.е. вычислить обход доски (если он существует), из n²-1 ходов так, чтобы каждое поле посещается ровно один раз.
   
5. 
   Реализуйте рекурсивный алгоритм, позволяющий получить все расстановки 8 ладей на шахматной доске, при которых ни одна ладья не угрожает другой.
   
6. 
   Реализуйте рекурсивный алгоритм, позволяющий найти такую расстановку пяти ферзей на шахматной доске, при которой каждое поле будет находиться под ударом одного из них.
   
7. 
   Имеется n предметов, веса которых равны А₁, А₂, … , А_n. Реализуйте рекурсивный алгоритм, позволяющий разделить эти предметы на две группы так, чтобы общие веса групп были максимально близки.
   
8. 
   В трехмерном пространстве задано множество точек. Реализуйте рекурсивный алгоритм, позволяющий найти разбиение этого множества на два непустых непересекающихся множества, чтобы их центры тяжести находились как можно ближе друг к другу.
   
9. 
   Дан набор слов. Реализуйте рекурсивный алгоритм, позволяющий составить из них цепочку максимальной длины по количеству слов (или по количеству букв). Цепочка образуется, если первая буква следующего слова совпадает с последней буквой предыдущего слова. Повторно использовать слова нельзя.
   
10. 
    Реализуйте рекурсивный алгоритм, позволяющий построить такой многоугольник (не обязательно выпуклый) с вершинами в заданном множестве, периметр которого максимален.
    
11. 
    Реализуйте рекурсивный алгоритм, позволяющий найти минимальное множество прямых, на которых можно разместить все точки заданного множества.
    
12. 
    По двум конвейерам двигаются молочные бутылки. Для каждой бутылки известно время заполнения и закупоривания. Реализуйте рекурсивный алгоритм, позволяющий найти расстановку бутылок по конвейерам, при которой время обработки будет минимальным.
    
13. 
    У игрока имеется набор костей домино (не обязательно полный). Реализуйте рекурсивный алгоритм, позволяющий найти последовательность выкладывания этих костей таким образом, чтобы получившаяся в результате цепочка была максимальной длины.
    
14. 
    Задача о рюкзаке. Имеется n предметов, пронумерованных числами от 0 до n-1, для каждого из которых известен набор масс m₀,...,m_n-1 и набор стоимостей s₀,...,s_n-1. Определите, какой набор предметов необходимо положить в рюкзак, чтобы его масса не превышала Q, а стоимость предметов была бы наибольшей.
    
15. 
    Из 92 решений задачи 6 только 12 по существу различны. Все остальные решения можно получить с помощью осевой или центральной симметрии. Реализуйте рекурсивный алгоритм, позволяющий находить именно эти 12 решений. Обратите внимание, что поиск на первой вертикали можно ограничить позициями 1 - 4.