Задание 5. ЕГЭ по информатике. На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R

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

1.    Строится двоичная запись числа N.

2.    Далее эта запись обрабатывается по следующему правилу:

а) если число N чётно, то справа приписывается «01»;

б) если число N нечётно, то к этой записи слева приписывается 1 и справа приписывается «01».

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

3.    Результат переводится в десятичную систему и выводится на экран.

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

Приведем решение задачи на языках Паскаль и Python. В программе на языке Паскаль будем использовать функции модуля school для перевода чисел в двоичную/десятичную системы счисления (подобная задача ранее разбиралась в данном блоге).

Как будем решать задачу

1. Запустим цикл по натуральному числу N от 1 до 100 (правая граница промежутка изменяемая, будем проводить эксперимент).
2. Число N переведем в двоичную систему счисления.
3. Обработаем двоичную запись числа в соответствие с алгоритмом.
4. Полученную двоичную запись переведем в десятичную систему счисления R.
5. Если R>150, выведем таблицу значений N и R на экран.

Далее проанализируем полученные результаты, нам необходимо найти наименьший результат, больший 150, для какого-либо N.

Программа решения задачи на языке Паскаль

uses school;

var n,r:integer; b:string;

begin

  for n:=1 to 100 do

  begin

    b:=bin(n);

    if n mod 2 = 0 then b:=b + '01'

    else b:='1'+b+'01';

    r:=dec(b, 2);

    if r>150 then println(n,r);

  end;

end.

Запустим программу для промежутка чисел N от 1 до 100. Обратим внимание, что по мере возрастания числа N, результаты R ведут себя произвольно, первое по счету R, очевидно, не является ответом. Необходимо выполнить эксперимент и запускать цикл по числу N до 200, 300, наблюдать, как ведут себя результаты (>150). Ответом является число 153.

Ответ: 153

В программу на языке Python внесем изменения: запустим цикл до 1000 и сохраним результаты, большие 150, в список, в качестве ответа возьмем минимум. Можно увеличивать правую границу и видеть, что минимум не меняется.

Программа решения задачи на языке Python

a = []

for n in range(1,1001):

    b = bin(n)[2:]

    if n % 2 == 0:

        b = b + '01'

    else:

        b = '1' + b + '01'

    r = int(b, 2)

    if r>150:

        a.append(r)

        #print(n, r)

print(min(a))

Ответ: 150