Задача "Трансфигурация чисел"

[makskovalko]

Помогите решить задачу.

[Abstraction]

Обход дерева вариантов в ширину не работает, что ли?

[makskovalko]

Можете реализовать эту задачу на Паскале?

[Abstraction]

Можете реализовать эту задачу на Паскале?

Нечестно. Я первый спросил.

[makskovalko]

Я не пробовал решать эту задачу через графы. Может, что-то посоветуете?

[BDA]

Да тут хватит односвязного списка для поиска (правда, пока не придумал, как завершить поиск, если нельзя получить такое число).

[Abstraction]

Граф - математическая абстракция. Она не обязательно воплощается в коде напрямую. Например (хотя это неоптимальное решение и может не пройти по времени), можно создать два массива из 1000 целых чисел: первый изначально заполненный значениями -1, кроме A-го элемента, который содержит значение 0; второй изначально заполнен значениями 0. Дальше на каждом шаге мы ищем минимальное положительное значение в первом массиве, такое, что соответствующий элемент во втором массиве равен 0 ("элемент не рассмотрен"), применяем к индексу поочерёдно оба наших преобразования и, если элемент по получившемуся индексу во втором массиве равен 0, пишем туда (значение по исходному индексу + 1); после этого во второй массив по исходному индексу пишем 1 ("элемент рассмотрен").
Если на очередном шаге не нашлось элемента с 0 во втором массиве и положительным значением в первом - поиск закончен; если на очередном шаге мы присвоили какое-то значение элементу с индексом B - поиск опять же закончен.

Для примера (максимум равен 40, A=4, B=5):

1. Выбрали индекс 4 (0,0). Записали по индексу 11 (1,0), по индексу 4 (0,1).
2. Выбрали индекс 11 (1,0). Записали по индексу 32 (2,0), по индексу 1 (2,0), по индексу 11 (1,1).
3. Выбрали индекс 1 (2,0). Записали по индексу 2 (3,0), по индексу 1 (2,1).
4. Выбрали индекс 32 (2,0). Записали по индексу 3 (3,0), по индексу 32 (2,1).
5. Выбрали индекс 2 (3,0). Записали по индексу 5 (4,0), по индексу 2 (3,1).
6. B=5 достижимо за 4 шага.

Попробуйте провести те же рассуждения для B=7.

[s-andriano]

Первое, что я сделал, это задался вопросом: Что такое трансфигурация?
Судя по 5-му предложению, трансфигурацией называется единственное заклинание N -> 3N-1.
Собственно, отсюда алгоритм:
Если число меньше 1000, значит заклинание одно, если больше - ни одного.

[BDA]

s-andriano, ох и любите Вы позаниматься казуистикой.

[s-andriano]

Если я не прав, укажите, в чем?