419. Задача 3n + 1

Рассмотрим следующий алгоритм генерации последовательности чисел:

1. input n

2. print n

3. if n = 1 then STOP

4. if n is odd then n = 3 * n + 1

5. else n = n / 2

6. GOTO 2

Например, для n = 22 будет сгенерирована следующая последовательность чисел:

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Полагают (но это еще не доказано), что этот алгоритм сойдется к n = 1 для любого целого n. По крайней мере, это предположение верно для всех целых n, для которых 0 < n < 1,000,000.

Длиной цикла числа n будем называть количество сгенерированных чисел в последовательности включая 1. В приведенном примере длина цикла числа 22 равна 16.

Для двух заданных чисел i и j необходимо найти максимальную длину цикла среди всех чисел между i и j включительно.

Вход. Каждый тест задается в отдельной строке и содержит пару целых чисел i и j. Входные числа будут меньше 1000000 и больше 0. Считайте, что для вычислений достаточно использовать 32 битный целочисленный тип.

Выход. Для каждой пары чисел i и j выведите числа i и j в том же порядке, в каком они поступили на вход. После чего выведите максимальную длину цикла среди всех целых чисел между i и j включительно. Для каждого теста три числа следует выводить в отдельной строке, разделяя одним пробелом.

Пример входа	Пример выхода
1 10 100 200 201 210 900 1000	1 10 20 100 200 125 201 210 89 900 1000 174

РЕШЕНИЕ

циклы

Анализ алгоритма

Напишем функцию cycle_length, которая вычисляет длину цикла числа n. Затем для каждого значения от i до j включительно простым перебором вычисляем длину цикла. Выводим длину максимального цикла.

Реализация алгоритма

Функция cycle_length вычисляет длину цикла числа n. Генерируем последовательность пока не дойдем до 1 и подсчитываем ее длину в переменной cnt.

int cycle_length(int n)

{

int cnt;

for(cnt = 1; n != 1; cnt++)

n = (n % 2) ? 3 * n + 1: n / 2;

return cnt;

}

Функция check вычисляет длину максимального цикла для чисел от i до j простым перебором.

int check(int i,int j)

{

int mx = 0;

for(; i <= j; i++)

mx = max (mx, cycle_length(i));

return mx;

}

Основная часть программы. Читаем входные данные. Входное значение i может быть больше j, в таком случае следует поменять i и j местами. Вычисляем и выводим максимальную длину цикла.

while (scanf("%d %d",&i,&j) == 2)

{

itemp = i; jtemp = j;

if (i > j) tmp = i, i = j, j = tmp;

printf("%d %d %d\n",itemp, jtemp, check(i,j));

}