Вывести на экран x, записанное в системе счисления с основанием n

Формулировка. Даны натуральные числа x и n (n <= 10). Вывести на экран число x, записанное в системе счисления с основанием n.

Решение. Вспомним правило из задачи 5:

Остаток от деления любого десятичного числа x на число p дает нам разряд единиц числа x (его крайний разряд справа) в системе счисления с основанием p.

Раньше мы принимали это правило без доказательства, однако сейчас мы коснемся его, так как оно достаточно краткое.

Воспользуемся формулой записи десятичного числа x в системе счисления с основанием p, состоящего из r знаков:

x = a_r–1 * p^r–1 + a_r–2 * p^r–2 + … + a₂ * p² + a₁ * p¹ + a₀ * p⁰,

где p^r–1, p^r–2, …, p², p¹, p⁰ – основание системы счисления, возведенное в соответствующие степени, a_r–1, a_r–2, …, a₂,a₁, a₀– цифры в записи этого числа в системе счисления с основанием p.

Например, число 378 в десятичной системе счисления выглядит так: 378 = 3 * 10² + 7 * 10¹ + 8 * 10⁰. Если мы подряд выпишем цифры a₂ (= 3), a₁ (= 7), a₀ (= 8), то исходное число восстановится.

Запишем представление числа в 22 двоичной системе счисления (переведем его с помощью калькулятора, оно равно 10110₂) по этой же формуле: 22 = 1 * 2⁴ + 0 * 2³ + 1 * 2² + 1 * 2¹ + 0 * 2⁰. Понятно, что если мы вычислим выражение в правой части равенства, то получим как раз 22.

Теперь покажем то, что если мы возьмем остаток от деления числа 22 на 2, затем разделим его на 2, отбросив остаток, и будем повторять эти действия до обнуления числа, то в итоге получим все его разряды в порядке справа налево. Возьмем его запись 1 * 2⁴ + 0 * 2³ + 1 * 2² + 1 * 2¹ + 0 * 2⁰ и разделим ее на 2. Из алгебры известно, что если мы делим сумму чисел на некоторое число, то на него делятся все слагаемые этой суммы. 1 * 2⁴, 0 * 2³, 1 * 2² и 1 * 2¹ делятся на 2, так как в них присутствует множитель 2. 0 * 2⁰ = 0 * 1 = 0 не делится на 2, соответственно, это число будет остатком от деления на 2, и при этом по формуле оно является крайним справа разрядом. Затем мы делим всю эту запись на 2 и отбрасываем остаток, получаем: 1 * 2³ + 0 * 2² + 1 * 2¹ + 1 * 2⁰. Очевидно, что при следующем взятии остатка мы получим цифру из крайнего справа слагаемого. Повторяя эту цепочку, мы постепенно получим все цифры числа 22 в системе счисления с основанием 2.

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

Каким образом мы запишем остатки справа налево? Очень просто: умножаем очередной остаток на некоторый множительz, добавляющий необходимое количество нулей, чтобы цифра оказалась в необходимой позиции, и прибавляем к результатуr. Поначалу z будет равен 1, так как мы прибавляем цифру к разряду единиц, затем z в каждой итерации будет умножаться на 10.

В итоге мы прибавляем к результату r первый остаток, умноженный на 1, второй остаток, умноженный на 10, третий остаток, умноженный на 100 и так далее, пока не будет сформировано искомое число:

r := 0;

z := 1;

while x <> 0 do begin

r := r + z * (x mod n);

x := x div n;

z := z * 10

end;

Код:

1. program ConvertNotation;
2. var
3. x, n: word;
4. r, z: integer;
5. begin
6. readln(x, n);
7. r := 0;
8. z := 1;
9. while x <> 0 do begin
10. r := r + z * (x mod n);
11. x := x div n;
12. z := z * 10
13. end;
14. writeln(r)
15. end.