Задача № 35. Вывести на экран x, записанное в системе счисления с основанием n
Формулировка. Даны натуральные числа x и n (n <= 10). Вывести на экран число x, записанное в системе счисления с основанием n.
Решение. Вспомним правило из задачи 5:
Остаток от деления любого десятичного числа x на число p дает нам разряд единиц числа x (его крайний разряд справа) в системе счисления с основанием p.
Раньше мы принимали это правило без доказательства, однако сейчас мы коснемся его, так как оно достаточно краткое.
Воспользуемся формулой записи десятичного числа x в системе счисления с основанием p, состоящего из r знаков:
x = ar–1 * pr–1 + ar–2 * pr–2 + ... + a2 * p2 + a1 * p1 + a0 * p0,
где pr–1, pr–2, …, p2, p1, p0 – основание системы счисления, возведенное в соответствующие степени, ar–1, ar–2, ..., a2, a1, a0 – цифры в записи этого числа в системе счисления с основанием p.
Например, число 378 в десятичной системе счисления выглядит так: 378 = 3 * 102 + 7 * 101 + 8 * 100. Если мы подряд выпишем цифры a2 (= 3), a1 (= 7), a0 (= 8), то исходное число восстановится.
Запишем представление числа в 22 двоичной системе счисления (переведем его с помощью калькулятора, оно равно 101102) по этой же формуле: 22 = 1 * 24 + 0 * 23 + 1 * 22 + 1 * 21 + 0 * 20. Понятно, что если мы вычислим выражение в правой части равенства, то получим как раз 22.
Теперь покажем то, что если мы возьмем остаток от деления числа 22 на 2, затем разделим его на 2, отбросив остаток, и будем повторять эти действия до обнуления числа, то в итоге получим все его разряды в порядке справа налево. Возьмем его запись 1 * 24 + 0 * 23 + 1 * 22 + 1 * 21 + 0 * 20 и разделим ее на 2. Из алгебры известно, что если мы делим сумму чисел на некоторое число, то на него делятся все слагаемые этой суммы. 1 * 24, 0 * 23, 1 * 22 и 1 * 21 делятся на 2, так как в них присутствует множитель 2. 0 * 20 = 0 * 1 = 0 не делится на 2, соответственно, это число будет остатком от деления на 2, и при этом по формуле оно является крайним справа разрядом. Затем мы делим всю эту запись на 2 и отбрасываем остаток, получаем: 1 * 23 + 0 * 22 + 1 * 21 + 1 * 20. Очевидно, что при следующем взятии остатка мы получим цифру из крайнего справа слагаемого. Повторяя эту цепочку, мы постепенно получим все цифры числа 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. 3. var 4. c, z, r: integer; 5. x, z: word; 6. 7. begin 8. readln(x, n); 9. r := 0; 10. z := 1; 11. while x <> 0 do begin 12. r := r + z * (x mod n); 13. x := x div n; 14. z := z * 10 15. end; 16. writeln(r) 17. end. |
Задача № 36. Найти наименьший нетривиальный делитель двух заданных чисел
Формулировка. Даны натуральные числа m и n. Вывести на экран их наименьший нетривиальный делитель или сообщить, что его нет.
Решение. Задача похожа на задачу 15, в которой поиск минимального делителя осуществлялся с помощью цикла:
for i := 2 to n do begin
if n mod i = 0 then begin
writeln(i);
break
end
end;
Здесь все просто: проверяем все числа от 2 по возрастанию – если нашли делитель, выводим его на экран и выходим из цикла с помощью break. В нашем же случае нужно проверять делимость двух введенных чисел. При этом цикл должен проходить по всем i от 2 до минимального из чисел m и n (назовем его min), так как оно может быть наименьшим нетривиальным делителем, когда оно простое. Например, для чисел 17 и 34 таковым является 17.
|
|
|
Найти наименьшее из двух чисел можно так:
if n < m then min := n else min := m;
Кстати, теперь в цикле мы должны не просто вывести на экран найденный делитель, а сохранить его в некоторую переменную (mindiv), которая до входа в цикл будет равна 1 (или 0), чтобы проверить, выполнилось ли условие делимости в цикле. Если да, то необходимо вывести значение наименьшего общего делителя, а если нет, и mindiv все еще равно 1 (или 0), то вывести сообщение об отсутствии делителя.
Код :
Дата добавления: 2018-10-25; просмотров: 235; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!