Если по условию нужно найти R
m = <контрзначение>
# перебираем всевозможные N
for N in range(1, 1000):
# переводим N в двоичную СС
N_2 = bin(N)[2:]
<делаем проверки на N, формируем число R2>
# переводим результат в десятичную СС
R = int(R2, 2)
# делаем проверку на R
if R <условие из задания>:
m = max(m, R)
# min(m, R)
print(m)
Если по условию нужно найти N
# перебираем всевозможные N
for N in range(1, 1000):
# переводим N в двоичную СС
N_2 = bin(N)[2:]
<делаем проверки на N, формируем число R2>
# переводим результат в десятичную СС
R = int(R2, 2)
# делаем проверку на R
if R <условие из задания>:
print(N)
# если нужно найти наименьшее N
break
Правила для N:
Если N четное/ нечетное, то…
if N % 2 == 0:
<формируем R2 для четного N>
else:
<формируем R2 для нечетного N
Если сумма цифр в двоичной записи числа четная/ нечетная, то…
if N2.count('1') % 2 == 0:
<формируем R2 для четной суммы цифр>
else:
<формируем R2 для нечетной суммы цифр>
Правила для R:
В начало и конец добавляется по единице
R2 = '1' + N2 + '1'
Первые две цифры двоично записи заменяются на «11»
R2 = '11' + N2[2:]
В конец добавляются три последние цифры двоичной записи числа N
R2 = N2 + N2[-3:]
Остаток от деления N на 3 умножается на 5, переводится в двоичную СС и дописывается в конец числа
ost=bin((N % 3) * 5)
R2 = N2 + ost
Прототипы с ЕГЭ
Задача №1 На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите такое наименьшее число N, для которого результат работы данного алгоритма больше числа 77.
Ответ: 19
Задача №2 На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1. Строится двоичная запись числа N. 2. Далее эта запись обрабатывается по следующему правилу:
а) если сумма цифр в двоичной записи числа чётная, то к этой записи справа дописывается 0, а затем два левых разряда заменяются на 10;
б) если сумма цифр в двоичной записи числа нечётная, то к этой записи справа дописывается 1, а затем два левых разряда заменяются на 11.
Полученная таким образом запись является двоичной записью искомого числа R.
Например, для исходного числа 610 = 1102 результатом является число 10002 = 810, а для исходного числа 410 = 1002 результатом является число 11012 = 1310.
Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, не меньшее, чем 16.
Ответ: 8
Задача №3
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число чётное, то к двоичной записи числа слева дописывается 10;
6) если число нечётное, то к двоичной записи числа слева дописывается 1 и справа дописывается 01.
Полученная таким образом запись является двоичной записью искомого числа R.
Например, для исходного числа 410 = 1002, результатом является число 2010 = 101002, а для исходного числа 510 = 1012 результатом является число 5310 = 1101012
Укажите максимальное число R, которое может быть результатом работы данного алгоритма, при условии, что N не больше 8. В ответе запишите это число в десятичной системе счисления.
Ответ: 61
Задача №4 На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится троичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число N делится на 3, то к этой записи дописываются две последние троичные цифры;
б) если число N на 3 не делится, то остаток от деления умножается на 5, переводится в троичную запись и дописывается в конец числа. Полученная таким образом запись является троичной записью искомого числа R. 3. Результат переводится в десятичную систему и выводится на экран. Например, для исходного числа 11 = 1023 результатом является число 1021013 = 307, а для исходного числа 12 = 1103 это число 110103 = 111.
Укажите минимальное число R, большее 133, которое может быть получено с помощью описанного алгоритма. В ответе запишите это число в десятичной системе счисления.
Ответ: 141
Задания уровня ЕГЭ
Задача №1 У исполнителя Утроитель две команды, которым присвоены номера:
1. прибавь 1,
2. умножь на 3.
Первая из них увеличивает число на экране на 1, вторая – утраивает его.
Запишите порядок команд в программе преобразования числа 1 в число 22, содержащей не более 5 команд, указывая лишь номера команд. (Например, 21211 – это программа
умножь на 3
прибавь 1
умножь на 3
прибавь 1
прибавь 1,
которая преобразует число 1 в 14.)
(Если таких программ более одной, то запишите любую из них.)
Ответ: 12121
Задача №2 На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи справа дописываются разряды по следующему правилу.
Если число кратно 3, то дописывается 010, иначе в конец дописывается двоичная последовательность, являющаяся результатом умножения 5 на остаток от деления числа N на 3. Например, для числа 13 двоичная запись 1101 преобразуется в запись 1101101, для числа 9 двоичная запись 1001 преобразуется в 1001010. Полученная таким образом запись является двоичной записью искомого числа R.
Укажите значение N, в результате обработки которого будет получено минимально возможное четное значение R, большее 300. Если таких значений несколько, приведите минимальное подходящее значение.
Ответ: 39
Задача №3 (6588) Автомат обрабатывает натуральное число N по следующему алгоритму.
1. Строится двоичная запись числа N.
2. Все значащие цифры инвертируются (‘0’ заменяется на ‘1’, а ‘1’ на ‘0’). 3. К полученному результату слева добавляется ‘1’. 4. К двоичной записи полученного числа справа дописывается бит четности: ‘1’, если количество единиц в двоичной записи нечетно, ‘0’ - если четно. 5. Полученное в результате этих операций число переводится в десятичную систему счисления. Полученная таким образом запись является результатом работы алгоритма: R.
Укажите такое наименьшее число N, для которого результат работы данного алгоритма больше числа 180. В ответе это число запишите в десятичной системе счисления.
Ответ: 32
Задача №4 На вход алгоритма подаётся натуральное число N>8. Алгоритм строит по нему новое число R следующим образом.
1. Из числа N вычитается остаток от деления N на 8.
2. Строится двоичная запись этого результата 3.
К этой записи дописываются справа ещё два разряда по следующему правилу: складываются все цифры построенной двоичной записи; если сумма чётная, то в конец числа (справа) дописывается 00, если сумма нечётная то в конец числа (справа) дописывается 01.
Полученная таким образом запись является двоичной записью искомого числа R.
Укажите максимальное число N, для которого результат работы алгоритма меньше 353.
Ответ: 87
Задача №5 Автомат обрабатывает натуральное число N (128≤N≤255) но следующему алгоритму:
1. Строится восьмибитная двоичная запись числа N.
2. Все цифры двоичной записи заменяются на противоположные (0 на 1, 1 на 0).
3. Полученное число переводится в десятичную запись.
4. Из исходного числа вычитается полученное, разность выводится на экран.
Пример. Дано число N = 131. Алгоритм работает следующим образом:
1. Восьмибитная двоичная запись числа N: 10000011.
2. Все цифры заменяются на противоположные, новая запись: 01111100.
3. Десятичное значение полученного числа: 124.
4. На экран выводится число: 131 - 124 = 7.
Какое число нужно ввести в автомат, чтобы в результате получилось 105?
Ответ: 180
Задача №6 Автомат получает на вход трехзначное число. По этому числу строится новое число по следующим правилам.
1. Умножаются первая и вторая, а также вторая и третья цифры исходного числа.
2. Полученные два числа записываются друг за другом в порядке убывания (без разделителей).
Пример. Исходное число: 543. Произведения: 5 * 4 = 20; 4 * 3 = 12.
Результат: 2012.
Укажите максимальное число, в результате обработки которого, автомат выдаст число 240.
Ответ: 830
