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

Відповідь:

Для вычисления значения функции F(n) в заданном диапазоне необходимо использовать динамическое программирование. Создадим массив dp размером (n+1), где dp[i] будет хранить значение функции F(i).

Инициализируем dp[0]=0. Затем перебираем числа от 1 до n в цикле и вычисляем значения функции F для каждого числа. Если число четное, то используем формулу F(n)=F(n/2), если нечетное - формулу F(n)=F(n–1)+1. Значения функции сохраняем в массиве dp.

После завершения цикла, максимальное значение функции F(n) находится в ячейке dp[max_n], где max_n - максимальное число в заданном диапазоне.

Реализация на Python:

def find_max_F(n):

   dp = [0] * (n+1)

   for i in range(1, n+1):

       if i % 2 == 0:

           dp[i] = dp[i//2]

       else:

           dp[i] = dp[i-1] + 1

   return max(dp[200000000:n+1])

max_F = find_max_F(1000000000)

print(max_F)

В результате выполнения этого кода мы получим наибольшее значение функции F(n) в заданном диапазоне, которое соответствует максимальному элементу массива dp от 200000000 до 1000000000.