Алгоритм вычисления значения функции F(n), где n — целое неотрицательное число, задан следующими соотношениями:
F(0) = 0;
F(n) = F(n / 2), если
Сколько существует таких
Приведём аналитическое решение Романа Решетилова :
Докажем, что F(n) - это количество единиц в двоичной записи числа n. По условию, F(0) = 0. F(1) = 1 + F(0) = 1. Предположим, что утверждение верно для любого k-значного в двоичной записи числа с двоичной записью A. Тогда F(A0) = F(A), F(A1) = 1 + F(A). Утверждение доказано.
В промежутке от 1 до 1023 включительно чисел, у которых в точности три единицы в двоичной записи, С(3, 10) = 10!/(3!*7!)=120 (число сочетаний).
Среди чисел от 1001 до 1023 ни одно не содержит в точности три единицы в двоичной записи. Действительно, 24 < 25, поэтому каждое такое число в двоичном виде начинается по крайней мере с пяти единиц.
Приведём решение на языке Python.
k = 0
for n in range(1, 1001):
if bin(n).count('1') == 3:
k += 1
print(k)
Приведём программу на PascalABC, решающую данную задачу:
var n: longint;
i, count: integer;
function F(n: longint): longint;
begin
if n = 0
then F := 0
else if (((n mod 2) = 0) and (n > 0))
then F := F(n div 2)
else if ((n mod 2) <> 0)
then F := 1 + F(n - 1);
end;
begin
count := 0;
for i := 1 to 1000 do
if F(i) = 3 then count := count + 1;
writeln(count);
end.
Результат работы программы — 120.
Ответ: 120.
Приведём другое решение на языке Python.
def f(n):
if n == 0:
return 0
if n > 0 and n % 2 == 0:
return f(n / 2)
if n % 2 != 0:
return 1 + f(n - 1)
k = 0
for n in range(1, 1001):
if f(n) == 3:
k += 1
print(k)
Приведём решение Виктории Зиберовой на языке Python.
f = [0]*1001
for n in range(1,1001):
if n==0:
f[n]=0
if n>0 and n%2==0:
f[n]=f[n//2]
if n%2!=0:
f[n]=1+f[n-1]
print(sum([1 for i in f if i==3]))