Задача № 33. Получить каноническое разложение числа на простые сомножители
Формулировка. Дано натуральное число n ( n > 1). Получить его каноническое разложение на простые сомножители, то есть представить в виде произведения простых сомножителей. При этом в разложении допустимо указывать множитель 1. Например, 264 = 2 * 2 * 2 * 3 * 11 (программе допустимо выдать ответ 264 = 1 * 2 * 2 * 2 * 3 * 11).
Решение. Данная задача имеет достаточно красивое решение.
Из основной теоремы арифметики известно, что для любого натурального числа больше 1 существует его каноническое разложение на простые сомножители, причем это разложение единственно с точностью до порядка следования множителей. То есть, например, 12 = 2 * 2 * 2 и 12 = 3 * 2 * 2 – это одинаковые разложения.
Рассмотрим каноническую форму любого числа на конкретном примере. Например, 264 = 2 * 2 * 2 * 3 * 11. Каким образом можно выявить эту структуру? Чтобы ответить на этот вопрос, вспомним изложенные в любом школьном курсе алгебры правила деления одночленов, представив, что числа в каноническом разложении являются переменными. Как известно, если разделить выражение на переменную в некоторой степени, содержащуюся в этом выражении в той же степени, оно вычеркивается в ее записи.
То есть, если мы разделим 264 на 2, то в его каноническом разложении уйдет одна двойка. Затем мы можем проверить, делится ли снова получившееся частное на 2. Ответ будет положительным, но третий раз деление даст остаток. Тогда нужно брать для рассмотрения следующее натуральное число 3 – на него частное разделится один раз. В итоге, проходя числовую прямую в положительном направлении, мы дойдем до числа 11, и после деления на 11 n станет равно 1, что будет говорить о необходимости закончить процедуру.
|
|
|
Почему при таком «вычеркивании» найденных сомножителей мы не получим делимостей на составные числа? На самом деле, здесь все просто – любое составное число является произведением простых сомножителей, меньших его. В итоге получается, что мы вычеркнем из n все сомножители любого составного числа, пока дойдем до него самого в цепочке делений. Например, при таком переборе n никогда не разделится на 4, так как «по пути» к этому числу мы вычеркнем из n все сомножители-двойки.
Алгоритм на естественном языке:
1) Ввод n;
2) Присвоение переменной p числа 2;
3) Вывод числа n, знака равенства и единицы для оформления разложения;
4) Запуск цикла с предусловием n < > 1. В цикле:
1. Если m mod p = 0, то вывести на экран знак умножения и переменную p, затем разделить n на p, иначе увеличить значение i на 1;
Код:
| 1. program PrimeFactors; 2. 3. var 4. n, p: word; 5. 6. begin 7. readln(n); 8. p := 2; 9. write(n, ' = 1'); 10. while n <> 1 do begin 11. if (n mod p) = 0 then begin 12. write(' * ', p); 13. n := n div p 14. end 15. else begin 16. inc(p) 17. end 18. end 19. end. |
Задача № 34. Сформировать число из двух заданных чередованием разрядов
|
|
|
Формулировка. Даны два натуральных числа одинаковой десятичной разрядности. Сформировать из них третье число так, чтобы цифры первого числа стояли на нечетных местах третьего, а цифры второго – на четных. При этом порядки следования цифр сохраняются. Например, при вводе 1234 и 5678 программа должна выдать ответ 15263748 (для наглядности разряды обоих чисел выделены разными цветами).
Решение. Так как у чисел (обозначим их a и b) одинаковая десятичная разрядность, крайняя справа цифра у третьего числа (c, которое поначалу должно быть равно 0) всегда будет на четном месте, так как при его формировании мы работаем с длинами a и b как с числами одной четности, сумма которых всегда четна, и длина c как раз и есть позиция крайней справа цифры.
Это значит, что формирование c нужно в любом случае начинать с последнего разряда b. При этом каждый взятый из a или b разряд мы должны сместить на необходимую позицию влево, чтобы добавлять разряды c, используя операцию сложения. Мы сделаем это с помощью вспомогательной переменной z, которая перед входом в цикл будет равна 1. В цикле же она будет умножаться на последний добытый разряд b (при этом выражение z * b mod 10 нужно прибавить к c), затем умножить z на 10 и проделать то же самое с последним разрядом a и снова умножить z на 10. Кстати, при этом нужно не забыть своевременно отбросить уже рассмотренные разряды чисел.
|
|
|
Так как разрядность чисел неизвестна, нам нужен цикл с предусловием. В силу одинаковой десятичной разрядности a и b мы можем сделать условие по обнулению любого из них, так как второе при этом также обнулится. Возьмем условие a < > 0.
Таким будет основной цикл:
while a <> 0 do begin
c := c + z * (b mod 10);
z := z * 10;
b := b div 10;
c := c + z * (a mod 10);
z := z * 10;
a := a div 10
end;
В итоге конечное число c будет сформировано в таком виде (все направления справа налево): первая цифра b, первая цифра a, вторая цифра b, вторая цифра a и так далее до самых последних разрядов слева. Кстати, скобки в двух операторах нужны для правильного понимания компилятором приоритета выполняемых арифметических операций. Без них z умножится на соответствующее число, и остаток от деления именно этого числа прибавится к c, что неправильно.
Алгоритм на естественном языке:
1) Ввод a и b;
2) Обнуление переменной c;
3) Присвоение переменной z числа 1;
|
|
|
4) Запуск цикла с предусловием a < > 0. В цикле:
1. Прибавляем последний разряд b в текущий разряд c, определяемый с помощью множителя z;
2. Умножаем z на 10;
3. Избавляемся от последнего разряда в b;
4. Прибавляем последний разряд a в текущий разряд c с помощью множителя z;
5. Умножаем z на 10;
6. Избавляемся от последнего разряда в a;
5) Вывод c.
Код :
Дата добавления: 2018-10-25; просмотров: 385; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!