Задания
Версия для печати и копирования в MS Word
Тип 16 № 46974
i

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

Спрятать решение

Ре­ше­ние.

За­ме­тим, что дан­ная ре­кур­сив­ная функ­ция фак­ти­че­ски под­счи­ты­ва­ет ко­ли­че­ство еди­ниц в числе n в дво­ич­ном виде. Тогда не­об­хо­ди­мо найти ко­ли­че­ство чисел в за­дан­ном диа­па­зо­не, ко­то­рые в дво­ич­ном виде имеют толь­ко две цифры 1. То есть под­хо­дят числа вида 11, 101, 110, 1001, 1010, 1100 и так далее. За­ме­тим также, что ко­ли­че­ство ис­ко­мых чисел среди чисел, ко­то­рые в дво­ич­ном виде со­сто­ит из двух зна­ков, равно 1, среди чисел, со­сто­я­щих в дво­ич­ном виде из трёх зна­ков, равно 2, а среди чисел, со­сто­я­щих в дво­ич­ном виде из четырёх зна­ков, равно 3 и так далее.

Число 1 000 000 000 в дво­ич­ном виде имеет 30 зна­ков. Мак­си­маль­ное под­хо­дя­щее число, для ко­то­ро­го F(n)  =  2 и со­сто­я­щее в дво­ич­ном виде из 30 зна­ков,  — 1100..002  =  805 306 36810, что мень­ше гра­ни­цы за­дан­но­го диа­па­зо­на. Зна­чит, чтобы под­счи­тать ко­ли­че­ство под­хо­дя­щих чисел n, име­ю­щих в дво­ич­ном виде от 1 до 30 зна­ков, и про­сум­ми­ро­вать ко­ли­че­ство най­ден­ных чисел для каж­дой раз­ряд­но­сти, вос­поль­зу­ем­ся язы­ком PascalABC:

var sum: integer;

i: integer;

begin

for i := 2 to 30 do

sum := sum + i - 1;

writeln(sum);

end.

 

Ре­зуль­тат ра­бо­ты про­грам­мы  — 435.

 

Ответ: 435.

 

При­ведём ре­ше­ние на языке Python.

За­ме­тим, что дан­ная ре­кур­сив­ная функ­ция фак­ти­че­ски под­счи­ты­ва­ет ко­ли­че­ство еди­ниц в числе n в дво­ич­ном виде. Тогда не­об­хо­ди­мо найти ко­ли­че­ство чисел в за­дан­ном диа­па­зо­не, ко­то­рые в дво­ич­ном виде имеют толь­ко две цифры 1. То есть под­хо­дят числа вида 11, 101, 110, 1001, 1010, 1100 и так далее. За­ме­тим также, что ко­ли­че­ство ис­ко­мых чисел среди чисел, ко­то­рые в дво­ич­ном виде со­сто­ит из двух зна­ков, равно 1, среди чисел, со­сто­я­щих в дво­ич­ном виде из трёх зна­ков, равно 2, а среди чисел, со­сто­я­щих в дво­ич­ном виде из четырёх зна­ков, равно 3, и так далее.

Число 1 000 000 000 в дво­ич­ном виде имеет 30 зна­ков. Мак­си­маль­ное под­хо­дя­щее число, для ко­то­ро­го F(n)  =  2 и со­сто­я­щее в дво­ич­ном виде из 30 зна­ков,  — 1100..002  =  805 306 36810, что мень­ше гра­ни­цы за­дан­но­го диа­па­зо­на. Зна­чит, чтобы под­счи­тать ко­ли­че­ство под­хо­дя­щих чисел n, име­ю­щих в дво­ич­ном виде от 1 до 30 зна­ков, и про­сум­ми­ро­вать ко­ли­че­ство най­ден­ных чисел для каж­дой раз­ряд­но­сти, вос­поль­зу­ем­ся язы­ком Python:

k = 0

for i in range(2, 31):

k = k + i - 1

print(k)

 

При­ведём дру­гое ре­ше­ние.

За­ме­тим, что дан­ная ре­кур­сив­ная функ­ция фак­ти­че­ски под­счи­ты­ва­ет ко­ли­че­ство еди­ниц в числе n в дво­ич­ном виде. Тогда не­об­хо­ди­мо найти ко­ли­че­ство чисел в за­дан­ном диа­па­зо­не, ко­то­рые в дво­ич­ном виде имеют толь­ко две цифры 1. То есть под­хо­дят числа вида 11, 101, 110, 1001, 1010, 1100 и так далее. Число 1 000 000 000 в дво­ич­ном виде имеет 30 зна­ков. То есть не­об­хо­ди­мо раз­ме­стить две еди­ни­цы среди 30 по­зи­ций всеми воз­мож­ны­ми спо­со­ба­ми. Вос­поль­зу­ем­ся фор­му­лой вы­чис­ле­ния со­че­та­ний из 30 по­зи­ций по 2:

дробь: чис­ли­тель: 30!, зна­ме­на­тель: 28! умно­жить на 2! конец дроби = дробь: чис­ли­тель: 29 умно­жить на 30, зна­ме­на­тель: 2 конец дроби =435.

 

При­ве­дем ре­ше­ние Бо­ри­са Са­ве­лье­ва на языке Python.

cnt=0

for i in range (1,100):

for j in range (0,i):

if (2**i+2**j) < 1000000000:

cnt += 1

print(cnt)


Аналоги к заданию № 46974: 47013 Все

Спрятать решение · Помощь


О про­ек­те · Ре­дак­ция · Пра­во­вая ин­фор­ма­ция · О ре­кла­ме
© Гущин Д. Д., 2011—2026