2. Тип 5 № 75269 
Анализ и построение алгоритмов для исполнителей. Посимвольное преобразование в n-ричной системе счисления
i
Алгоритм получает на вход натуральное число N и строит по нему новое число R следующим образом.
1. Строится троичная запись числа N.
2. В полученной записи все нули заменяются на двойки, все двойки — на нули. Из полученного числа удаляются ведущие нули.
3. Результат переводится в десятичную систему счисления.
4. Результатом работы алгоритма становится модуль разности исходного числа N и числа, полученного на предыдущем шаге.
Пример. Дано число N = 35. Алгоритм работает следующим образом.
1. Строим троичную запись числа N: 3510 = 10223.
2. Заменяем цифры и удаляем ведущие нули: 1022 → 1200.
3. Переводим в десятичную систему: 12003 = 4510.
4. Вычисляем модуль разности: |35 − 45| = 10.
Результат работы алгоритма R = 10.
При каком наименьшем N в результате работы алгоритма получится R = 1 864 648.
Решение. Приведём решение задачи на языке Python.
for N in range(1864648, 10**10):
s = ''
while N > 0:
s += str(N%3)
N //= 3
s = s[::-1]
R = s.replace('0','*').replace('2','0').replace('*','2')
if abs(int(s,3) - int(R,3)) == 1864648:
print(int(s,3))
break
Ответ: 3323808.
Приведём программу Сергея Донец на PascalABC.NET:
При малых N разность R = |M - N| также мала (как в примере с N = 35 → R = 10).
M получается заменой цифр в троичной записи N, поэтому M и N имеют сопоставимый порядок величины.
R растёт пропорционально N, но нелинейно из-за замены цифр в троичной системе.
Если N∼103 то R∼103.
Если N∼106 то R∼106.
Следовательно, R=∣M−N∣ также имеет порядок, близкий к N.
При замене всех 0 на 2 в троичной записи N, число M может увеличиться максимум в 2 раза
если N = R = 1864648 div 2, то N = 932123 M = 661998 R = 270326 подтверждается пропорциональность ∼103
чтобы не высчитывать оптимальное начало N примем N = R = 1864648 и для него высчитаем разность:
N = 1864648. получим M = 2918320 R = 1053672 (меньше требуемого почти в 2 раза), значит
N > 1864648. также подтверждается пропорциональность ∼106
Если N<1864648, то M (полученное заменой цифр) не может быть больше N+1864648, так как замена цифр в троичной системе не приводит к такому скачку. Следовательно, R=∣M−N∣ не может достичь 1864648 при N<1864648.
Перебор можно начинать и с N = 1, но оптимальнее — с N = R = 1864648, так как при N<1864648 разность заведомо меньше целевого значения.
мы и так уже сэкономили диапазон 1..1864648. Начинаем перебор с N=1864648.
Обоснование нижней границы поиска
Если N<1864648, то R заведомо меньше целевого значения, так как R≤N<1864648.
Следовательно, перебор можно начинать с N=1864648 (это экономит диапазон 1..1864648).
Оптимизация верхней границы
Верхняя граница: N≤2×1864648 (так как M≤2N, и R=M−N≤N).
Итоговый диапазон перебора: N∈[1864648, 1864648 * 2].}
uses School;
begin
var start := 1864648;
var koend := 1864648 * 2;
var minN := MaxInt; // Инициализация максимальным значением
for var n := start to koend do
begin
var T := ToBase(n, 3); // N в троичной системе
T := T.Translate('02', '20');// Замена 0→2, 2→0
var M := dec(t, 3); // M = преобразованное число
var R := abs(M - N); // R = |M - N|
if R = 1864648 then begin
minN := N < minN ? N : minN;// Обновляем минимальное N
//Println(N, M, R); // Вывод для отладки = в окончательном варианте закоментируем
end;
end;
Println(minN); // Минимальное N, дающее R = 1864648
end.
PDF-версии: