Задание 5

Проверка числовой последовательности на соответствие алгоритму

  • для выполнения некоторых заданий необходимо повторить тему системы счисления;
  • максимальное значение суммы цифр десятичного числа — это 18, так как 9 + 9 = 18;
  • для проверки правильности переданного сообщения иногда вводится бит четности — дополнительный бит, которым дополняется двоичный код таким образом, чтобы в результате количество единиц стало четным: т.е. если в исходном сообщении количество единиц было четным, то добавляется 0, если нечетным — добавляется 1:
    • например: 
 310 = 112 
после добавления бита четности: 110
----
 410 = 1002 
после добавления бита четности: 1001
  • добавление к двоичной записи числа нуль справа увеличивает число в 2 раза:
    • например:
1112 - это 710
добавим 0 справа:
11102 - это 1410

Теперь будем рассматривать конкретные типовые экзаменационные варианты по информатике с объяснением их решения.

Разбор 5 задания


Решение задания про алгоритм, который строит число R

5_12: Демоверсия ЕГЭ 2018 информатика:

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

  1. Строится двоичная запись числа N.
  2. К этой записи дописываются справа ещё два разряда по следующему правилу:
  3. складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
  4. над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2.

    5. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.

    Укажите минимальное число R, которое превышает число 83 и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.


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

  • Заметим, что после второго пункта условия задачи получаются только четные числа (т.к. если число в двоичной системе заканчивается на 0, то оно четное). Таким образом, нас будут интересовать только четные числа.
  • Наименьшим возможным числом, превышающим 83, является число 84. С ним и будем работать.
  • Переведем 84 в двоичную систему счисления. На компьютерном ЕГЭ это можно сделать с помощью программистского режима калькулятора. Либо в консоли интерпретатора Python набрать bin(84). Получим:
    • 84 = 1010100
  • В данном числе выделенная часть — это N. Значит, необходимое нам двоичное число — это 10101. После первого пункта задачи к данному числу должна была добавиться справа единица, так как оно нечетное. А мы имеем 0. Соответственно, это оно не подходит.
  • Возьмем следующее четное число — 86. Переведем его в двоичную систему счисления:
    • 86 = 1010110
  • В данном числе выделенная часть — это N. Значит, необходимое нам двоичное число — это 10101. После первого пункта задачи к данному числу должна была добавиться справа единица, так и есть: 101011. А затем добавляется 0: 1010110. Соответственно, оно подходит.

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

    PascalAbc.Net:

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

    uses school;
 
begin
  for var n := 1 to 70 do 
  begin
    var r := bin(n);
    for var i := 1 to 2 do
      if r.CountOf('1') mod 2 = 0 then
        r := r + '0'
      else
        r := r + '1';
    var r10 := dec(r, 2);
    if r10 > 83 then
    begin
      print(r10);
      break;
    end;
  end;
end.

    Python:

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

    x_ = 1
while True:
    x = x_
    sx = str(bin(x))
    sx = sx[2:]
    if sx.count('1') % 2 == 0:
        sx+='0'
    else:
        sx+='1'
    if sx.count('1') % 2 == 0:
        sx+='0'
    else:
        sx+='1'
    x = int(sx, base=2)
    if x > 83 :
        print(x)
        break
    x_+=1

Результат: 86


5_11:

На вход алгоритма подается натуральное число N. Алгоритм строит по нему новое число R следующим образом:

  1. Строится двоичная запись числа 4N.
  2. К этой записи дописываются справа еще два разряда по следующему правилу:
    • складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 10000 преобразуется в запись 100001;
    • над этой записью производятся те же действия — справа дописывается остаток от деления суммы цифр на 2.

    Полученная таким образом запись является двоичной записью искомого числа R.

    Укажите такое наименьшее число N, для которого результат работы алгоритма больше 129. В ответе это число запишите в десятичной системе счисления.

  
Типовые задания для тренировки


    ✎ Решение аналитическим способом:

  • Заметим, что после выполнения второго пункта задания, будут получаться только четные числа! Наименьшим возможным четным числом, превышающим 129, является число 130. С ним и будем работать.
  • Переведем 130 в двоичную систему счисления. Используя компьютер это можно сделать с помощью программистского режима калькулятора. Либо в консоли интерпретатора Python набрать bin(130). Получим:
    • 13010 = 100000102
  • Это двоичное число получилось из исходного двоичного, после того как дважды был добавлен остаток от деления суммы цифр на 2. Т.е.:
    • в обратном порядке:
было 1000001 -> стало 10000010 
еще раз то же самое: 
было 100000 -> стало 1000001
  • Значит, необходимое нам двоичное число — это 100000.
  • Переведем 100000 в 10-ю систему. Для этого можно воспользоваться калькулятором, либо использовать интерпретатор Питона: int('100000',2).
    • 1000002 = 3210
  • Так как по условию у нас 4*N, то 32 делим на 4 — > 8.

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

    PascalAbc.Net:

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

    uses school;
 
begin
  var n_ := 1;
  while True do
  begin
    var n := 4*n_;
    var ost := bin(n).CountOf('1') mod 2; // остаток при делении на 2
    n := 2 * n + ost; //в двоичной с.с. добавляем разряд (*2) и остаток к этому разряру (+ost)
    ost := bin(n).CountOf('1') mod 2; // остаток при делении на 2
    n := 2 * n + ost;
    if n > 129 then
    begin
      println(n_);
      break
    end;
    n_ += 1;
  end;
end.

    Python:

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

    n_ = 1
while True:
    n = 4*n_
    r = str(bin(n))
    r = r[2:]
    for i in range(2):
        if r.count('1') % 2 == 0:
            r+='0'
        else:
            r+='1'
 
    n = int(r, base=2)
    if n > 129:
        print(n_)
        break
    n_+=1

Результат: 8

Комментарии

Отправить комментарий