ПРОШУ ОЧЕНЬ СРОЧНО!!!ПАМАГИТЕ!!!ПЖЖЖЖЖЖ!!!!!!
Алгоритм вычисления значения функции 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
.
Обратите внимание, что непосредственное вычисление данной функции для всех указанных значений будет выполняться слишком долго.
Алгоритм вычисления значения функции 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
.
Обратите внимание, что непосредственное вычисление данной функции для всех указанных значений будет выполняться слишком долго.
More Questions From This User See All
Answers & Comments
Відповідь:
Для вычисления значения функции 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.