Задание 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)

№ 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