CC6251 — Преобразование записи числа: ответ и решение

Впишите правильный ответ.

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

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

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

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

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

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

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

Например, для исходного числа 11 = 102₃ результатом является число 102101₃ = 307, а для исходного числа 6 = 20₃ это число 2020₃ = 60.

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

СВОЙСТВА ЗАДАНИЯ

КЭС:

3.2 Оценка сложности вычислений. Время работы и объём используемой памяти, их зависимость от размера исходных данных. Оценка асимптотической сложности алгоритмов. Алгоритмы полиномиальной сложности. Переборные алгоритмы. Примеры различных алгоритмов решения одной задачи, которые имеют различную сложность

3.3 Определение возможных результатов работы простейших алгоритмов управления исполнителями и вычислительных алгоритмов. Определение исходных данных, при которых алгоритм может дать требуемый результат

3.4 Алгоритмы обработки натуральных чисел, записанных в позиционных системах счисления: разбиение записи числа на отдельные цифры, нахождение суммы и произведения цифр, нахождение максимальной (минимальной) цифры. Представление числа в виде набора простых сомножителей. Алгоритм быстрого возведения в степень. Поиск простых чисел в заданном диапазоне с помощью алгоритма «решето Эратосфена»

3.5 Многоразрядные целые числа, задачи длинной арифметики

Тип ответа:

Краткий ответ

Номер: CC6251

Статус задания: НЕ РЕШЕНО Ответить

Решение задания EGEINFCC6251

Ответ: 11

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

Приписать справа d троичных цифр со значением t означает получить R = 3ᵈ · N + t. При остатке 1 от деления N на 3 дописывается 5 = 12₃; при остатке 2 — число 10 = 101₃. У кратного 3 натурального числа есть как минимум две троичные цифры; их значение равно N mod 9.
Общие формулы: R = 9N + (N mod 9) при кратном 3 числе; R = 9N + 5 при остатке 1; R = 27N + 10 при остатке 2. Здесь mod означает остаток от деления.
Каждая ветвь даёт R ≥ 9N.

Обоснование конечного перебора.
Ниже проверяются все натуральные N от 1 до 11 включительно. Для минимального N достаточно найти первый подходящий вход: ни одно большее N уже не может улучшить ответ.

Полный расчёт на выбранном отрезке по приведённым формулам. В каждой паре сначала указан вход N, затем результат R:
N = 1, R = 14; N = 2, R = 64; N = 3, R = 30; N = 4, R = 41.
N = 5, R = 145; N = 6, R = 60; N = 7, R = 68; N = 8, R = 226.
N = 9, R = 81; N = 10, R = 95; N = 11, R = 307.

Первый вход, для которого R не меньше 228: N = 11, R = 307. Все меньшие N есть в таблице и не удовлетворяют требованию.

Проверка выбранного входа: N = 11 = 102₃.
Преобразованная запись: 102101₃.
R = 243 + 54 + 9 + 1 = 307.
Полученное значение удовлетворяет условию. Полный перебор с доказанной границей подтверждает требуемый экстремум. В ответ записываем N.

Ответ: 11.

Задание EGEINFCC6251: Преобразование записи числа

Решение задания EGEINFCC6251

Помочь улучшить сайт

Комментарии к решению