Решение: Анализ алгоритма в позиционной системе
Получив на вход натуральное число $x$, алгоритм выполняет несколько итераций: на каждой итерации увеличивает $N$ на 1, прибавляет остаток от деления $x$ на 4 к $S$, умножает $P$ на этот остаток, после чего заменяет $x$ на целую часть частного $x/4$. После завершения цикла к $S$ и $P$ прибавляется $N$. Затем алгоритм печатает сначала $S$, а потом $P$. Укажите наибольшее число $x$, при вводе которого алгоритм печатает сначала 7, а потом 3.
1x = int(input()) 2P = 1 3S = 0 4N = 0 5while x > 0: 6 N = N + 1 7 S = S + (x % 4) 8 P = P * (x % 4) 9 x = x // 4 10S = S + N 11P = P + N 12print(S) 13print(P)
Решение по шагам
5 шаговПри последовательном целочисленном делении $x$ на 4 остатки являются цифрами записи числа $x$ в четверичной системе счисления. Число итераций $N$ равно количеству цифр этой записи.
Пусть цифры четверичной записи числа $x$ равны $d_1, d_2, \ldots, d_N$. Тогда после цикла $S=d_1+d_2+\ldots+d_N+N=7$, а $P=d_1d_2\ldots d_N+N=3$.
Следовательно, сумма цифр равна $7-N$, а произведение цифр — $3-N$. При $N\geq4$ произведение было бы отрицательным, что невозможно. При $N=1$ и $N=2$ условия на сумму и произведение несовместимы.
При $N=3$ сумма цифр равна $4$, а произведение равняется нулю. Для получения наибольшего числа выбираем наибольшую возможную первую цифру: запись $310_4$ удовлетворяет этим условиям.
Переведём число в десятичную систему: $x=3\cdot4^2+1\cdot4+0=48+4=52$.
Где здесь ошибаются
Забывают прибавить $N$ к значениям $S$ и $P$ после завершения цикла.
Путают остатки от деления на 4 с цифрами десятичной записи числа.
Выбирают набор цифр с подходящей суммой, но не проверяют их произведение.
Записывают цифры в неправильном порядке и получают не наибольшее число.