Предмет: Информатика, автор: onetwo1984

"Задача 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 включительно. Для каждого теста три числа следует выводить в отдельной строке, разделяя одним пробелом."

Помогите , Хелп , срочно
ЯЗЫК СИ


Леганда555: Ого, а эту задачу нужно в систему посылать? На первый взгляд числа тут очень большие, так ещё и несколько тестов, за секунду вряд ли уложиться можно
Леганда555: В общем - у задачи есть ограничения по времени работы?
onetwo1984: Лимит времени 1 секунда

Лимит использования памяти 128 MiB
Леганда555: эх, всё же 1 секунда... а на каком языке нужно решение?
onetwo1984: язык си

Ответы

Автор ответа: Леганда555
1

#include <stdio.h>

int cycle_length(int n) {

   int cnt;

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

       if (n % 2)

           n = 3 * n + 1;

       else

           n = n / 2;

       return cnt;

}

int check(int i, int j) {

   int mx = 0;

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

       int h = cycle_length(i);

       if (mx < h)

           mx = h;

   }

   return mx;

}

int main() {

   int i, j;

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

       int tmp, itemp = i, jtemp = j;

       if (i > j) {

           tmp = i;

           i = j;

           j = tmp;

       }

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

   }

   return 0;

}

Похожие вопросы
Предмет: Қазақ тiлi, автор: Никита111111111114
Предмет: Окружающий мир, автор: bysamysa