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

5.01 Запись числа в двоичной системе счисления

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела алгоритмы – анализ простейших алгоритмов
Решаем задачу:

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

Задача 1#26192

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

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

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

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

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

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

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

Решение программой
В условии задачи описан алгоритм, для поиска подходящего числа N необходимо «перевести» этот алгоритм с естественного языка на язык программирования Python. Первым делом переводим число N в двоичную строку с помощью функции bin, затем дублируем последнюю цифру, используя доступ по индексу (s[-1]) и сложение строк (+). Далее вычисляем число единиц, используя метод count, находим остаток от деления на 2 (% 2), дописываем в конец записи. Повторяем то же самое для обновлённой записи. Осталось перевести результат в десятичную систему счисления, получив R.

Далее организуем перебор чисел N в цикле for. Для каждого полученного значения R проверяем, превышает ли оно 90. Если условие выполняется, выводим N и завершаем цикл, ведь нас интересует наименьшее N, а следующие значения N будут больше, так как цикл перебирает их по возрастанию.

for n in range(1000):  # Перебираем числа N от 0 до 999 включительно
    s = bin(n)[2:]  # Перевод в двоичную систему
    s = s + s[-1]  # Дописываем последнюю цифру

    # Считаем количество единиц с помощью count,
    # находим остаток (% 2), дописываем в конец s
    s = s + str(s.count("1") % 2)
    s = s + str(s.count("1") % 2)  # Повторяем для обновлённой записи

    r = int(s, 2)  # Переводим в десятичную систему

    if r > 90:  # Проверяем, что полученное число больше 90
        print(n)  # Первое выведенное N будет минимальным
        break  # Завершаем цикл

Ответ: 11

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение

Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!