Алгоритм вычисления значения функции F(n), где n — целое неотрицательное число, задан следующими соотношениями:
F(0) = 0;
Сколько существует таких чисел n, что
Приведём аналитическое решение Юрия Красильникова.
Функция подсчитывает сумму цифр (или, что то же самое, количество единиц) в двоичной записи числа.
Из условия следует, что требуется найти количество чисел, двоичная запись которых содержит три единицы.
Число 500 в двоичной записи - это 111110100, оно состоит из 9 цифр.
Очевидно, что числа из 9 цифр и большие 500 (т. е. 501-511) содержат более трёх единиц.
Поэтому ответ к задаче - это число сочетаний из 9 по 3: 9 · 8 · 7/(1 · 2 · 3)=84.
Приведём программу на 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 500 do
if F(i) = 3 then count := count + 1;
writeln(count);
end.
Результат работы программы — 84.
Ответ: 84.
Приведём решение на языке Python.
def F(n):
if n == 0:
return 0
if n % 2 == 0 and n > 0:
return F(n // 2)
if n % 2 != 0:
return 1 + F(n - 1)
k = 0
for i in range(1, 501):
if F(i) == 3:
k += 1
print(k)
Приведём решение Юрия Красильникова на языке Python.
print(len([x for x in range(1,501) if bin(x)[2:].count('1')==3]))