Задача. На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число N чётно, то справа приписывается «01»;
б) если число N нечётно, то к этой записи слева приписывается 1 и справа приписывается «01».
Полученная таким образом запись является двоичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Укажите минимальное число R, большее 150, которое может быть получено в результате обработки натурального числа N. В ответе запишите это число в десятичной системе счисления.
Приведем решение задачи на языках Паскаль и Python. В программе на языке Паскаль будем использовать функции модуля school для перевода чисел в двоичную/десятичную системы счисления (подобная задача ранее разбиралась в данном блоге).
Как будем решать задачу
- Запустим цикл по натуральному числу N от 1 до 100 (правая граница промежутка изменяемая, будем проводить эксперимент).
- Число N переведем в двоичную систему счисления.
- Обработаем двоичную запись числа в соответствие с алгоритмом.
- Полученную двоичную запись переведем в десятичную систему счисления R.
- Если 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
