Способы решения задач по теме "Системы счисления". Решение задач ЕГЭ № 14 .

Тема: Позиционные системы счисления.

Что нужно знать:

• принципы кодирования чисел в позиционных системах счисления

• чтобы перевести число, скажем, 12345_N, из системы счисления с основанием в десятичную систему, нужно умножить значение каждой цифры на в степени, равной ее разряду:

4 3 2 1 0 ← разряды

1 2 3 4 5_N = 1·N⁴ + 2·N³ + 3·N² + 4·N¹ + 5·N⁰

• последняя цифра записи числа в системе счисления с основанием – это остаток от деления этого числа на

• две последние цифры – это остаток от деления на , и т.д.

• число 10^N записывается как единица и N нулей:

• число 10^N-1 записывается как N девяток:

• число 10^N-10^M = 10^M · (10^N-M – 1) записывается как N-M девяток, за которыми стоят M нулей:

• число 2^N в двоичной системе записывается как единица и N нулей:

• число 2^N-1 в двоичной системе записывается как N единиц:

• число 2^N–2^K при K N в двоичной системе записывается как N–K единиц и K нулей:

• поскольку , получаем , откуда следует, что

• число 3^N записывается в троичной системе как единица и N нулей:

• число 3^N-1 записывается в троичной системе как N двоек:

• число 3^N – 3^M = 3^M · (3^N-M – 1) записывается в троичной системе как N-M двоек, за которыми стоят M нулей:

• можно сделать аналогичные выводы для любой системы счисления с основанием a:

  • число a^N в системе счисления с основанием a записывается как единица и N нулей:

  • число a^N-1 в системе счисления с основанием a записывается как N старших цифр этой системы счисления, то есть, цифр (a-1):

  • число a^N – a^M = a^M · (a^N-M – 1) записывается в системе счисления с основанием a как N-M старших цифр этой системы счисления, за которыми стоят M нулей:

Операнды арифметического выражения записаны в системе счисления с основанием 15.

123x515 + 1x23315

В записи чисел переменной x обозначена неизвестная цифра из алфавита 15-ричной системы счисления. Определите наименьшее значение x, при котором значение данного арифметического выражения кратно 14.

Для найденного значения x вычислите частное от деления значения арифметического выражения на 14 и укажите его в ответе в десятичной системе счисления. Основание системы счисления в ответе указывать не нужно.

Решение:

1. запишем оба слагаемых в развернутой записи в системе счисления с основанием 15:

123x5₁₅ + 1x233₁₅ =

(1·15⁴+2·15³+3·15²+x·15+5) + (1·15⁴+x·15³+2·15²+3·15+3) =

(2·15⁴+2·15³+5·15²+ 3·15+8) + (x·15³ +x·15)

= (101250 + 6750 + 1125 + 45 + 8) + x · (3375 + 15) = 109178 + 3390·x

1. нам нужно, чтобы выражение Y = 109178 + 3390·x делилось на 14

2. остаток от деления 109178 на 14 равен 6; остаток от деления 3390 на 14 равен 2

3. для того чтобы Y делилось на 14, остаток от деления Y на 14 должен быть равен 0 (14, 28 и т.д.) Попробуем сложить остатки. 6+2*x = 0, даст нам отрицательное значение x, значит нужно взять следующее значение остатка 6+2*x = 14 2*x = 8 x =4.

4. Y = 109178 + 3390·4 = 122738. В качестве ответа нужно поделить Y на 14, получим 8767

5. Ответ 8767.

Решение (программа на Python):

1. полный текст программы:

for x in range (15):

a = 1*15**4 + 2*15**3 + 3*15**2 + x*15 + 5

b = 1*15**4 + x*15**3 + 2*15**2 + 3*15 + 3

if (a+b) %14 == 0:

print( (a+b) // 14 )

break

1. Ответ 8767.

Значение арифметического выражения: 49⁷ + 7²¹ – 7 – записали в системе

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

Решение:

1. приведём все числа к степеням семерки, учитывая, что 49 = 7²

7¹⁴ + 7²¹ – 7¹

1. расставим степени в порядке убывания:

7²¹ + 7¹⁴ – 7¹

1. Очевидно, что «шестёрки» в семеричной записи значения выражения возникнут только за счёт вычисления разности 7¹⁴ – 7¹, их количество равно 14-1=13

2. Ответ: 13.

Решение (использование программы):

1. язык Python позволяет работать с большими числами, не задумываясь о том, что для их хранения требуется больше памяти, чем для «обычного» целого числа (когда значение не помещается в 4 байта, интерпретатор автоматически переходит на представление числа в виде массива с «длинной арифметикой»)

2. поэтому может быть написана программа, которая вычисляет нужное значение и методом деления в столбик определяет все цифры его записи в семеричной системе счисления; шестёрки считаем с помощью счётчика count6:

x = 49**7 + 7**21 - 7

count6 = 0

while x:

if x % 7 == 6: count6 += 1

x //= 7

print( count6 )

1. Ответ: 13.

Решение (использование программы в среде Pascal ABC.NET):

1. Pascal ABC.NET за счет использования фреймворка .NET позволяет воспользоваться типом System.Numerics.BigInteger (предназначенным для произвольно больших целых со знаком) и связанными с ним функциями.

2. Таким образом, программа получается во многом схожей с программами на Python. Особо отметим, что использование функций возведения в степень не связанных с типом BigInteger для систем с основанием, не являющимся степенью двойки, приводит к неверным результатам из-за использования вещественных чисел. Например, BigInteger(power(9,34)) или BigInteger(9 ** 34) преобразуют вещественное число в целое произвольно большой длины, но еще при операции возведения в степень потеряется часть идеальной, математической мантиссы.

3. В связи с вышесказанным допустимо только использование записей вида BigInteger.Pow(9,34).

4. Полная программа:

var

a: BigInteger;

k: int64;

begin

a := BigInteger.Pow(49, 7) + BigInteger.Pow(7, 21) - 7;

k := 0;

while (a 0) do

begin

if (a mod 7 = 6) then

k := k + 1;

a := a div 7;

end;

writeln(k);

end.

1. Ответ: 13.

Значение арифметического выражения: 64¹⁰ + 2⁹⁰ - 16 записали в системе счисления с основанием 8. Сколько цифр «7» содержится в этой записи?

Решение:

1. Приведём все числа к степеням восьмерки, учитывая, что 16 = 64 - 48 =8²-6∙8¹

64¹⁰ + 2⁹⁰ - 16 = (8²)¹⁰ + 2^3∙30 – (8² – 48) = 8²⁰ + 8³⁰ – 8² + 6∙8¹

1. Перепишем выражение, располагая степени восьмёрки в порядке убывания:
   8²⁰ + 8³⁰ – 8² + 6∙8¹ = 8³⁰ + 8²⁰ – 8² + 6∙8¹

2. Очевидно, что «семёрки» в восьмеричной записи значения выражения возникнут только за счёт вычисления разности 8²⁰ – 8², их количество равно 20-2=18

3. Ответ: 18.

Решение (использование программы в среде Pascal ABC.NET):

1. В среде Pascal ABC.NET при использовании типа BigInteger задача может быть решена с помощью программы:

var

a: BigInteger;

k: int64;

begin

a := BigInteger.Pow(64, 10) + BigInteger.Pow(2, 90) - 16;

k := 0;

while (a 0) do

begin

if (a mod 8 = 7) then

k := k + 1;

a := a div 8;

end;

writeln(k);

end.

1. Ответ: 18.

Решение (программа на Python):

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

x = 64**10 + 2**90 - 16

print( oct(x).count('7') )

1. ответ: 18.

Значение арифметического выражения: 9⁹ – 3⁹ + 9¹⁹ – 19 записали в системе счисления с основанием 3. Сколько цифр «2» содержится в этой записи?

Решение:

1. Приведём все числа к степеням тройки, учитывая, что 19=27-8=3³-(2∙3¹+2∙3⁰):

9⁹ – 3⁹ + 9¹⁹ – 19= (3²)⁹ – 3⁹ + (3²)¹⁹ – (3³ – (2∙3¹ + 2∙3⁰)) = 3¹⁸ – 3⁹ + 3³⁸ – 3³ + 2∙3¹ + 2∙3⁰

1. Перепишем выражение, располагая степени тройки в порядке убывания:
   3¹⁸ – 3⁹ + 3³⁸ – 3³ + 2∙3¹ + 2∙3⁰ = 3³⁸ + 3¹⁸ – 3⁹ – 3³ + 2∙3¹ + 2∙3⁰

2. Сначала рассмотрим часть выражения, в которой имеется два расположенных подряд «минуса»: 3¹⁸ - 3⁹ ‑ 3³:

   1. найдём разность двух крайних чисел: 3¹⁸ – 3³, в её троичной записи 18 – 3=15 «двоек» и 3 «нуля»;

   2. вычтем из этого числа значение 3⁹: одна из «двоек» (на 10-й справа позиции) уменьшится на 1, остальные цифры не изменятся;

   3. итак, троичная запись разности 3¹⁸ – 3⁹ – 3³ содержит 15 – 1=14 «двоек», одну «единицу» и 3 «нуля»

3. Прибавим к полученному значению сумму: 2∙3¹ + 2∙3⁰ = 22₃. В троичной записи результата два крайних справа нуля заменяются на «двойки», остаётся один ноль. Общее количество «двоек»: 14+2=16.

4. Прибавление значения 3³⁸ не изменит количества «двоек» в троичном числе: слева от имеющихся цифр появятся ещё 38 – 18=20 «нулей» и одна «единица» – на 39-й справа позиции.

5. Итак, результат, записанный в троичной системе, содержит 39 цифр. Его состав: 16 «двоек», 2 «единицы» (их позиции: 39-я и 10-я справа) и 21 «нуль» (39-16-2=21).

6. Ответ: 16.

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

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

Решение:

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

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

1. первое слагаемое, 3¹⁶, даёт в троичной записи одну единицу – она нас не интересует

2. пара 3⁵ – 3² даёт 5 – 2 = 3 двойки

3. Ответ: 3.

Решение (программа):

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

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

x3 = ''

while x:

x3 = str(x%3) + x3

x //= 3

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

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

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

count2 = 0

while x:

if x % 3 == 2:

count2 += 1

x //= 3

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

1. Ответ: 3.

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

Решение:

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¹

1. старшая степень двойки – 2¹⁵³⁶, двоичная запись этого числа представляет собой единицу и 1536 нулей, то есть, состоит из 1537 знаков; таким образом, остаётся найти количество единиц

2. вспомним, число 2^N–2^K при K N записывается как N–K единиц и K нулей:

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

4. в нашем случае вы выражении

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

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

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

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

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

1. общее число единиц равно 1 + (1024 – 129) + (128 – 8) + 1 + 1 = 1018

2. таким образом, количество значащих нулей равно 1537 – 1018 = 519

3. ответ: 519.

Решение (программа на Python):

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

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

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

1. ответ: 519.

Сколько единиц в двоичной записи числа
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¹

1. вспомним, число 2^N–2^K при K N записывается как N–K единиц и K нулей:

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

3. в нашем случае вы выражении

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

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

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

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

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

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

2. ответ: 1210.

Решение (программа на Python):

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

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

print( x.count( '1' ) )

1. ответ: 1210.

Решите уравнение .

Ответ запишите в троичной системе счисления. Основание системы счисления указывать не нужно.

Решение:

1. переведём все числа в десятичную систему счисления:

1. собирая всё в одно уравнение получаем

1. это уравнение имеет два решения, 6 и -8; основание системы счисления – натуральное число, поэтому ответ – 6

2. переводим ответ в троичную систему: 6 = 2∙3¹ = 20₃.

3. ответ: 20.

Решение (программа на Python):

1. можно (но сложнее) решить задачу перебором с помощью программы:

a = 1*7**2 + 0 + 1 # перевод "101" в 10-ю систему

c = a - 1 # число "121" в 10-й системе

for i in range(3,100):# перебираем возможные основания

b = 1*i**2 + 2*i + 1 # перевод в 10-ю систему числа "121"

if b == c:

x = i # основание системы счисления (в 10й системе)

break

x3 = ''

while x 0:# перевод основания в 3-ю систему

x3 += str(x%3)

x //= 3

x3 = x3[::-1]# разворот числа

print(x3)

1. ответ: 20.

Решение (программа на Python):

1. вариант программы:

for x in range( 3, 37): # среди оснований от 3 до 36

if int( '121', x ) + 1 == int( '101', 7 ):

break

print('в 10 c.c:', x)

s = ''

while x:

s = str( x%3 ) + s

x //= 3

print( 'Ответ в 3 с.с:', s )

1. ответ: 20.

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

Решение:

1. приведём все числа к степеням двойки:

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

1. вспомним, что число 2^N-1 в двоичной системе записывается как N единиц: ,
   а число 2^N–2^K при K N записывается как N–K единиц и K нулей:

2. согласно п. 2, число 2²⁰¹⁵ – 2³ запишется как 2012 единиц и 3 нуля

3. прибавление 2⁴⁰²⁸ даст ещё одну единицу, всего получается 2012 + 1 = 2013 единиц

4. ответ: 2013.

Решение (программа на Python):

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

x = bin( 4**2014 + 2**2015 - 8 )
print( x.count( '1' ) )

1. ответ: 2013.

Сколько единиц в двоичной записи числа
4²⁰¹⁶ + 2²⁰¹⁸ – 8⁶⁰⁰ + 6

Решение:

1. приведём все числа к степеням двойки, разложив 6 как 2²+2¹

4²⁰¹⁶ + 2²⁰¹⁸ – 8⁶⁰⁰ + 6 = (2²)²⁰¹⁶ + 2²⁰¹⁸ - (2³)⁶⁰⁰ + 2² + 2¹ = 2⁴⁰³² + 2²⁰¹⁸ – 2¹⁸⁰⁰ + 2² + 2¹

1. вспомним, что число 2^N-1 в двоичной системе записывается как N единиц: ,
   а число 2^N–2^K при K N записывается как N–K единиц и K нулей:

2. согласно п. 2, число 2²⁰¹⁸ – 2¹⁸⁰⁰ запишется как 218 единиц и 1800 нулей

3. прибавление 2⁴⁰³² даст ещё одну единицу, а прибавление 2² + 2¹ – ещё две, всего получается 218 + 3 = 221 единица

4. ответ: 221.

Сколько единиц в двоичной записи числа
4²⁰¹⁶ – 2²⁰¹⁸ + 8⁸⁰⁰ – 80

Решение:

1. приведём все числа к степеням двойки, разложив 80 как 2⁶+2⁴

4²⁰¹⁶ – 2²⁰¹⁸ + 8⁸⁰⁰ – 80 = (2²)²⁰¹⁶ – 2²⁰¹⁸ + (2³)⁸⁰⁰ – 2² – 2¹ = 2⁴⁰³² – 2²⁰¹⁸ + 2²⁴⁰⁰ – 2⁶ – 2⁴

1. перестроим слагаемые в порядке уменьшения степеней двойки

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

1. вспомним, что число 2^N-1 в двоичной системе записывается как N единиц: ,
   а число 2^N–2^K при K N записывается как N–K единиц и K нулей:

2. согласно п. 2, число 2²⁴⁰⁰ – 2²⁰¹⁸ запишется как 382 единицы и 2018 нулей

3. добавляем старшее слагаемое 2⁴⁰³², получаем число 2⁴⁰³² + 2²⁴⁰⁰ – 2²⁰¹⁸, в котором 383 единицы и в конце (после последней единицы) – 2018 нулей:

1. выделим из этого значения последнюю единицу со следующими 2018 нулями как отдельное слагаемое (число 2²⁰¹⁸):

,

где число K содержит 382 единицы в старших разрядах; таки образом, интересующее нас число равно

1. согласно п. 2, число 2²⁰¹⁸ – 2⁶ запишется как 2012 единиц и 6 нулей; также выделим последнюю единицу с последующими нулями как отдельное слагаемое:

где число L содержит 2011 единиц

1. теперь остаётся найти, сколько единиц будет в двоичной записи числа 2⁶ – 2⁴, согласно п. 2 находим, что оно содержит 2 единицы

2. таким образом, общее число единиц равно 382 + 2011 + 2 = 2395

3. ответ: 2395.