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

Ал­го­ритм по­лу­ча­ет на вход на­ту­раль­ное число N > 1 и стро­ит по нему новое число R сле­ду­ю­щим об­ра­зом:

1.  Стро­ит­ся дво­ич­ная за­пись числа N.

2.  Вы­чис­ля­ет­ся ко­ли­че­ство еди­ниц, сто­я­щих на чётных ме­стах в дво­ич­ной за­пи­си числа N без ве­ду­щих нулей, и ко­ли­че­ство нулей, сто­я­щих на нечётных ме­стах. Места от­счи­ты­ва­ют­ся слева на­пра­во (от стар­ших раз­ря­дов к млад­шим, на­чи­ная с еди­ни­цы).

3.  Ре­зуль­та­том ра­бо­ты ал­го­рит­ма ста­но­вит­ся мо­дуль раз­но­сти по­лу­чен­ных двух чисел.

 

При­мер. Дано число N  =  39. Ал­го­ритм ра­бо­та­ет сле­ду­ю­щим об­ра­зом:

1.  Стро­ит­ся дво­ич­ная за­пись: 3910  =  1001112.

2.  Вы­де­ля­ем еди­ни­цы на чётных и нули на нечётных ме­стах: 100111. На чётных ме­стах стоят две еди­ни­цы, на нечётных  — один ноль.

3.  Мо­дуль раз­но­сти равен 1.

Ре­зуль­тат ра­бо­ты ал­го­рит­ма R  =  1.

 

При каком наи­мень­шем N в ре­зуль­та­те ра­бо­ты ал­го­рит­ма по­лу­чит­ся R  =  5?

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

Ре­ше­ние.

Чтобы мо­дуль раз­но­сти был равен 5, в дво­ич­ной за­пи­си ис­ко­мо­го числа долж­но быть не менее де­вя­ти зна­ков. Пусть зна­ков ровно де­вять, тогда на всех не­чет­ных ме­стах долж­ны быть нули (всего 5 нулей), и на всех че­ты­рех чет­ных ме­стах также стоят нули (то есть 0 еди­ниц на этих ме­стах). Раз­ность 5 и 0 равна пяти, но по усло­вию число, за­пи­сан­ное од­ни­ми ну­ля­ми, не под­хо­дит. Пусть в дво­ич­ной за­пи­си 10 зна­ков, на пер­вом (не­чет­ном) месте стоит 1. Тогда под­хо­дит число, за­пи­сан­ное од­ни­ми еди­ни­ца­ми: в нем на пять еди­ниц на не­чет­ных ме­стах (по­лу­ча­ем число 5) и нет нулей на не­чет­ных ме­стах (по­лу­ча­ем число 0). Оста­лось за­ме­тить, что 11111111112  =  102310.

 

Ответ: 1023.

 

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

for n in range(2, 10000):

s = bin(n)[2:] # пе­ре­вод в дво­ич­ную си­сте­му

s = str(s)

sum_one = 0

sum_zero = 0

for i in range(len(s)):

if i % 2 != 0 and s[i] == "1":

sum_one += 1

elif i % 2 == 0 and s[i] == "0":

sum_zero += 1

if abs(sum_one - sum_zero) == 5:

print(n)

break

 

При­ме­ча­ние 1.

Об­ра­ща­ем вни­ма­ние чи­та­те­лей, что в про­грам­ме умыш­лен­но вы­чис­ля­ет­ся ко­ли­че­ство еди­ниц, сто­я­щих на НЕчётных ме­стах в дво­ич­ной за­пи­си числа N без ве­ду­щих нулей, и ко­ли­че­ство нулей, сто­я­щих на Чётных ме­стах, в про­ти­во­вес за­да­нию. Свя­за­но это с тем, что в за­да­нии счет цифр в числе ведут с пер­вой по­зи­ции, а в языке Python  — с ну­ле­вой по­зи­ции.

 

При­ме­ча­ние 2.

Об­ра­ща­ем вни­ма­ние чи­та­те­лей, что число 511 не под­хо­дит. Во-пер­вых, это сразу сле­ду­ет из при­ве­ден­но­го выше тек­сто­во­го ре­ше­ния. Если вы еще не про­чли его  — про­чти­те. Во-вто­рых, по­нят­но, что в дво­ич­ном числе из де­вя­ти еди­ниц 1111111112 стоят 4 еди­ни­цы на чет­ных по­зи­ци­ях и 0 нулей на не­чет­ных, но 4 − 0  =  4, а не 5.


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