ЦУЙУ. Позиционные системы счисления

• Название: Позиционные системы счисления
• Дата: 15.09.2022
• Размер: 0.86 Mb.
• Имя файла: ege14 (1).doc
• Тип: Документы; #678195
• страница: 4 из 15

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

Р-22. Значение арифметического выражения: 9⁸ + 3⁵ – 9

записали в системе счисления с основанием 3. Сколько цифр «2» содержится в этой записи?

Решение:

1. 
   приведём все слагаемые к виду 3^N и расставим в порядке убывания степеней:
   

9⁸ + 3⁵ – 9 = 3¹⁶ + 3⁵ – 3²

2. 
   первое слагаемое, 3¹⁶, даёт в троичной записи одну единицу – она нас не интересует
   
3. 
   пара 3⁵ – 3² даёт 5 – 2 = 3 двойки
   
4. 
   Ответ: 3.
   

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

1. 
   задача может быть решена с помощью программы на Python, где есть встроенная поддержка длинных чисел:
   

x = 9**8+3**5-9

x3 = ''

while x:

x3 = str(x%3) + x3

x //= 3

print( 'Ответ:', x3.count('2') )

2. 
   вариант без использования символьных строк:
   

x = 9**8+3**5-9

count2 = 0

while x:

if x % 3 == 2:

count2 += 1

x //= 3

print( 'Ответ:', count2 )

3. 
   Ответ: 3.
   

Решение (электронные таблицы, Б.С. Михлин):

1. 
   эта конкретная задача может быть решена с помощью электронных таблиц
   
2. 
   Замечание. Электронные таблицы имеют ограничения при работе с длинными целыми числами. Например, Excel при вводе больших чисел заменяет все цифры после 15-го разряда на нули. Это легко проверить, введя в ячейку число с более чем 15-ю разрядами.
   

Обычно электронные таблицы при этом переходят к экспоненциальному (научному) формату. Если число больше, чем 10¹⁵, то оно хранится как вещественное число (неточно). Это ограничивает использование электронных таблиц. В этой задаче заданное число меньше, чем 10¹⁵, поэтому использовать электронные таблицы можно.

3. 
   введём заданное число, заданное арифметическим выражением, в ячейку электронной таблицы:
   

4. 
   выполним алгоритм перевода числа в троичную систему: найдём в B1 остаток от деления числа на 3, а в A2 – частное:
   

5. 
   скопируем формулы из А2 и В1 вниз до того момента, когда частное станет равно 0 (это означает окончание процесса перевода):
   

6. 
   подсчитаем в столбце В число остатков, равных 2:
   

7. 
   Ответ: 3.
   
8. 
   в OpenOffice Calc нужно использовать такие формулы:
   

в A2: =QUOTIENT(A1;3)
в B1: =MOD(A1;3)

в B19: =COUNTIF(B1:B18;2)

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

Р-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.