Задача
Рассмотрим следующий алгоритм генерации последовательности чисел:
|
1 2 3 4 5 6 |
input n print n if n = 1 then STOP if n is odd then n = 3 * n + 1 else n = n / 2 GOTO 2 |
Например, для [latex]n = 22[/latex] будет сгенерирована следующая последовательность чисел:
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
Полагают (но это еще не доказано), что этот алгоритм сойдется к [latex]n = 1[/latex] для любого целого [latex]n[/latex]. По крайней мере, это предположение верно для всех целых [latex]n[/latex], для которых [latex]0 < n < 1,000,000[/latex].
Длиной цикла числа [latex]n[/latex] будем называть количество сгенерированных чисел в последовательности включая [latex]1[/latex]. В приведенном примере длина цикла числа [latex]22[/latex] равна [latex]16[/latex].
Для двух заданных чисел [latex]i[/latex] и [latex]j[/latex] необходимо найти максимальную длину цикла среди всех чисел между [latex]i[/latex] и [latex]j[/latex] включительно.
Входные данные
Каждый тест задается в отдельной строке и содержит пару целых чисел [latex]i[/latex] и [latex]j[/latex]. Входные числа будут меньше [latex]1000000[/latex] и больше [latex]0[/latex]. Считайте, что для вычислений достаточно использовать [latex]32[/latex] битный целочисленный тип.
Выходные данные
Для каждой пары чисел [latex]i[/latex] и [latex]j[/latex] выведите числа [latex]i[/latex] и [latex]j[/latex] в том же порядке, в каком они поступили на вход. После чего выведите максимальную длину цикла среди всех целых чисел между [latex]i[/latex] и [latex]j[/latex] включительно. Для каждого теста три числа следует выводить в отдельной строке, разделяя одним пробелом.
Тесты
| Входные данные | Выходные данные |
|---|---|
| 1 10 100 200 201 210 900 1000 |
1 10 20 100 200 125 201 210 89 900 1000 174 |
| 1 10 10 1 |
1 10 20 10 1 20 |
| 5 25 70 54 38 250 |
5 25 24 70 54 113 38 250 128 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
import java.util.*; import java.lang.*; import java.io.*; import static java.lang.Math.*; class Main { public static void main (String[] args) throws java.lang.Exception { int i, j, ait; Scanner scan = new Scanner(System.in); while(scan.hasNext()) { i = scan.nextInt(); j = scan.nextInt(); int it, maxIt; maxIt = 0; for (int a = min(i, j); a <= max(i, j); a++) { it = 1; ait = a; while(ait != 1){ if(ait % 2 == 1){ ait = ait * 3 + 1; } else{ ait = ait / 2; } it++; } if (it > maxIt) { maxIt = it; } } System.out.println(i + " " + j + " " + maxIt); } } } |
Решение
Алгоритм, описанный в условии задачи используется для построения сиракузской последовательности. Интересный факт — какое бы число не взять, в конце получаем единицу. Нам же надо посчитать сколько раз должен сработать алгоритм для подсчитывания «длины цикла». Считывая пару чисел из потока ввода я высчитывал «длину цикла» для каждого числа из заданного введенной парой промежутка. После чего сравнивал количество итераций для каждого такого числа и находил максимальное. И так для каждой пары чисел.