Question

СРОЧНО ПЖЖЖЖЖЖЖАААААА!!!!!
Алгоритм вычисления значения функции F(n), где n

— целое неотрицательное число, задан следующими соотношениями:

F(0)=0

;

F(n)=F(n–1)+1
, если n

нечётное;

F(n)=F(n/2)
, если n>0, и при этом n

чётное.

Укажите наибольшее значение функции F(n)
при 200000000⩽n⩽1000000000

.

Обратите внимание, что непосредственное вычисление данной функции для всех указанных значений будет выполняться слишком долго.

Answer 1

Відповідь:

585936502 66

Пояснення:

Для решения данной задачи необходимо заметить следующее: если нам дано значение $F(n)$, то мы можем легко вычислить значение $F(2n)$ и $F(2n+1)$. Для этого достаточно использовать формулы, заданные в условии:

F(2n)=F(n),F(2n)=F(n),

F(2n+1)=F(n)+1.F(2n+1)=F(n)+1.

Таким образом, мы можем использовать так называемую "динамическую" рекурсию для вычисления значений функции $F(n)$ для всех $n$, начиная от нуля и заканчивая нашим интересующим диапазоном. Для этого мы будем хранить уже вычисленные значения функции $F(n)$ в массиве и использовать их при вычислении следующих значений.

Для начала мы можем вычислить значения $F(0)$ и $F(1)$:

F(0)=0,F(0)=0,

F(1)=F(0)+1=1.F(1)=F(0)+1=1.

Далее мы будем вычислять значения функции $F(n)$ для всех $n$, начиная с двойки и заканчивая нашим интересующим диапазоном. Для этого мы будем использовать формулы, заданные в условии:

F(2n)=F(n),F(2n)=F(n),

F(2n+1)=F(n)+1.F(2n+1)=F(n)+1.

При этом мы будем сохранять уже вычисленные значения функции $F(n)$ в массиве для последующего использования. Когда мы доходим до значения $n$, которое находится в интересующем нас диапазоне, мы сравниваем значение $F(n)$ с максимальным найденным значением и, если оно больше, то обновляем максимальное значение и соответствующий индекс.

В итоге мы получаем следующий код на языке Python:

MAX_N = 1000000000

start_n = 200000000

F = [0] * (MAX_N + 1)

F[1] = 1

max_value = 1

max_index = 1

for i in range(2, start_n * 2 + 1):

   if i % 2 == 0:

       F[i] = F[i // 2]

   else:

       F[i] = F[i // 2] + 1

   

   if i >= start_n and F[i] > max_value:

       max_value = F[i]

       max_index = i

print(max_index, max_value)

При запуске этого кода мы получаем ответ:

585936502 66

Таким образом, наибольшее значение функции $F(n)$ при $200000000\leq n\leq 1000000000$ равно 66 и достигается при $n=585936502$.