Задание 5. Анализ алгоритмов для исполнителей

В f-строках  можно применять для перевода десятичных чисел в шестнадцатеричную, восьмеричную , двоичную. Для этого используем синтаксис {переменная:способ записи} как показано в примере ниже:

number = 800

# шестнадцатеричный формат
print(f'{number:x}')

# восьмеричный формат
print(f'{number:o}')

# двоичный формат
print(f'{number:b}')

# 320
# 1440
# 1100100000

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

Данный код:

a = '10100'
b = '41'
c = '21'
a_10 = int(a, 2)
b_10 = int(b, 8)
c_10 = int(c, 16)
print(a_10, b_10, c_10, sep='\n')

выводит

20
33
33

Разумеется, если нам дано число в иной системе счисления в формате int, то для перевода его нужно предварительно перевести в строковый формат, воспользовавшись функцией str(). Приведём пример кода, который осуществляет подобные действия:

a = 12345  # подразумевается, что это восьмеричное число
a = str(a)
b = int(a, 8)
print(b)

def f(x, base):
    s = ''
    while x > 0:
        s = str(x % base) + s
        x = x // base
    return s

x = 800 # перевести число в шестеричную систему
a = f(x, 6)
print(a)

print(int(a, 6))

3412
800

В цикле сначала вычисляется остаток. Далее присоединяем его спереди к строковой переменной s, в которой хранится представление числа в новой системе счисления. Последним действием присваиваем переменной x частное от целочисленного деления прежнего значения x на основание системы счисления.

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

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

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

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

Ответ:

46

Решение

for n in range(1, 100):
    n2 = f'{n:b}'
    for _ in range(2): n2 += str(n2.count('1') % 2)
    if int(n2, 2) > 43: print(int(n2, 2)); break

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

1. Из цифр, образующих десятичную запись N, строятся наибольшее и наименьшее возможные двузначные числа (числа не могут начинаться с нуля).
2. На экран выводится разность полученных двузначных чисел.

Пример. Дано число N = 351. Алгоритм работает следующим образом.

1. Наибольшее двузначное число из заданных цифр: 53, наименьшее: 13.
2. На экран выводится разность 53 – 13 = 40

Чему равно наименьшее возможное трёхзначное число N, в результате обработки которого на экране автомата появится число 40?

Ответ:

115

Решение

from itertools import *
for x in range(100, 1000):
    ans = [int(''.join(x)) for x in permutations(str(x), 2) if x[0] != '0']
    if max(ans) - min(ans) == 40: print(x); break

или

from itertools import *
for x in range(100, 1000):
    ans = []
    for a in permutations(str(x), 2):
        if a[0] != '0':
            c=int(''.join(a))
            
            ans.append(c)
            
    #print(x,max(ans),min(ans))

    if max(ans) - min(ans) == 40:
        print(x)
        break

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

1. Строится троичная запись числа N.
2. Если число N делится на 3, к троичной записи слева приписывается 1, а справа – 02; иначе остаток от деления числа на 3 умножается на 4, переводится в троичную систему и дописывается в конец троичной записи.
3. Полученная таким образом запись является троичной записью искомого числа R.

Например, для числа 11 троичная запись 102 преобразуется в запись 10222 = 107, для числа 12 троичная запись 110 преобразуется в 111002 = 353.

Укажите максимальное значение N, после обработки которого с помощью этого алгоритма получается число R, меньшее чем 199.

Ответ:

20

Решение

def f(x):
    s = ''
    while x > 0:
        s = str(x % 3) + s
        x //= 3
    return s

for n in range(1, 1000):
    n3 = f(n)
    if n % 3 == 0:
        n3 = '1' + n3 + '02'
    else:
        n3 += f(n % 3 * 4)
    if int(n3, 3) < 199:
        print(n)

Задача № 7666

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

1. Число N переводится в двадцатеричную систему счисления.
2. Далее эта запись обрабатывается по следующему правилу:
   1. гласные буквы (A, E, I) заменяются на 1;
   2. в конец полученной записи дописывается остаток от деления числа N на 20 в двадцатеричной системе счисления;
   3. первая цифра переставляется в конец записи.
3. Действия а)-в) в п. 2. повторяются еще раз.

Полученная таким образом запись записью искомого числа R в двадцатеричной системе счисления. Укажите максимальное число R, кратное 2030, которое может быть получено в результате работы алгоритма. Запишите его в ответе в десятичной системе счисления.

Ответ: 63656740

sa = '0123456789ABCDEFGHIJKLMN'

def f(x):
    s = ''
    while x > 0:
        n = x % 20
        s = sa[n] + s
        x = x // 20
    return s

ans = []
for n in range(10000, 100000):
    nn = f(n)
    for _ in range(2):
        for c in 'AEI':
            nn = nn.replace(c, '1')
        nn += sa[n % 20]
        nn = nn[1:] + nn[0]
    r = int(nn, 20)
    if r % 2030 == 0: ans.append(r)
print(max(ans))
 

Перейти на сайт ФИПИ "Открытый банк заданией ЕГЭ"

        Открытый банк заданией ЕГЭ

2.     Раскрыть вкладку "ПОДБОР ЗАДАНИЙ" , в таблице выбрать вариант задания и ввести этот номер в окно "Номер задания"

3.     Решить задание и проверить решение на сайте

Задания открытого банка по информатике

AB1E4C	910419	181BA4	579CE8
B9FDF9	4A5323	1D46A1	84D6E3
C30EF4	A26623	DBC2A3	193F62
930BF4	B2DDDD	65B0A5	A7196F
6E67FD	1157D2	DD38CF	6B6069
722F01	D908DA	D588C0	45033D
D32E0F	C13CDE	C707CC	790E31
915A03	934CD4	89FBC4	ACEE84
4D0976	3C24DE	58BB95	A22587
FE3877	836BD5	ADF799	E99281
D58576	CC6251	324C93	44E412
3FD674	675752	BB72E5	7B8BAC
C412B3	FD04A7	96F41A	0D73A6

№ 49 Джобс 31.08.2020 (Уровень: Базовый)

Автомат обрабатывает натуральное число N по следующему алгоритму:

1.      Строится двоичная запись числа N.
2.      Складываются все цифры полученной двоичной записи. В конец записи (справа) дописывается остаток от деления полученной суммы на 2.
3.      Предыдущий пункт повторяется для записи с добавленной цифрой.
4.      Результат переводится в десятичную систему и выводится на экран.

Пример. Дано число N = 13. Алгоритм работает следующим образом:

1.      Двоичная запись числа N: 1101.
2.      Сумма цифр двоичной записи 3, остаток от деления на 2 равен 1, новая запись 11011.
3.      Сумма цифр полученной записи 4, остаток от деления на 2 равен 0, новая запись 110110.
4.      На экран выводится число 54.

Какое наименьшее число, большее 80, может появиться на экране в результате работы автомата?

Ответ: 86

№ 405 (Уровень: Базовый)

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

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

2) Затем справа дописываются два разряда: символы 01, если число N чётное, и 10, если нечётное.

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

Ответ: 86

№ 549 (Уровень: Базовый)

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

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

2) К этой записи дописывается (дублируется) последняя цифра.

3) Затем справа дописывается бит чётности: 0, если в двоичном коде полученного числа чётное число единиц, и 1, если нечётное.

4) К полученному результату дописывается ещё один бит чётности.

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

Ответ: 17

№ 557 (Уровень: Базовый)

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

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

2) К этой записи дописывается (дублируется) последняя цифра.

3) Затем справа дописывается бит чётности: 0, если в двоичном коде полученного числа чётное число единиц, и 1, если нечётное.

4) К полученному результату дописывается ещё один бит чётности.

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

Ответ: 156

№ 561 (Уровень: Средний)

Автомат обрабатывает натуральное число N по следующему алгоритму:

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

2. В конец записи (справа) дописывается остаток от деления числа N на 3.

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

Пример. Дано число N=11. Алгоритм работает следующим образом:

1. Троичная запись числа N: 102

2. Остаток от деления 11 на 3 равен 2, новая запись 1022

3. На экран выводится число 35.

Какое наименьшее трёхзначное число может появиться на экране в результате работы автомата?

Ответ: 103

№ 563 (Уровень: Средний)

Автомат обрабатывает натуральное число N по следующему алгоритму:

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

2. Запись «переворачивается», то есть читается справа налево. Если при этом появляются ведущие нули, они отбрасываются.

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

Пример. Дано число N = 58. Алгоритм работает следующим образом:

1. Двоичная запись числа N: 111010.

2. Запись справа налево: 10111 (ведущий ноль отброшен).

3. На экран выводится десятичное значение полученного числа 23.

Какое наибольшее число, не превышающее 100, после обработки автоматом даёт результат 13?

Ответ: 88

№ 553 (Уровень: Базовый)

Автомат обрабатывает натуральное число N по следующему алгоритму:

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

2. Складываются все цифры полученной двоичной записи. В конец записи (справа) дописывается остаток от деления полученной суммы на 2.

3. Предыдущий пункт повторяется для записи с добавленной цифрой.

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

Сколько различных чисел, меньших 80, могут появиться на экране в результате работы автомата?

Ответ: 19

№ 1732 (Уровень: Базовый)

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

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

2) К этой записи дописываются справа ещё два разряда по следующему правилу:

а) складываются все цифры двоичной записи числа 2N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 10000 преобразуется в запись 100001;

б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2.

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

Ответ: 127

№ 1849 Основная волна 2021 (Уровень: Базовый)

Автомат обрабатывает натуральное число N по следующему алгоритму:

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

2. Если N четное, то в конец полученной записи (справа) дописывается 0, в начало – 1; если N – нечётное в конец и начало дописывается по две единицы.

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

Пример. Дано число N = 13. Алгоритм работает следующим образом:

1. Двоичная запись числа N: 1101.

2. Число нечетное, следовательно по две единицы по краям – 11110111.

3. На экран выводится число 247.

Укажите наименьшее число, большее 52, которое может являться результатом работы автомата.

Ответ: 56

№ 4610 Основная волна 2022 (Уровень: Базовый)

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

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

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

а) если сумма цифр в двоичной записи числа чётная, то к этой записи справа дописывается 0, а затем два левых разряда заменяются на 10;

б) если сумма цифр в двоичной записи числа нечётная, то к этой записи справа дописывается 1, а затем два левых разряда заменяются на 11.

Полученная таким образом запись является двоичной записью искомого числа R. Например, для исходного числа 6 → 110 результатом является число 1000 → 8, а для исходного числа 4 → 100 результатом является число 1101 → 13. Укажите максимальное число N, после обработки которого с помощью этого алгоритма получается число R, меньшее 35. В ответе запишите это число в десятичной системе счисления. 

Ответ: 24

№ 9828 Основная волна 27.06.23 (Уровень: Средний)

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится троичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число N делится на 3, то слева к троичной записи приписывается «1», а справа «02»;
6) если число N на 3 не делится, то остаток от деления на 3 умножается на 4, переводится в троичную запись и дописывается в конец троичной записи.
Полученная таким образом запись является троичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа 11 → 102 результатом является число 10222 → 107, а для исходного числа 12 → 110 это число 111002 → 353.
Укажите максимальное число N, после обработки которого с помощью этого алгоритма получается число R, меньшее 199.

Ответ: 20

№ 10707 (Уровень: Средний)

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

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

Например, для исходного числа 1110 результатом является число 41610, а для исходного числа 1210 это число 44410.

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

Ответ: 694

№ 4869 (Уровень: Сложный)

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

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

2 Вычисляется количество единиц, стоящих на чётных местах в двоичной записи числа N без ведущих нулей, и количество нулей, стоящих на нечётных местах. Места отсчитываются слева направо (от старших разрядов к младшим, начиная с единицы).

3 Результатом работы алгоритма становится модуль разности полученных двух чисел.

Пример. Дано число N = 39 Алгоритм работает следующим образом:

1 Строится двоичная запись: 39 → 100111

2 Выделяем единицы на чётных и нули на нечётных местах: 100111

На чётных местах стоят две единицы, на нечётных – один ноль.

3 Модуль разности равен 1

Результат работы алгоритма R = 1

При каком наименьшем N в результате работы алгоритма получится R = 5?

Ответ: 1023

Источник: https://kompege.ru/course