Позиционные системы счисления

• Название: Позиционные системы счисления
• Дата: 18.04.2022
• Размер: 0.83 Mb.
• Имя файла: ege14 3.doc
• Тип: Документы; #483521
• страница: 4 из 14

Ещё пример задания:

Р-21. Сколько значащих нулей в двоичной записи числа
4⁵¹² + 8⁵¹² – 2¹²⁸ – 250

Решение (способ Е.А. Смирнова, Нижегородская область):

1. 
   Общая идея: количество значащих нулей равно количеству всех знаков в двоичной записи числа (его длине!) минус количество единиц
   
2. 
   приведём все числа к степеням двойки, учитывая, что 250 = 256 – 4 – 2 = 2⁸ – 2² – 2¹:
   

4⁵¹² + 8⁵¹² – 2¹²⁸ – 250 = (2²)⁵¹² + (2³)⁵¹² – 2¹²⁸ – 2⁸ + 2² + 2¹ =

= 2¹⁵³⁶ + 2¹⁰²⁴ – 2¹²⁸ – 2⁸ + 2² + 2¹

3. 
   старшая степень двойки – 2¹⁵³⁶, двоичная запись этого числа представляет собой единицу и 1536 нулей, то есть, состоит из 1537 знаков; таким образом, остаётся найти количество единиц
   
4. 
   вспомним, число 2^N–2^K при K < N записывается как N–K единиц и K нулей:
   
5. 
   для того чтобы использовать это свойство, нам нужно представить заданное выражение в виде пар вида 2^N–2^K, причём в этой цепочке степени двойки нужно выстроить по убыванию
   
6. 
   в нашем случае вы выражении
   

2¹⁵³⁶ + 2¹⁰²⁴ – 2¹²⁸ – 2⁸ + 2² + 2¹

стоит два знака «минус» подряд, это не позволяет сразу использовать формулу

7. 
   используем теперь равенство , так что – 2¹²⁸ = – 2¹²⁹ + 2¹²⁸; получаем
   

2¹⁵³⁶ + 2¹⁰²⁴ – 2¹²⁹ + 2¹²⁸ – 2⁸ + 2² + 2¹

здесь две пары 2^N–2^K , а остальные слагаемые дают по одной единице

8. 
   общее число единиц равно 1 + (1024 – 129) + (128 – 8) + 1 + 1 = 1018
   
9. 
   таким образом, количество значащих нулей равно 1537 – 1018 = 519
   
10. 
    ответ: 519.
    

Решение (программа на Python, Б.С. Михлин):

3. 
   если доступна среда программирования на Python, можно написать программу, которая использует встроенную арифметику длинных чисел:
   

x = 4**512 + 8**512 - 2**128 - 250

print( bin(x)[2:].count('0') )

4. 
   ответ: 519.
   

Ещё пример задания:

Р-20. Сколько единиц в двоичной записи числа
4²⁰¹⁵ + 8⁴⁰⁵ – 2¹⁵⁰ – 122

Решение (способ Е.А. Смирнова, Нижегородская область):

1. 
   приведём все числа к степеням двойки, учитывая, что 122 = 128 – 4 – 2 = 2⁷ – 2² – 2¹:
   

4²⁰¹⁵ + 8⁴⁰⁵ – 2¹⁵⁰ – 122 = (2²)²⁰¹⁵ + (2³)⁴⁰⁵ – 2¹⁵⁰ – 2⁷ + 2² + 2¹ =

= 2⁴⁰³⁰ + 2¹²¹⁵ – 2¹⁵⁰ – 2⁷ + 2² + 2¹

2. 
   вспомним, число 2^N–2^K при K < N записывается как N–K единиц и K нулей:
   
3. 
   для того чтобы использовать это свойство, нам нужно представить заданное выражение в виде пар вида 2^N–2^K, причём в этой цепочке степени двойки нужно выстроить по убыванию
   
4. 
   в нашем случае вы выражении
   

2⁴⁰³⁰ + 2¹²¹⁵ – 2¹⁵⁰ – 2⁷ + 2² + 2¹

стоит два знака «минус» подряд, это не позволяет сразу использовать формулу

5. 
   используем теперь равенство , так что – 2¹⁵⁰ = – 2¹⁵¹ + 2¹⁵⁰; получаем
   

2⁴⁰³⁰ + 2¹²¹⁵ – 2¹⁵¹ + 2¹⁵⁰ – 2⁷ + 2² + 2¹

здесь две пары 2^N–2^K , а остальные слагаемые дают по одной единице

6. 
   общее число единиц равно 1 + (1215 – 151) + (150 – 7) + 1 + 1 = 1210
   
7. 
   ответ: 1210.
   

Решение (С.О. Куров, Москва):

1. 
   приведём все числа к степеням двойки, учитывая, что 122 = 128 – 4 – 2 = 2⁷ – 2² – 2¹:
   

4²⁰¹⁵ + 8⁴⁰⁵ – 2¹⁵⁰ – 122 = (2²)²⁰¹⁵ + (2³)⁴⁰⁵ – 2¹⁵⁰ – 2⁷ + 2² + 2¹ =

= 2⁴⁰³⁰ + 2¹²¹⁵ – 2¹⁵⁰ – 2⁷ + 2² + 2¹

2. 
   ищем в разности крайнюю левую степень двойки и крайнюю правую 2¹²¹⁵ – 2⁷, при этом 2¹⁵⁰ на время «теряем»
   
3. 
   определяем количество единиц в разности 2¹²¹⁵ – 2⁷, получаем 1215 – 7 = 1208 единиц
   
4. 
   так как «внутри» этой разности есть еще 2¹⁵⁰, то просто вычитаем одну единицу: 1208 – 1 = 1207; итого в разности 2¹²¹⁵ – 2¹⁵⁰ – 2⁷ ровно 1207 единиц
   
5. 
   осталось прибавить по одной единицы от чисел 2⁴⁰³⁰, 2², 2¹
   
6. 
   Ответ: 1210
   

Решение (программа на Python, Б.С. Михлин):

1. 
   используется встроенная «длинная арифметика» в Python:
   

x = bin( 4**2015 + 8**405 - 2**150 - 122 )

print( x.count( '1' ) )

2. 
   ответ: 1210.