Задание 5
тема 1 из 3

Алгоритмы, которые меняют запись числа

В задании 5 алгоритм строит двоичную или другую запись числа N, дописывает, заменяет или удваивает её цифры и получает число R. Программа повторяет алгоритм в функции над строкой и перебирает N, а вопрос решает условие в цикле: наименьшее N, наибольшее N или наименьший возможный результат R. Короткие правила, например дописывание битов чётности, решаются и вручную: дописать цифру справа значит умножить число на основание и прибавить цифру.

Главная тема в задании5На карте навыков

Как решать задание 5

Алгоритм превращает число NN в число RR через запись в системе счисления. KK — число из вопроса задачи.

  • Функция R(n): запись s = bin(n)[2:], действия над строкой s, результат int(s, 2).
  • Наименьшее NN, при котором RR больше KK: цикл по NN вверх, первое подходящее NN — ответ.
  • Наибольшее NN, при котором RR меньше KK: перебор всех NN до KK, запоминается последнее подходящее.
  • Наименьшее возможное RR, большее KK: соберите все результаты и возьмите наименьший из подходящих.
  • Вручную: дописать цифру dd справа к P-ичной записи — получить N⋅P+dN \cdot P + d.

Запись числа как строка

Алгоритм задания 5 меняет запись числа, поэтому в программе запись хранят строкой. bin(n)[2:] — двоичная запись без приставки 0b. Над строкой работают срезы и методы: s + '01' дописывает цифры справа, '1' + s — слева, s[2:] отрезает два левых разряда, s[-2:] — две последние цифры, s.count('1') — число единиц, то есть сумма цифр двоичной записи. Середина строки длины LL — позиция L // 2: s[:L // 2] + '1' + s[L // 2:] вставляет 1 в середину.

Готовую строку переводят в число функцией int(s, 2). Перевод и приставки bin — в теме позиционные системы счисления.

Пример

К двоичной записи числа N=13N = 13 справа дописывают остаток от деления суммы её цифр на 2. Затем то же делают с новой записью. Найдите результат RR.

  1. 1.13=1101213 = 1101_2, единиц три, остаток 1: запись 1101111011.
  2. 2.В новой записи единиц четыре, остаток 0: запись 110110110110.
  3. 3.R=1101102=32+16+4+2=54R = 110110_2 = 32 + 16 + 4 + 2 = 54. Программа печатает 110110 54.

Ответ: 5454

Дописывание разрядов вручную

Дописать к P-ичной записи числа NN цифру dd справа — значит получить N⋅P+dN \cdot P + d: все цифры сдвигаются на разряд влево. Дописать справа две двоичные цифры — получить 4N4N плюс значение этих цифр. Дописать цифры слева к числу из kk цифр — прибавить их значение, умноженное на PkP^k. Эти правила разобраны в теме позиционные системы счисления.

Частый алгоритм — два бита чётности: дважды дописывают остаток от деления суммы цифр на 2. Если в записи NN единиц чётное число, дописываются 0 и 0, и R=4NR = 4N. Если нечётное, дописываются 1 и 0, и R=4N+2R = 4N + 2. Значит, RR всегда чётно и в его записи всегда чётное число единиц.

Пример задания

Открытый банк ФИПИ

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

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

Например, для исходного числа 1210 = 11002 результатом является число 1100002 = 4810, а для исходного числа 710 = 1112 это число 111102 = 3010.

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

Программа: наименьшее N

Функция R(n) повторяет алгоритм шаг за шагом: строит запись, проверяет условие правила через if и меняет строку. Цикл for n in range(1, 1000) перебирает NN по возрастанию. Первое NN, при котором условие на RR верно, — наименьшее, и цикл останавливает break.

Сначала проверьте функцию на примерах из условия: она должна давать те же RR. Читайте вопрос точно: «больше» — знак >, «не меньше» — знак >=.

Пример

Строится двоичная запись числа NN. Если NN чётное, к записи справа дописывают 01. Если нечётное, слева дописывают 11. Получается двоичная запись числа RR. Найдите наименьшее NN, при котором RR больше 100.

  1. 1.Проверка функции: 4=1002→100012=174 = 100_2 \to 10001_2 = 17, 5=1012→111012=295 = 101_2 \to 11101_2 = 29.
  2. 2.Цикл идёт по NN от 1. Все RR до N=16N = 16 не больше 100: R(16)=10000012=65R(16) = 1000001_2 = 65.
  3. 3.N=17=100012N = 17 = 10001_2 нечётное: 11100012=1131110001_2 = 113, это больше 100. Программа печатает 17.

Ответ: 1717

Наименьший результат R, больший K

Вопрос «укажите наименьшее число RR, большее KK, которое может получиться» спрашивает о результате, а не об NN. Перебирайте NN, считайте RR и оставьте только те RR, которые больше KK. Ответ — наименьшее из них: min(R(n) for n in range(1, 1000) if R(n) > K). Результат растёт не всегда вместе с NN, поэтому первое найденное RR не обязательно наименьшее.

Вручную помогает длина записи. Если алгоритм удлиняет запись на известное число цифр, найдите, сколько цифр должно быть у RR, и подберите наименьшую запись такой длины, которую алгоритм может дать.

Пример задания

Открытый банк ФИПИ

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

1) Строится двоичная запись числа N.
2) Каждый разряд этой записи заменяется двумя разрядами по следующему правилу: если в разряде стоит 0, то вместо него пишется 00; если в разряде стоит 1, то 1 заменяется на 11.
Например, двоичная запись 1001 числа 9 будет преобразована в 11000011.

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

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

Если алгоритм строит запись в системе с основанием PP, функции bin нет. Запись строит цикл деления на PP из темы позиционные системы счисления, его оформляют отдельной функцией. Результат переводят обратно через int(s, p). Сумма цифр P-ичной записи — sum(int(c) for c in s).

Число, которое дописывают в конец, тоже сначала переводят в систему PP. Если оно не меньше PP, его запись займёт две цифры: в четверичной системе 2=242 = 2_4, а удвоенный остаток 6=1246 = 12_4.

Пример

Строится четверичная запись числа NN. Справа к ней дописывают остаток от деления суммы её цифр на 4. Получается четверичная запись числа RR. Найдите наименьшее NN, при котором RR больше 200.

  1. 1.Дописывание одной цифры даёт R=4N+dR = 4N + d, где dd от 0 до 3. RR больше 200 не раньше N=50N = 50.
  2. 2.50=302450 = 302_4, сумма цифр 5, остаток 1: 30214=192+8+1=2013021_4 = 192 + 8 + 1 = 201.
  3. 3.Программа перебирает NN с функцией to4 и печатает 50.

Ответ: 5050

Программа: наибольшее N

Если нужно наибольшее NN, при котором RR меньше KK, цикл не останавливают на первом подходящем числе. Он проходит весь диапазон, а переменная best запоминает каждое подходящее NN. После цикла в ней последнее, то есть наибольшее. Алгоритм только дописывает цифры, поэтому RR больше NN, и перебор NN до KK ничего не пропускает.

Пример задания

Открытый банк ФИПИ

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

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

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

Например, для исходного числа 11 = 234 результатом является число 23124 = 182, а для исходного числа 12 = 304 это число 30304 = 204.
Укажите максимальное число N, после обработки которого с помощью этого алгоритма получается число R, меньшее 261.

Автомат над десятичными цифрами

Другой вид задания 5: автомат берёт цифры трёхзначного числа, считает из них два числа (суммы квадратов, произведение, сумму) и записывает их подряд в порядке невозрастания. Цифры числа дают n // 100, n // 10 % 10 и n % 10: цифры числа.

Вручную результат разрезают на два числа: левое не меньше правого, и оба не больше наибольшего возможного значения (сумма квадратов двух цифр не больше 81+81=16281 + 81 = 162). Затем подбирают цифры. Для наибольшего исходного числа ставят большую цифру в старший разряд. Программа перебирает все числа от 100 до 999 и запоминает последнее, которое даёт нужный результат.

Пример задания

Открытый банк ФИПИ

Автомат получает на вход трёхзначное число. По этому числу строится новое число по следующим правилам:

1) Вычисляются суммы квадратов первой и второй, а также второй и третьей цифр исходного числа.
2) Полученные два числа записываются друг за другом в порядке невозрастания (без разделителей).

Пример. Исходное число: 621. Суммы квадратов цифр: 62+22=40;22+12=5.6^{2} + 2^{2} = 40 ; 2^{2} + 1^{2} = 5 . Результат: 405.
Укажите наибольшее число, при обработке которого автомат выдаст число 9752.

Потренируйте навык

Все задания на этот навык

Решать