Тема 5. Алгоритмы – анализ простейших алгоритмов

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

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела алгоритмы – анализ простейших алгоритмов

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#30303

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

1) Строится шестнадцатеричная запись числа $N∕∕2$ , где « $∕∕$ » — операция деления нацело.

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

а) если $N$ не делится на 4, то слева к нему приписывается « $F$ », а справа « $A0$ ».

б) в противном случае слева приписывается « $15$ », а справа « $C$ ».

Например, $N = 410 ⇒ 216 ⇒ 152C16 = 542010 = R$ .

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

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

Показать ответ и решение

def f_16(n):
    x = n
    s = ’’
    while x > 0:
        h = x % 16
        if h > 9:
            s = chr(55 + h) + s  # По табличке ASCII
        else:
            s = str(h) + s
        x //= 16
    return s
for i in range(1000000, 0, -1):
    s = f_16(i // 2)
    if i % 4 != 0: s = ’F’ + s + ’A0’
    else: s = ’15’ + s + ’C’
    if int(s, 16) < 1048576:
        print(i)
        break

Ответ: 511

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#57743

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. В четверичной записи числа N дублируется последняя цифра.
2. Получившееся число переводится в двоичное представление.
3. В получившейся записи дублируется последняя цифра.
4. Полученное в результате этих операций число переводится в десятичную систему счисления.

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

Показать ответ и решение

mx = 0
for n in range(1, 300):
    f = ’’
    while n > 0:
        f = str(n % 4) + f
        n = n // 4
    f += f[-1]
    b = bin(int(f, 4))[2:]
    b += b[-1]
    r = int(b, 2)
    if r < 280:
        mx = max(r, mx)
print(mx)

Ответ: 276

Ошибка.
Попробуйте повторить позже

Задача 3#60020

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

Строится семиричная запись числа N
В начало записи (слева) дописывается остаток от деления числа N на 5, а в конец записи (справа) остаток от деления N на 3.
Результат переводится из семиричной системы в десятичную и выводится на экран.

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

Показать ответ и решение

for n in range(1, 1000):
    s = ’’
    x = n
    while x > 0:
        s = str(x % 7) + s
        x = x // 7
    s = str(n % 5) + s + str(n % 3)
    r = int(s, 7)
    if len(str(r)) == 3:
        print(r)

Ответ: 982

Ошибка.
Попробуйте повторить позже

Задача 4#63913

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

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

2) Инвертируются все разряды исходного числа, кроме последней единицы и стоящих за ней нулей (0 заменяется на 1, 1 на 0).

3) Полученное число переводится в десятичную систему счисления.

Для какого значения N результат работы алгоритма равен 98?

Показать ответ и решение

for number in range(256):
    binary_number = bin(number)[2:]
    new_bin = ’’
    for i in range(len(binary_number)):
        if binary_number[i] == ’1’ and binary_number[i+1:].count(’1’) == 0:
            new_bin += binary_number[i:]
            break
        else:
            if binary_number[i] == ’1’:
                new_bin += ’0’
            else:
                new_bin += ’1’
    decimal_result = int(new_bin, 2)

    if decimal_result == 98:
        print(number)

Ответ: 158

Ошибка.
Попробуйте повторить позже

Задача 5#72185

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

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

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

а) если остаток от деления числа $N$ на 5 чётный, то к этой записи справа дописываются два нуля.

б) если остаток от деления числа $N$ на 5 нечётный, то к этой записи справа дописывается единица.

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

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

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

Показать ответ и решение

ans= []
for n in range(1,1000):
    t = bin(n)[2:]
    if (n % 5) % 2 == 0:
        t += ’00’
    else:
        t += ’1’
    r = int(t,2)
    if r > 300:
        ans += [r]
print(min(ans))

Ответ: 303

Ошибка.
Попробуйте повторить позже

Задача 6#72428

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

Строится троичная запись числа N.
К этой записи дописывается справа бит по определённым правилам: 0, если в троичном коде числа $N$ сумма количества единиц и двоек чётна, и 1, если сумма количества единиц и двоек нечётна.
К полученному результату дописывается ещё один бит по тем же правилам.

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

Показать ответ и решение

def tr(n):
    x = n
    s = ’’
    while x > 0:
        s = str(x % 3) + s
        x = x // 3
    return s

mn = 10**10
for n in range(1, 100):
    t = tr(n)
    if (t.count(’1’)+t.count(’2’)) % 2 == 0:
        t += ’0’
    else:
        t += ’1’

    if (t.count(’1’)+t.count(’2’)) % 2 == 0:
        t += ’0’
    else:
        t += ’1’

    if int(t, 3) > 337:
        mn = min(mn, int(t, 3))

print(mn)

Ответ: 345

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#75227

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

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

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

а) если число N дает остаток 0 или 1 при делении на 3, то к этой записи справа дописываются две первые цифры двоичной записи числа N;

б) если число N дает остаток 2 при делении на 3, то считается количество нулей в этой записи, это количество переводится в двоичную запись и дописывается в конец числа.

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

Например, для исходного числа $1210 = 11002$ результатом является число $1100112 = 5110$ , а для исходного числа $510 = 1012$ результатом является число $10112 = 1110$ .

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

Показать ответ и решение

for n in range(1, 150):
    s = bin(n)[2:]  # Переводим число в двоичную систему счисления
    if n % 3 == 0 or n % 3 == 1:  # Если число n дает остаток 0 или 1 при делении на 3,
        s += s[0:2]  # то приписываем две единицы двоичной записи.
    if n % 3 == 2:  # Если число n дает остаток 2 при делении на 3,
        k = s.count(’0’)  # то считаем количество нулей в числе.
        s1 = bin(k)[2:]  # Переводим это количество в двоичную сс
        s += s1  # Прибавляем это число к двоичной записи числа
    r = int(s, 2)
    if r > 122:
        print(n)
        break  # Первое выведенное значение будет минимальным

Ответ: 30

Ошибка.
Попробуйте повторить позже

Задача 8#75228

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

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

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

а) если число N делится на 5, то к этой записи справа дописывается 02;

б) если число N не делится на 5, то остаток от деления умножается на 3, это произведение переводится в троичную систему счисления, от него берется две последние цифры и дописываются в конец числа.

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

Например, для исходного числа $1210 = 1103$ результатом является число $110203 = 11410$ , а для исходного числа $510 = 123$ результатом является число $12023 = 4710$ .

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

Показать ответ и решение

def f(n, osn): #функция перевода числа n в сс с основанием osn
    s = ’’
    while n > 0:
        s += str(n % osn)
        n //= osn
    s = s[::-1]
    return s

for n in range(1, 300):
    s = f(n, 3) #переводим число в троичную систему счисления
    if n % 5 == 0: #если число n делится на 5
        s += ’02’ #то приписываем 02
    if n % 5 != 0:  #если число n не делится на 5
        k = (n % 5) * 3 #то считаем остаток от деления на 5, умноженный на 3
        s1 = f(k,3) #переводим это число в троичную сс
        s += s1[len(s1)-2:] #прибавляем последние две цифры этого числа к троичной записи числа
    r = int(s, 3)
    if r == 192:
        print(n)
        break

Ответ: 21

Ошибка.
Попробуйте повторить позже

Задача 9#75229

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

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

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

а) если в троичной записи числа содержится хотя бы одна цифра 2, то к этой записи справа дописывается 0;

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

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

Например, для исходного числа $1210 = 1103$ результатом является число $11013 = 3710$ , а для исходного числа $510 = 123$ результатом является число $1203 = 1510$ .

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

Показать ответ и решение

def f(n, osn): #функция перевода числа n в сс с основанием osn
    s = ’’
    while n > 0:
        s += str(n % osn)
        n //= osn
    s = s[::-1]
    return s

a = set()
for n in range(1, 200):
    s = f(n, 3) #переводим число в троичную систему счисления
    if ’2’ in s: #если в троичной записи содержится хотя бы одна двойка
        s += ’0’ #то приписываем 0
    if ’2’ not in s:  #если в троичной записи нет двойки
        k = (n % 10)//2 #то берем последнюю цифру числа n и делим нацело на 2
        s1 = f(k,3) #переводим это число в троичную сс
        s += s1 #прибавляем к троичной записи числа
    r = int(s, 3)
    if r >= 202:
        a.add(r)
print(min(a))

Ответ: 204

Ошибка.
Попробуйте повторить позже

Задача 10#75230

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

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

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

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

б) если число N дает нечетный остаток при делении на 5, то к этой записи слева дописывается 21.

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

Например, для исходного числа $1210 = 225$ результатом является число $2245 = 6410$ , а для исходного числа $610 = 115$ результатом является число $21115 = 28110$ .

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

Показать ответ и решение

def f(n, osn): #функция перевода числа n в сс с основанием osn
    s = ’’
    while n > 0:
        s += str(n % osn)
        n //= osn
    s = s[::-1]
    return s

for n in range(1, 200):
    s = f(n, 5) #переводим число в пятеричную систему счисления
    if n % 5 == 0 or n % 5 == 2 or n % 5 == 4: #если n дает четный остаток при делении на 5
        k = sum(map(int, s)) #считаем сумму цифр в строке
        s1 = f(k, 5) #переводим в пятеричную сс
        s += s1 #приписываем полученное значение к записи
    if n % 5 == 1 or n % 5 == 3:   #если n дает нечетный остаток при делении на 5
        s = ’21’ + s #дописываем слева к пятеричной записи числа 21
    r = int(s, 5)
    if r <= 320:
        print(n)

Ответ: 60

Ошибка.
Попробуйте повторить позже

Задача 11#75231

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

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

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

а) если в записи числа больше четных цифр, то складывается сумма всех четных цифр в записи числа, переводится в восьмеричную систему счисления и дописывается в конец числа;

б) если в записи числа больше нечетных цифр, то складывается сумма всех нечетных цифр в записи числа, переводится в восьмеричную систему счисления и дописывается в конец числа;

в) если в записи числа одинаковое количество четных и нечетных цифр, то складывается сумма всех четных цифр в записи числа и делится нацело на 2, затем переводится в восьмеричную систему счисления и дописывается в конец числа;

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

Например, для исходного числа $12 = 14 10 8$ результатом является число $142 = 98 8 10$ , а для исходного числа $7210 = 1108$ результатом является число $11028 = 57810$ .

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

Показать ответ и решение

for n in range(1, 1000):
    t = oct(n)[2:]  # Перевод числа в восьмеричную систему счисления
    count_even = t.count(’0’) + t.count(’2’) + t.count(’4’) + t.count(’6’)  # Подсчёт чётных цифр в числе
    count_odd = t.count(’1’) + t.count(’3’) + t.count(’5’) + t.count(’7’)  # Подсчёт нечётных цифр в числе
    sum_digits = 0  # Переменная для суммы цифр
    if count_even > count_odd:  # Если чётных цифр больше
        for i in t:  # Складываем чётные цифры записи
            if int(i) % 2 == 0:
                sum_digits += int(i)
        t += oct(sum_digits)[2:]  # Добавляем к числу восьмеричную запись суммы чётных цифр
    elif count_odd > count_even:  # Если нечётных цифр больше
        for i in t:  # Складываем нечётные цифры записи
            if int(i) % 2 != 0:
                sum_digits += int(i)
        t += oct(sum_digits)[2:]  # Добавляем к числу восьмеричную запись суммы нечётных цифр
    else:  # Если количество цифр равно
        for i in t:  # Складываем чётные цифры записи
            if int(i) % 2 == 0:
                sum_digits += int(i)
        t += oct(sum_digits // 2)[2:]  # Добавляем к числу восьмеричную запись суммы чётных цифр, делённую на 2
    r = int(t, 8)  # Перевод в 10сс из 8сс
    if r <= 870:
        print(n)

Ответ: 108

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 12#75232

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

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

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

а) если число N делится на 4, то к этой записи слева дописывается 1;

б) если число N не делится на 4, то к этой записи справа дописывается 1.

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

Например, для исходного числа $1210 = 148$ результатом является число $1148 = 7610$ , а для исходного числа $6110 = 758$ результатом является число $7518 = 48910$ .

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

Показать ответ и решение

a = set()
for n in range(1, 200):
    s = oct(n)[2:]  # переводим число в восьмеричную систему счисления
    if n % 4 == 0:  # если число делится на 4
        s = ’1’ + s  # дописываем слева 1
    if n % 4 != 0:  # если число не делится на 4
        s = s + ’1’  # дописываем справа 1
    r = int(s, 8)
    if 590 < r and r < 650:
        a.add(r)
print(len(a))

Ответ: 21

Ошибка.
Попробуйте повторить позже

Задача 13#75233

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

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

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

а) если произведение цифр записи, отличных от 0, кратно 3, то к этой записи справа дописывается 21;

б) если произведение цифр записи, отличных от 0, не кратно 3, то к этой записи справа дописывается 12.

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

Например, для исходного числа $1210 = 304$ результатом является число $30214 = 20110$ , а для исходного числа $510 = 114$ результатом является число $11124 = 8610$ .

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

Показать ответ и решение

def f(n, osn): #функция перевода числа n в сс с основанием osn
    s = ’’
    while n > 0:
        s += str(n % osn)
        n //= osn
    s = s[::-1]
    return s
a = set()
for n in range(1, 200):
    s = f(n, 4) #переводим число в четверичную систему счисления
    k = map(int,s)
    mult = 1 #произведение цифр в четверичной записи числа
    for i in k: # считаем прозведение
        if i != 0:
            mult *= i
    if mult % 3 == 0: #если произведение делится на 3 без остатка
        s += ’21’ #приписываем 21 к записи
    if mult % 3 != 0:   #если произведение не делится на 3 без остатка
        s += ’12’ #приписываем 12 к записи
    r = int(s, 4)
    if r <= 280:
        a.add(r)
print(max(a))

Ответ: 278

Ошибка.
Попробуйте повторить позже

Задача 14#75234

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

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

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

а) если целая часть среднего значения цифр в числе N больше 5, то к записи в начало дописывается 1;

б) если целая часть среднего значения цифр в числе N меньше или равно 5, то к записи в начало дописывается 2.

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

Например, для исходного числа $3410 = 2216$ результатом является число $22216 = 54610$ , а для исходного числа $5610 = 3816$ результатом является число $23816 = 56810$ .

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

Показать ответ и решение

for n in range(1,1000):
    t = hex(n)[2:]#Запись числа в шестнадцатеричной системе счисления
    avg = sum(map(int,str(n)))//len(str(n))#Среднее арифметическое значение числа N
    if avg > 5:#Если оно больше 5
        t = ’1’ + t#Слева от числа приписываем 1
    else:#Если оно меньше или равно 5
        t = ’2’ + t#Слева от числа приписываем 2
    r = int(t,16)#Перевод в 10сс из 16сс
    if r > 310 and r < 350:
        print(n)
        break

Ответ: 57

Предыдущий раздел

Следующий раздел