TUZ_2-18 Расстояние Коллатца
2.18 Расстояние Коллатца
Имея заданное целое число n, требуется достичь некоторого положительного целого числа с применением формул 3 × n + 1 и n//2, взятых из гипотезы Коллатца. Пусть путь между начальным и конечным числами
start и
goal имеет несколько
слоев, содержащих по нескольку положительных целых чисел.
Первый слой инициализируется начальным числом
start. Все положительные целые числа имеют одинаковое расстояние в каждом слое.
Начиная с начального числа
start для каждого
следующего слоя генерируются числа однократным применением формул 3 × n + 1 и n//2 к каждому числу в предыдущем слое. Создание слоев продолжается, пока в каком-то из них не будет получено искомое число
goal.
Рассмотрим следующий пример. Пусть
start = 10 и
goal = 20. На каждом шаге генерируется несколько положительных целых чисел с одинаковым расстоянием, пока не будет получено число
goal. Поскольку первый (будем считать его нулевым)
слой инициализируется числом
start, в нем имеется только число
10. Далее:
• слой 1: к числу 10 применяются формулы 3 × n + 1 и n//2, и получают- ся два числа (3n + 1) = (3 × 10 + 1) = 31, (n//2) = (10//2) = 5;
• слой 2: к числам 31 и 5 применяются те же формулы, и получаются четыре числа (3 × 31 + 1) = 94, (3 × 5 + 1) = 16, (31//2) = 15, (5//2) = 2;
• слой 3: 283, 49, 46, 7, 47, 8, 7, 1;
• слой 4: 850, 148, 139, 22, 142, 25, 22, 4, 141, 24, 23, 3, 23, 4, 3, 0;
• слой 5: 2551, 445, 418, 67, 427, 76, 67, 13, 424, 73, 70, 10, 70, …;
• слой 6: 7654, 1336, 1255, 202, 1282, 229, 202, 40, …;
• слой 7: 22963, 4009, 3766, …, 20…
Как видите, в слое 7 обнаружилось целевое число 20.
Ваша задача: написать функцию, которая принимает начальное и конечное числа и возвращает номер слоя, в котором присутствует целевое число.
В табл. 2.18 показаны ожидаемые результаты для некоторых входных данных.
| Таблица 2.18. Некоторые ожидаемые результаты для задачи поиска целевого числа на основе расстояния Коллатца |
| Start, goal |
Ожидаемый результат |
| 20, 321 |
9 |
| 22, 15 |
8 |
| 4, 7 |
2 |
| 10, 20 |
7 |