Алгоритм вычисления значения функции F(n), где n – целое неотрицательное число, задан следующими соотношениями:
F(0) = 0;
F(n) = F(n – 1) + 1, если n нечётно;
F(n) = F(n/2), если n > 0 и при этом n чётно.
Укажите количество таких значений n < 1 000 000 000, для которых F(n) = 2.
Ответы
Ответ:
(см. объяснение)
Объяснение:
Если решать задачу в лоб, то можно написать программу, скажем на паскале, которая у меня выполнялась 10 минут.
##
function F(n: integer): integer;
begin
if (n = 0)
then F:= 0
else if (n mod 2 > 0)
then F:= F(n - 1) + 1
else F:= F(n div 2)
end;
var k:= 0;
var n:= 1;
loop 1000000000 do
begin
if (F(n) = 2)
then k += 1;
inc(n);
end;
print(k);
Результат ее работы: 435.
Если при решении задачи можно использовать компьютер, то тогда просто пишете этот код за 5 секунд и идете решать другие номера, для которых компьютер не требуется. Далее минут через 10-15 получаете ответ.
Но это топорный алгоритм и при решении задачи в реальной жизни такой подход применять строго противопоказано.
Более того, настоятельно рекомендовано Вам попробовать самостоятельно увидеть изюминку этого номера.
Задание выполнено!
Интересный факт: было подсчитано, что при решении некоторых задач питон оказался более чем в 100 раз медленнее, чем язык СИ++.
Вообще говоря, на паскале, как я уже писал выше у меня ответ считался 10 минут, на СИ я получил его за 5 минут, а на питоне за 40 минут. Но я Вам написал решение на паскале, так как не думаю, что вы поймете что-то такое:
int f(int n) {
return (n == 0) ? 0 : (n % 2 > 0) ? f(n - 1) + 1 : f(n / 2);
}
int main() {
int k = 0;
for (int i = 0; i < 1000000000; ++i) {
if (f(i) == 2) {
++k;
}
}
printf("%i", k);
return(0);
}