Question

Алгоритм вычисления значения функции 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.

Answer 1

Ответ:

(см. объяснение)

Объяснение:

Если решать задачу в лоб, то можно написать программу, скажем на паскале, которая у меня выполнялась 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 получаете ответ.

Но это топорный алгоритм и при решении задачи в реальной жизни такой подход применять строго противопоказано.

Более того, настоятельно рекомендовано Вам попробовать самостоятельно увидеть изюминку этого номера.

Задание выполнено!

Answer 2

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

Описание алгоритма:

1. Если n = 0, то значение функции F(n) равно 0.

2. Если n нечетное (n % 2 != 0), то значение функции F(n) равно F(n-1) + 1.

3. Если n четное (n % 2 == 0), то значение функции F(n) равно F(n/2).

Пример работы алгоритма:

Давайте рассмотрим пример для n = 6:

1. n = 6 четное, поэтому значение F(6) равно F(6/2) = F(3).

2. n = 3 нечетное, поэтому значение F(3) равно F(3-1) + 1 = F(2) + 1.

3. n = 2 четное, поэтому значение F(2) равно F(2/2) = F(1).

4. n = 1 нечетное, поэтому значение F(1) равно F(1-1) + 1 = F(0) + 1.

5. n = 0, поэтому значение F(0) равно 0.

Таким образом, F(6) = F(3) = F(2) + 1 = F(1) + 1 = F(0) + 1 + 1 = 0 + 1 + 1 = 2.

Подсчет количества значений n, для которых F(n) = 2:

Для подсчета количества значений n, для которых F(n) = 2, мы можем использовать цикл и проверять каждое значение n от 0 до 1 000 000 000.

count = 0

for n in range(1, 1000000000):
    if F(n) == 2:
        count += 1

print(count)

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

Более эффективный подход:

Заметим, что значение F(n) может быть равно 2 только в двух случаях:

1. Если n = 2, тогда F(n) = F(2) = F(2/2) = F(1) = F(1-1) + 1 = F(0) + 1 = 0 + 1 = 1.

2. Если n = 3, тогда F(n) = F(3) = F(3-1) + 1 = F(2) + 1 = F(2/2) + 1 = F(1) + 1 = F(1-1) + 1 + 1 = F(0) + 1 + 1 = 0 + 1 + 1 = 2.

Таким образом, единственным значением n, для которого F(n) = 2, является n = 3.

Ответ:

Количество значений n < 1 000 000 000, для которых F(n) = 2, равно 1.