Информатика ЕГЭ 14 задание разбор

1
2
3
4
5
6
7
8
9
10
11
12

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.

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 )

1

✎ Решение теоретическое:

• Существует правило:
2^N = 10..0₂(1 единица и N нулей)
• Чтобы воспользоваться этим правилом, преобразуем общее выражение к степеням двойки:

21024 + (22)64 - 26 = 21024 + 2128 - 26

• При переводе в двоичную систему получим:

10...0 (1024 нуля) + 10...0 (128 нулей) - 10...0 (6 нулей)

• Обратим внимание, что разница между числами большая. Т.е. при выполнении сложения в столбик, единицы в одном и том же разряде быть не могут. Так:

 10....00000  - 1024 нуля
+
       10..0  - 128 нулей
_________________________
 10....10..0  

• Из первого слагаемого 10…0 (1024 нуля) запомним одну единицу в старшем бите, остальные нули нас не интересуют, так как далее мы воспользуемся другим правилом — для разницы:

 10....00000  - 1024 нуля
+
       10..0  - 128 нулей
_________________________
 10....10..0  - запомним единицу

• Существует также правило:
2^N — 2^K = 1…1 (N - K единиц)0…0(K нулей)
• По формуле выполним вычитание 2¹²⁸ — 2⁶: получим 1..1 (122 единицы) 0..0(6 нулей):

 10..0000000  - 128 нулей
-
     1000000  
_________________________
 11..1000000  - 122 единицы и 6 нулей

• Прибавим к 122 получившимся единицам еще одну из первого слагаемого (10…0 (1024 нуля)) и получим:

122 + 1 = 123 единицы

1
2
3
4
5
6
7
8
9
10
11
12

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.

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 )

1

✎ Решение теоретическое:

• Приведем все числа к степеням 7:

720 + 730 - 72

• Расставим операнды выражения в порядке убывания степеней:

730 + 720 - 72

• Вспомним две формулы для работы со системами счисления:

1.
an = 10..0a
       n
2.
an - am = (a-1)..(a-1)0..0a
              n-m       m

• Переведем первое число согласно формуле 1:

730 = 10..0
        30

• В данном числе нет цифры 6, как и в остальных числах.
• Цифра 6 появляется при выполнении вычитания.
• Подсчитаем все «6», используя формулу 2:

0 + (20 - 2) = 18

• Получаем шестерок: 18

Результат: 18

1

1
2
3
4
5
6
7
8

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

1

1
2
3
4
5
6
7
8

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..0a
       n
2.
an - am = (a-1)..(a-1)0..0a
              n-m       m

• Переведем первое число согласно формуле 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

✎ Решение с использованием программирования:

PascalABC.net: 1 2 3 4 5 6 7 8 9 10 11 12 13 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. 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 - 12 print(x) k = 0 while x: if x % 2 == 0: k += 1 x //= 2 print( 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 )

С++:

✎ Решение теоретическое:
4350 + 8340 – 2320 – 12

(22)350 + (23)340 - 2320 - 3*22 =
(22)350 + (23)340 - 2320 - 12 =
2700 + 21020 - 2320 - (23 + 22)

21020 + 2700 - 2320 - 23 - 22

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

• Для начала достаточно перевести первое и последнее число предложенного интервала в троичную систему счисления. Сделаем это:

1.
 13 | 3 
 12   4 | 3 
  1   3   1   
      1
1310 = 1113

2.
23 | 3 
21   7 | 3 
2    6   2
     1
2310 = 2123

• Теперь добавим промежуточные числа в троичной системе счисления (прибавляя единицу к каждому очередному полученному числу), не забывая, что в троичной системе всего три цифры (0, 1 и 2):

111, 112, 120, 121, 122, 200, 201, 202, 210, 211, 212

• На всякий случай стоит посчитать количество полученных чисел и сравнить их с количеством чисел в исходной последовательности.
• Теперь осталось посчитать количество цифр 2 в полученной последовательности. Их 13:

111, 112, 120, 121, 122, 200, 201, 202, 210, 211, 212

• Разделим уравнение на три части и вычислим каждую часть отдельно (выделим части разным цветом):

204N+1 = 204N + 2616
 1       2     3 

• Используем формулу разложения числа по степеням основания:

1. 
210
204N+1

По формуле получаем:
2*(N+1)2 + 0*(N+1)1 + 4*(N+1)0 =
= 2*(N2 + 2N + 1) + 0 + 4 = 2N2 + 4N + 6

• Выполним то же самое для остальных двух частей:

2.
210
204N

По формуле получаем:
2*N2 + 0*N1 + 4*N0 =
= 2N2 + 4

3.
2616 = 3810

• Подставим результаты всех частей в уравнение:

2N2 + 4N + 6 = 2N2 + 4 + 38;
4N = 36;
N = 9

• Вместо обозначения искомой системы счисления введем неизвестное x:

144x + 24x = 201x

• Запишем формулу перевода в десятичную систему счисления каждого из слагаемых и сумму исходного равенства:

144 + 24 = 201
1*x2 + 4*x1 + 4*x0 + 2*x1 + 4*x0 = 2*x2 + 0*x1 + 1*x0

• Упростим полученное уравнение:

x2 - 6x - 7 = 0

• Решим уравнение:

D = b2 - 4ac = 36 - 4*1*(-7) = 64
x = (-b ± √D)/2a
x1 = (6 + 8)/2 = 7
x2 = (6 - 8)/2 - не подходит
x = 7

• Вспомним правило:
Последняя цифра записи числа в системе счисления с основанием X — это остаток от деления этого числа на X
• Примем искомую систему счисления за x. Тогда, исходя из приведенного правила имеем:

94 / x = некоторое число и остаток 3
и
68 / x = некоторое число и остаток 3

• Поскольку x должно быть целым числом, то следующее деление должно выполняться без остатка:

91/x 
65/x

• Иными словами x — наибольший общий делитель чисел 91 и 65.
• Найдем НОД, например, по алгоритму Евклида:

91 - 65 = 26
65 - 26 = 39
39 - 26 = 13
26 - 13 = 13 

• Получаем результат 13.

• Данные числа с утерянными символами переведем из 16-й и из 8-й системы счисления в двоичную. Перевод будем делать триадами и тетрадами, неизвестные позиции оставим пустыми:

1. *516
    *   |    5  16

* * * * | 0 1 0 1 2

2. *0*8
  *  |  0  |  *  8
* * *|0 0 0|* * * 2

• Сопоставим известные и неизвестные биты в обеих получившихся масках:

* * 0 0 0 1 0 1

• Неизвестными остались 7-й и 8-й бит. Они не могут быть одновременно нулями, так как для *0*₈ тогда исчезнет старший разряд. Поэтому оставшиеся варианты будут такими:

1. 01000101
2. 10000101
3. 11000101

• Итого 3 варианта.

• Так как 75 должно оканчиваться на 13, то имеем два общих случая:

1. 7510 = 13N 
2. 7510 = ...13N (число оканчивается на 13)

• Рассмотрим подробно каждый случай.

1 случай:

• Остаток должен быть равен 3 (последнее число в неизвестной системе), а частное должно равняться 1 (предпоследнее число в неизвестной системе):

 75|N 
  N|1  отсюда имеем => 75 - N = 3; т.е. N = 72
  3

• Таким образом, мы получили одно из искомых оснований (72).

2 случай:

• Искомое оканчивается на цифру 3, значит:

 75|N 
 72|y  отсюда имеем => 75 = Ny + 3, где N - целое, неотриц.
  3

• и далее, частное от деления — 1 (предпоследнее число):

 75|N  
 72|  y |N   => y = Nz + 1, где z - целое, неотриц.
  3  y-1|z
       1

• Получаем два равенства (систему уравнений):

75 = Ny + 3
y = Nz + 1

• Подставим y из второго равенства в первое:

75 = N (Nz + 1) + 3;
75 = N2z + N + 3;
75 = N2z + N

• Выразим z:

z = (72 - N)/N2

• Учитывая то, что z — целое неотрицательное число, то 72 — N должно быть кратно N², т.е. в числителе не может быть простого числа.
• Простое число 67 получается путем вычитания из 72 числа 5. Соответственно, 5 нам не подходит: N ≠ 5:

72 - 5 / 52 = 67 / 25  не делится, - не подходит!

• Еще одно простое число — 71 получится при вычитании 72 — 1. Единица не подходит, так как при переводе в конце числа никак не останется 13: N ≠ 1.
• Раз в знаменателе N², то отбросим все числа, квадрат которых больше 72: 9, 10, … и т.д. до бесконечности: N < 9
• Раз в итоговом числе есть число 13, значит основание системы счисления больше 3 (т.е. цифра три присутствует в системах, начиная с 4-й): N >= 4
• Проверим оставшиеся варианты — 4, 6, 7, 8:

 75 | 4 
 72 | 18| 4 
  3   16| 2
       2  => не подходит! должна быть единица

 75 | 6 
 72 | 12| 6 
  3   12| 1
       0  => не подходит! должна быть единица

 75 | 7 
 70 
  5 => не подходит! должна быть 3 

 75 | 8 
 72 | 9| 8 
  3   8| 1
       1  => подходит!

Рассмотрим каждый сомножитель отдельно.
• Первый сомножитель:

25 = 32

Переведем в троичную систему счисления (делением на 3, переписываем остатки).
Результат:
3210 = 10123

• Для рассмотрения второго сомножителя будем использовать правило:



• Получим:

325 = 10..0{25 нулей}3

• Выполним произведение, но для простоты счета, представим, что нулей не 25, а только 3:

   1000 x
   1012 =
   ----
   2000
  1000
 0000
1000
-------
1012000

• В исходном числе было 3 нуля, стало 4. Значит если было 25 нулей, то станет 25 + 1 = 26.
• Единиц = 2, двоек = 1.