21.10.2024

Задание 14. ЕГЭ по информатике. Найти наименьшее значение x, при котором троичная запись значения выражения содержит 2000 цифр "2"

Задание 14 (ЕГЭ по информатике). Значение арифметического выражения 3^2000 + 3^10 - x, где х – натуральное число, записали в троичной системе счисления. Определите наименьшее значение x, при котором троичная запись значения данного выражения содержит 2000 цифр "2".

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

Как будем решать задачу

  • Запустим цикл по переменной x в диапазоне от 3^10 до 2*3^10
    (такой диапазон выбираем потому, что если вычтем 3**10, то получим 3**2000, а это число в 3 с.с. записывается, как 1 и 2000 нулей, а нам нужно получить число, в котором ровно 2000 двоек, а это число меньше на 1 разряд, значит, как минимум, нужно вычитать 3^10, так как ищем наименьшее, значит запускать можно не так далеко (), по сути, можно и теоретически решать эту задачу, в общем, кто понял, тот уже решил). Ну, в общем далее.
    спасибо за комментарий: правая граница подбираемая, но можно запустить и бесконечный цикл, брейковать, когда число x найдено.
  • В цикле формируем число n = 3^2000 + 3^10 - x
  • Переводим число n в троичную с.с. и считаем количество цифр "2"
  • Во внешнем цикле проверяем, если количество цифр "2" равно 2000, выводим число x на экран

Программа решения задачи на языке Python

for x in range(3**10,2*3**10):

    n = 3**2000 + 3**10 - x

    p = 0

    while n!=0:

        d = n % 3

        n//=3

        if d==2:

            p+=1

    if p==2000:

        print(x)

        break

Ответ: 59050

Если не очень понятно, почему запускаем цикл по такому диапазону, то можно запускать цикл сначала от 1 до 1000 (не получим никакого ответа), затем от 1000 до 10000 (тоже не получим ответа), затем от 10000 до 50000 (тоже не получим ответа), затем от 50000 до 10000, получим ответ. То есть, экспериментально подбираем диапазон. Поскольку ищем минимальное число x, то после успешной проверки, можно его вывести и выполнить оператор break (выйти из цикла и не гнать его дальше).

Другие задания 14 из ЕГЭ по информатике в разделе Разбор задач ЕГЭ.

4 комментария:

  1. Заметим, что 2000 двоек в троичной системе счисления имеет число 3^2000 - 1. Следовательно, x=3^2000+3^10-3^2000+1 = 3^10+1 = 59050. И не нужно ничего программировать.

    ОтветитьУдалить
    Ответы
    1. Александр, читайте внимательно!
      Как будем решать задачу
      Запустим цикл по переменной x в диапазоне от 3^10 до 2*3^10 (такой диапазон выбираем потому, что если вычтем 3**10, то получим 3**2000, а это число в 3 с.с. записывается, как 1 и 2000 нулей, а нам нужно получить число в котором ровно 2000 двоек, а это число меньше на 1 разряд, значит, как минимум, нужно вычитать 3^10, так как ищем наименьшее, значит запускать можно не так далеко, по сути, можно и теоретически решать эту задачу, в общем, кто понял, тот уже решил). Ну, в общем далее.
      Вы молодец, что решили! Блог для учеников!

      Удалить
  2. Нет ничего плохого, чтобы учить детей сразу писать хороший код. Я не предлагаю Вам читать (или перечитывать) книгу Стива Макконнелла "Совершенный код", но основные-то моменты нужно учитывать! Например, код не должен содержать магических чисел, их смысл надо раскрывать. Хорошо, 3^10 Вы объяснили, а почему именно 2*3^10 надо брать, если Вы все равно прерываете цикл? Алгоритмически правильно тут инициализировать х, а затем сделать бесконечный цикл, наращивая в его теле x на единицу, а не придумывать магию. Далее, зачем вычислять в теле цикла каждый раз 3^2000 + 3^10? Вычислите до входа в цикл константу m, а в теле цикла получайте из нее m.

    ОтветитьУдалить
    Ответы
    1. Александр, спасибо за комментарий! про бесконечный цикл и константу согласна

      Удалить