СРОЧНО ЯЗЫК С++ ОСТАЛСЯ ЧАС ДАЮ 60 БАЛЛОВ
Алгоритм вычисления значения функции F(n)
, где n
— целое неотрицательное число, задан следующими соотношениями:
F(0)=0
;
F(n)=F(n–1)+1
, если n
нечётное;
F(n)=F(n/2)
, если n>0
, и при этом n
чётное.
Укажите наибольшее n
в диапазоне 600000000⩽n⩽1500000000
, при котором значение функции F(n)
максимально.
Обратите внимание, что непосредственное вычисление данной функции для всех указанных значений будет выполняться слишком долго.
Ответы
Для решения данной задачи можно воспользоваться динамическим программированием. Создадим массив F размера 1500000001 и заполним его значениями F(0)=0 и F(1)=1. Затем пройдемся по всем четным значениям i от 2 до 1500000000 и заполним соответствующие значения массива F по формуле F(i) = F(i/2). Далее пройдемся по всем нечетным значениям i от 3 до 1500000000 и заполним соответствующие значения массива F по формуле F(i) = F(i-1) + 1.
Таким образом, мы заполним массив F снизу вверх, и значение F(n) для любого n в указанном диапазоне будет вычисляться за O(1) времени.
Остается найти максимальное значение F(n) и соответствующее ему значение n в заданном диапазоне. Для этого можно пройтись по всем значениям n в диапазоне 600000000 <= n <= 1500000000 и сохранить максимальное значение F(n) и соответствующее ему значение n. Это также займет O(1) времени для каждого n, и общее время выполнения будет O(N), где N = 900000001.
Ниже приведен код на C++, который реализует описанный алгоритм:
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<long long> F(1500000001);
F[0] = 0;
F[1] = 1;
// заполнение массива F
for (long long i = 2; i <= 1500000000; i += 2) {
F[i] = F[i/2];
}
for (long long i = 3; i <= 1500000000; i += 2) {
F[i] = F[i-1] + 1;
}
// поиск максимального значения F(n) в заданном диапазоне
long long max_val = 0;
long long max_n = 0;
for (long long n = 600000000; n <= 1500000000; n++) {
if (F[n] > max_val) {
max_val = F[n];
max_n = n;
}
}
cout << max_n << endl; // выводим значение n, при котором F(n) максимально
return 0;
}
Обратите внимание, что данное решение может занять значительное количество памяти, т.к. мы создаем массив размера 1500000001. Если память ограничена, можно использовать более сложные алгоритмы для вычисления значения F(n) без предварительного заполнения массива.