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

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

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

2.  В конец дво­ич­ной за­пи­си до­бав­ля­ет­ся дво­ич­ный код остат­ка от де­ле­ния числа N на 4.

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

 

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

1.  Стро­им дво­ич­ную за­пись: 1310  =  11012.

2.  Оста­ток от де­ле­ния 13 на 4 равен 1, до­бав­ля­ем к дво­ич­ной за­пи­си цифру 1, по­лу­ча­ем 110112  =  2710.

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

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

1.  Стро­им дво­ич­ную за­пись: 1410  =  11102.

2.  Оста­ток от де­ле­ния 14 на 4 равен 2, до­бав­ля­ем к дво­ич­ной за­пи­си цифры 10 (102  =  210), по­лу­ча­ем 1110102  =  5810.

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

 

Назовём до­ступ­ны­ми числа, ко­то­рые могут по­лу­чить­ся в ре­зуль­та­те ра­бо­ты этого ал­го­рит­ма. На­при­мер, числа 27 и 58  — до­ступ­ные. Опре­де­ли­те ко­ли­че­ство до­ступ­ных чисел, при­над­ле­жа­щих от­рез­ку [1 100 000 000; 1 987 653 210].

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

Ре­ше­ние.

Воз­мож­ные остат­ки от де­ле­ния числа на 4  — это 0, 1, 2, 3.

Рас­смот­рим какие цифры будут на конце чисел, при де­ле­нии на 4 да­ю­щие оста­ток 0, 1, 2 или 3.

Оста­ток 0 при де­ле­нии на 4 дадут числа, дво­ич­ная за­пись ко­то­рых за­кан­чи­ва­ет­ся на 00, до­бав­ля­ем оста­ток 0. В ре­зуль­та­те ав­то­ма­та до­ступ­ное число будет окан­чи­вать­ся на 000. Сле­до­ва­нии при де­ле­нии на 8 дол­жен быть оста­ток 0.

Оста­ток 1 при де­ле­нии на 4 дадут числа, дво­ич­ная за­пись ко­то­рых за­кан­чи­ва­ет­ся на 01, до­бав­ля­ем оста­ток 1. В ре­зуль­та­те ав­то­ма­та до­ступ­ное число будет окан­чи­вать­ся на 011. Сле­до­ва­нии при де­ле­нии на 8 дол­жен быть оста­ток 3.

Оста­ток 2 при де­ле­нии на 4 дадут числа, дво­ич­ная за­пись ко­то­рых за­кан­чи­ва­ет­ся на 10, до­бав­ля­ем оста­ток 2 (10 в в дво­ич­ной за­пи­си). В ре­зуль­та­те ав­то­ма­та до­ступ­ное число будет окан­чи­вать­ся на 1010. Сле­до­ва­нии при де­ле­нии на 16 дол­жен быть оста­ток 10.

Оста­ток 3 при де­ле­нии на 4 дадут числа, дво­ич­ная за­пись ко­то­рых за­кан­чи­ва­ет­ся на 11, до­бав­ля­ем оста­ток 3 (11 в дво­ич­ной за­пи­си). В ре­зуль­та­те ав­то­ма­та до­ступ­ное число будет окан­чи­вать­ся на 1111. Сле­до­ва­нии при де­ле­нии на 16 дол­жен быть оста­ток 15

По­счи­та­ем до­ступ­ные числа.

 

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

count = 0

for x in range(1_100_000_000, 1_987_653_210+1):

if x%16 in [10,15] or x%8 in [0,3]:

count += 1

print(count)

 

Ответ: 332869954.

 

 

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

Ре­зуль­тат ал­го­рит­ма - это число, дво­ич­ная за­пись ко­то­ро­го окан­чи­ва­ет­ся на 000, 011, 1010 или 1111. Такие числа можно пред­ста­вить вы­ра­же­ни­я­ми 8k, 8k+3, 16k+10 и 16k+15 (к - целое).

Ко­ли­че­ство целых чисел, за­да­ва­е­мых фор­му­лой ak+b, на от­рез­ке [d,u] можно найти по фор­му­ле (u-b)//a-(d-b-1)//a.

(1987653210-0)//8-(1100000000-0-1)//8=110956652

(1987653210-3)//8-(1100000000-3-1)//8=110956651

(1987653210-10)//16-(1100000000-10-1)//16=55478326

(1987653210-15)//16-(1100000000-15-1)//16=55478325

110956652+110956651+55478326+55478325=332869954

 

Эти вы­чис­ле­ния проще вы­пол­нить с по­мо­щью сле­ду­ю­щей про­грам­мы:

d,u = 1100000000,1987653210

m=0

for a,b in ((8,0),(8,3),(16,10),(16,15)):

m += (u-b)//a-(d-b-1)//a

print(m)


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

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


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