14-е задание: «Операции в системах счисления» Уровень сложности — повышенный, Требуется использование специализированного программного обеспечения — нет, Максимальный балл — 1, Примерное время выполнения — 5 минут.
Проверяемые элементы содержания: Знание позиционных систем счисления
До ЕГЭ 2021 года — это было задание № 16 ЕГЭ
Типичные ошибки и рекомендации по их предотвращению:
"Основные ошибки связаны с невнимательностью при выполнении арифметических действий
в недесятичных системах счисления. Например, вычитания единицы в ситуации типа: 10100002 – 1"
ФГБНУ "Федеральный институт педагогических измерений"
С основами темы можно ознакомиться в теории к заданию 1.
Перевод числа из любой системы счисления в десятичную
Чтобы перевести, например, 10045N, из системы счисления с основанием N в десятичную систему, нужно умножить значение каждой цифры на N в степени, равной разряду этой цифры:
Особенности при переводах в разные системы счисления
Некоторые правила, которые нужно знать, при работе с системами счисления:
последняя цифра (крайняя справа) в записи числа в системе счисления с основанием N – представляет собой остаток от деления этого числа на N:
710 = 1112
7/2 = остаток 1
две крайние справа цифры числа в системе счисления с основанием N – это остаток от деления этого числа на N², и так далее:
710 = 1112
112=310
7/22 = остаток 310 (112)
десятичное число 10N записывается как единица и N нулей:
тогда как десятичное число 2N> в двоичной системе записывается как единица и N нулей:
а десятичное число 3N записывается в троичной системе в виде единицы и N нулей:
можно сделать аналогичные выводы для любой системы счисления с основанием a; общее правило:
десятичное 10N-1 записывается как N девяток:
тогда как десятичное число 2N-1 в двоичной системе записывается как N единиц:
а десятичное число 3N-1 записывается в троичной системе как N двоек:
значит есть общее правило: число aN-1 в системе счисления с основанием a записывается как N старших цифр этой системы, то есть, цифр (a-1)
десятичное число 10N-10M = 10M * (10N-M – 1) записывается как N-M девяток, за которыми стоят M нулей:
тогда как десятичное число 2N – 2K при K < N в двоичной системе записывается как N – K единиц и K нулей:
14_12: Разбор задания 14 ЕГЭ по информатике (с сайта К. Полякова (с ссылкой на Е. Джобса), вариант 254):
Значение арифметического выражения
43∙7103 – 21∙757 + 98
записали в системе счисления с основанием 7. Найдите сумму цифр получившегося числа и запишите её в ответе в десятичной системе счисления.
✍Решение:
✎ Решение с использованием программирования:
PascalABC.net:
1
2
3
4
5
6
7
8
9
10
11
12
beginvar x,s: Biginteger;
x :=43*Biginteger.Pow(7,103)-21*Biginteger.Pow(7,57)+98;// в получившемся числе рассматриваем каждую цифру в 7-й системе сч.
s:=0;while x > 0dobegin
s:=s+ x mod7;// добавляем цифру правого разряда
x := x div7;// убираем разряд числа в 7-й системе сч.end;
println(s);end.
begin
var x,s: Biginteger;
x := 43*Biginteger.Pow(7, 103) - 21*Biginteger.Pow(7, 57) + 98;
// в получившемся числе рассматриваем каждую цифру в 7-й системе сч.
s:=0;
while x > 0 do
begin
s:=s+ x mod 7; // добавляем цифру правого разряда
x := x div 7; // убираем разряд числа в 7-й системе сч.
end;
println(s);
end.
Python:
1
2
3
4
5
6
7
x =43*7**103 - 21*7**57 + 98
s =0# в получившемся числе рассматриваем каждую цифру в 7-й системе сч.while x:
s+= x % 7# добавляем цифру к сумматору
x //=7# убираем разряд числа в 7-й системе сч.print( s )
x = 43*7**103 - 21*7**57 + 98
s = 0
# в получившемся числе рассматриваем каждую цифру в 7-й системе сч.
while x:
s+= x % 7 # добавляем цифру к сумматору
x //= 7 # убираем разряд числа в 7-й системе сч.
print( s )
С++:
1
Результат: 276
14_1: Задание 14 (16) ЕГЭ по информатике 2017 ФИПИ вариант 3 (Крылов С.С., Чуркина Т.Е.):
Значение арифметического выражения: 21024 + 464 - 64
записали в системе счисления с основанием 2.
beginvar k :=0;var x: Biginteger;
x := Biginteger.Pow(2,1024)+ Biginteger.Pow(4,64)-64;// в получившемся числе рассматриваем каждую цифру в 2-й системе сч.while x > 0dobeginif x mod2=1then k +=1;// если цифра = 1, то считаем ее
x := x div2;// убираем разряд числа в 2-й системе сч.end;
println(k);end.
begin
var k := 0;
var x: Biginteger;
x := Biginteger.Pow(2, 1024) + Biginteger.Pow(4, 64) - 64;
// в получившемся числе рассматриваем каждую цифру в 2-й системе сч.
while x > 0 do
begin
if x mod 2 = 1 then k += 1; // если цифра = 1, то считаем ее
x := x div 2; // убираем разряд числа в 2-й системе сч.
end;
println(k);
end.
Python:
1
2
3
4
5
6
7
8
x =2**1024 + 4**64 - 64
k =0# в получившемся числе рассматриваем каждую цифру в 2-й системе сч.while x:
if x % 2==1: # если цифра = 1, то считаем ее
k +=1
x //=2# убираем разряд числа в 2-й системе сч.print( k )
x = 2**1024 + 4**64 - 64
k = 0
# в получившемся числе рассматриваем каждую цифру в 2-й системе сч.
while x:
if x % 2 == 1: # если цифра = 1, то считаем ее
k += 1
x //= 2 # убираем разряд числа в 2-й системе сч.
print( k )
С++:
1
✎ Решение теоретическое:
Существует правило:
2N = 10..02(1 единица и N нулей)
Чтобы воспользоваться этим правилом, преобразуем общее выражение к степеням двойки:
Из первого слагаемого 10...0 (1024 нуля) запомним одну единицу в старшем бите, остальные нули нас не интересуют, так как далее мы воспользуемся другим правилом - для разницы:
beginvar x: Biginteger;
x := Biginteger.Pow(49,10)+ Biginteger.Pow(7,30)-49;// в получившемся числе рассматриваем каждую цифру в 7-й системе сч.var k:=0;while x > 0dobeginif x mod7=6then k+=1;// если цифра = 6, то считаем ее
x := x div7;// убираем разряд числа в 7-й системе сч.end;
println(k);end.
begin
var x: Biginteger;
x := Biginteger.Pow(49, 10) + Biginteger.Pow(7, 30) - 49;
// в получившемся числе рассматриваем каждую цифру в 7-й системе сч.
var k:=0;
while x > 0 do
begin
if x mod 7 = 6 then k+=1; // если цифра = 6, то считаем ее
x := x div 7; // убираем разряд числа в 7-й системе сч.
end;
println(k);
end.
Python:
1
2
3
4
5
6
7
8
x =49**10 + 7**30 - 49
k =0# в получившемся числе рассматриваем каждую цифру в 7-й системе сч.while x:
if x % 7==6: # если цифра = 6, то считаем ее
k +=1
x //=7# убираем разряд числа в 7-й системе сч.print( k )
x = 49**10 + 7**30 - 49
k = 0
# в получившемся числе рассматриваем каждую цифру в 7-й системе сч.
while x:
if x % 7 == 6: # если цифра = 6, то считаем ее
k += 1
x //= 7 # убираем разряд числа в 7-й системе сч.
print( k )
С++:
1
✎ Решение теоретическое:
Приведем все числа к степеням 7:
720 + 730 - 72
Расставим операнды выражения в порядке убывания степеней:
730 + 720 - 72
Вспомним две формулы для работы со системами счисления:
1.
an = 10..0an2.
an - am = (a-1)..(a-1)0..0an-mm
Переведем первое число согласно формуле 1:
730 = 10..0
30
В данном числе нет цифры 6, как и в остальных числах.
Цифра 6 появляется при выполнении вычитания.
Подсчитаем все "6", используя формулу 2:
0 + (20 - 2) = 18
Получаем шестерок: 18
Результат: 18
Подробное решение 14 (16) задания демоверсии ЕГЭ 2018 года смотрите на видео (аналитическое решение):
x =4**500 + 3*4**2500 + 16**500 - 1024
k =0# в получившемся числе рассматриваем каждую цифру в 4-й системе сч.while x:
if x % 4==3: # если цифра = 3, то считаем ее
k +=1
x //=4# убираем разряд числа в 4-й системе сч.print( k )
x = 4**500 + 3*4**2500 + 16**500 - 1024
k = 0
# в получившемся числе рассматриваем каждую цифру в 4-й системе сч.
while x:
if x % 4 == 3: # если цифра = 3, то считаем ее
k += 1
x //= 4 # убираем разряд числа в 4-й системе сч.
print( k )
С++:
1
Результат: 496
Подробное решение данного 14 задания ЕГЭ по информатике можно посмотреть на видео (аналитическое решение):
14_5: Разбор 14 (16) задания ЕГЭ по информатике, вариант 2 (ФИПИ, «ЕГЭ информатика и ИКТ, типовые экзаменационные варианты 2018», 10 вариантов, С.С. Крылов, Т.Е. Чуркина):
Значение арифметического выражения: 81024 + 832 – 65 – записали в системе счисления с основанием 8. Сколько цифр «7» содержится в этой записи?
x =8**1024 + 8**32 - 65
k =0# в получившемся числе рассматриваем каждую цифру в 8-й системе сч.while x:
if x % 8==7: # если цифра = 7, то считаем ее
k +=1
x //=8# убираем разряд числа в 8-й системе сч.print( k )
x = 8**1024 + 8**32 - 65
k = 0
# в получившемся числе рассматриваем каждую цифру в 8-й системе сч.
while x:
if x % 8 == 7: # если цифра = 7, то считаем ее
k += 1
x //= 8 # убираем разряд числа в 8-й системе сч.
print( k )
С++:
1
✎ Решение теоретическое:
Приведем все числа к степеням восьмерки:
65 = 64 + 1 = 82 + 80;
Получаем:
81024 + 832 - (82 + 80);
81024 + 832 - 82 - 80
Вспомним две формулы для работы с системами счисления:
1.
an = 10..0an2.
an - am = (a-1)..(a-1)0..0an-mm
Переведем первое число согласно формуле 1:
81024 = 10..0
1024
В данном числе нет цифры 7, как и в остальных числах.
Цифра 7 появляется при выполнении вычитания. У нас два таких действия, идущих подряд. Это неудобно. Необходимо, чтобы действия чередовались (a + b - c + d - e...)
Вспомним еще одну формулу:
3.
-2n = -2n+1 + 2n
! Формула предназначена для чисел в двоичной системе счисления,
но для подсчета цифр "7" в 8-й (или "6" в 7-й и т.п.) ее можно использовать
(для поиска единиц или нулей она не подходит!!!)
В нашем случае заменим часть выражения:
-82 = -83 + 82! обратите внимание, что тождество неверно, но
при поиске количества "7" этой формулой можно воспользоваться
(для поиска единиц или нулей она не подходит!)
Получаем:
81024 + 832 - 83 + 82- 80
Получили чередование операций "+" и "-".
Теперь посчитаем все "7", используя формулу 2:
0 + (32 - 3) + (2 - 0) = 31
Получаем семерок: 31
Результат: 31
14_13: Разбор 14 задания ЕГЭ по информатике (с сайта К. Полякова # 113):
Сколько значащих нулей в двоичной записи числа 4350 + 8340 – 2320 – 12?
begin
var b2 := biginteger(2);
var numb := (2 * b2) ** 350 + (4 * b2) ** 340 - (1 * b2) ** 320 - 12;
var digit: biginteger;
var n := 0;
while numb > 0 do
begin
digit := numb mod 2;
if digit = 0 then n += 1;
numb := numb div 2
end;
print(n)
end.
Python:
1
2
3
4
5
6
7
x =4**350 + 8**340 - 2**320 - 12print(x)
k =0while x:
if x % 2==0: k +=1
x //=2print( k )
x = 4**350 + 8**340 - 2**320 - 12
print(x)
k = 0
while x:
if x % 2 == 0: k += 1
x //= 2
print( k )
С++:
1
✎ Решение теоретическое:
4350 + 8340 – 2320 – 12
По возможности приведем каждое слагаемое к степеням 2. Получим:
Далее рассуждаем так: количество нулей можно найти, если из общего количества цифр в результирующем числе вычесть количество не нулей (любых других цифр).
Расположим операнды по убыванию:
21020 + 2700 - 2320 - 23 - 22
Наибольшее число 21020, в нем 1021 разряд в двоичной с.с. (одна единица и 1020 нулей). То есть всего 1021 знаков.
Для того, чтобы избежать два подряд идущих минуса, воспользуемся правилом -2n = -2n+1+2n и преобразуем выражение:
21020 + 2700 - 2321+ 2320- 24 + 23 - 22
Посчитаем количество не нулей в каждом операнде:
21020 -> один не ноль
2700 - 2321 -> 379 не нулей
2320- 24 -> 316 не нулей
23 - 22 -> один не ноль
Итого: 1+ 379+316 +1 = 697
Получаем нулей:
1021 - 697 = 324
Результат: 324
Найти основание системы счисления и уравнения
14_7: Разбор задания 14 ЕГЭ по информатике (с сайта К. Полякова, вариант 36):
Укажите, сколько всего раз встречается цифра 2 в записи чисел 13, 14, 15, …, 23 в системе счисления с основанием 3.
Теперь добавим промежуточные числа в троичной системе счисления (прибавляя единицу к каждому очередному полученному числу), не забывая, что в троичной системе всего три цифры (0, 1 и 2):
14_10: Разбор задания 14 ЕГЭ по информатике (с сайта К. Полякова, вариант 137):
Некоторое число X из десятичной системы счисления перевели в системы счисления с основаниями 16, 8. Часть символов при записи утеряна. Позиции утерянных символов обозначены *:
Данные числа с утерянными символами переведем из 16-й и из 8-й системы счисления в двоичную. Перевод будем делать триадами и тетрадами, неизвестные позиции оставим пустыми:
Сопоставим известные и неизвестные биты в обеих получившихся масках:
* * 0 0 0 1 0 1
Неизвестными остались 7-й и 8-й бит. Они не могут быть одновременно нулями, так как для *0*8 тогда исчезнет старший разряд. Поэтому оставшиеся варианты будут такими:
1. 01000101
2. 10000101
3. 11000101
Итого 3 варианта.
Ответ: 3
Предлагаем посмотреть видео решения данного 14 задания ЕГЭ (аналитическое решение):
В 14_11 ошибка. В ответе не 26, а 25 нулей. Как было 25, так и останется — не надо прибавлять ещё один ноль. Посчитал вручную и перепроверил на калькуляторе:
32 * 3^25 = 32 * 847288609443 = 27113235502176 = 1012,00000,00000,00000,00000,00000\/3.
ахелес
последнее видео неправильно! В порядке возрастания, т.е. от меньшего к большему
admin
так и есть, в порядке возрастания: сначала 8, потом 72
Hulos
В 14_11 ошибка. В ответе не 26, а 25 нулей. Как было 25, так и останется — не надо прибавлять ещё один ноль. Посчитал вручную и перепроверил на калькуляторе:
32 * 3^25 = 32 * 847288609443 = 27113235502176 = 1012,00000,00000,00000,00000,00000\/3.