Задания

Задание 1

Пусть необходимо вычислить целую степень для произвольных значений степени и основания, используя только операцию умножения. Проблема здесь заключается в том, что конкретное значение степени заранее неизвестно, следовательно, неизвестно и необходимое количество умножений. Чтобы решить эту проблему, ведем в алгоритм вспомогательную переменную – счетчик числа выполненных умножений, а степень будем вычислять по рекуррентной формуле:

Запись алгоритма вычисления произвольной целочисленной степени числа приводится ниже:

Ввести значения х и n. Переменной z присвоить начальное значение1. Вспомогательной переменной i присвоить начальное значение 0. Переменной z присвоить результат выполнения операции z х. Переменной i присвоить значение i + 1. Если i < n, то перейти к шагу 4,иначе остановить работу программы.

Этот алгоритм содержит ввод данных (шаг 1), блок вычислений (шаги 2, 3), ветвление (шаг 6), а также еще одну алгоритмическую структуру – цикл (шаги 4, 5 и 6).

Цикл представляет собой многократно повторяющуюся последовательность операторов и играет в программировании важнейшую роль. Кроме уже перечисленных структур иногда выделяют еще одну – обход, который представляет собой передачу управления с пропуском нескольких шагов алгоритма.

Задание 2 Алгоритм Евклида

Еще в III в. до н. э. математик Евклид, известный автор первого дошедшего до нас теоретического тракта по математике «Начала», в геометрической форме изложил правило получения наибольшего общего делителя двух натуральных чисел.

Идея этого правила (обоснование его корректности) заключается в том, что, если z –наибольший общий делитель двух натуральных чисел х и у, то в случае равенства этих чисел, он совпадает с любым из них, а в случае их неравенства разность между большим и меньшим имеет тот же самый наибольший общий делитель z.

Назовем число, равное тому из двух чисел х, у, которое не меньше другого, их верхней гранью и обозначим g , а второе обозначим h. После вычитания одного числа из другого получим новую пару чисел g-h и h, верхняя грань g которых строго меньше z. Новые числа имеют тот же наибольший общий делитель z. Значит, мы свели задачу к нахождению наибольшего общего делителя натуральных чисел, верхняя грань которых меньше первоначальной.

Повторяя прием, мы должны в конце концов прийти к случаю, когда новые полученные натуральные числа между собой равны, так как безграничное число шагов уменьшения верхней грани невозможно (потому что натуральных чисел, не превосходящих числа g, всего несколько).

Сам алгоритм нахождения наибольшего общего делителя z двух натуральных чисел х и у (алгоритм Евклида) можно изложить так:

1.  Если х > у, то перейти к п.4, иначе перейти к п.2.

2.  Если у > х, то перейти к п.5, иначе перейти к п.3.

3.  Считать, что z = x. Конец.

4.  От х отнять у и впредь считать, что эта разность является значением х. Возвратиться к п.1.

5.  От у отнять х и впредь считать эту разность значением у.

Возвратиться к п.1.

Можно было бы получить другую разновидность алгоритма Евклида. Если учесть, что деление является многократным вычитанием. При этом нужно будет большее из чисел х, у, делить на меньшее и остаток в дальнейшем считать значением буквы, которая при этом обозначила делимое.

Это позволит, не меняя первых трех пунктов, прежнее пп.4,5 заменить следующими:

1.  Остаток от деления х на у впредь считать значением х. Перейти к п.1..

2.  Остаток от деления у на х считать новым значением у. Вернуться к п.1.

Новый алгоритм тоже называют алгоритмом Евклида.

Он окажется удобнее первоначального, если мы можем пользоваться операцией деления с остатком.

В алгоритме Евклида мы замечаем интересный прием: изменяя величину, мы сохраняем за ней ее исходное имя. При этом возникает понятие величины, значение которой может изменяться. Пункты алгоритма, изменяющие значения величин, относятся к числу так называемых операторов.

Задание 3 Решето Эратосфена

Целые положительные числа, отличные от единицы, которые без остатка делятся на единицу и на самих себя, называются простыми. Первым из таких чисел является 2. Все остальные чётные числа уже не будут простыми, так как допускают деление без остатка на 2 (а не только на 1 и на себя ).

Нетрудно указать и ещё несколько простых чисел: 3, 5, 7, 11, 13.

Древнегреческий учёный Эратосфен (III – II вв. до н. э.) предложил способ получения простых чисел, не превосходящих заданного числа N. Этот способ можно описать в виде следующего алгоритма Эратосфена.

Выписать последовательные целые числа, начиная с 2 и заканчивая числом N. Перейти к п. 2. Считать, что p является именем числа 2. Перейти к п. 3. Если p² ≤ N, то перейти к п. 4, иначе перейти к п. 6. Начиная с числа p + 1 в последовательности чисел зачеркнуть (не отбрасывая его и не обращая внимания на то, было ли оно уже зачёркнуто) каждое p – e число. Перейти к п. 5. Первое после p не зачеркнутое число последовательности считать новым значением имени p. Вернуться к п. 3. Процесс окончен. Все, не зачёркнутые числа последовательности, являются простыми.

Обосновать корректность алгоритма Эратосфена нетрудно.

Кроме числа p, которое имеет вид p = 1 * p, мы вычеркиваем все числа 2 * p, 3 * p, …, которые не превосходят заданного числа N.

Выбирая первое после p не зачеркнутое число, мы, естественно, находим новое наименьшее из простых чисел, превосходящее p, потому что оно не делится на p и на все меньшие его простые числа, а делится только на себя и на единицу (на большее число деление без остатка невозможно, а на меньшее число оно не делится, так как если бы оно имело простой делитель, то было бы вычеркнуто, а если бы имело непростой делитель, то каждый простой делитель этого непростого делителя был бы также его делителем, т. е. опять – таки оно оказалось бы зачеркнутым).

Остаётся только убедиться в том, что, прекращая процесс после того, как получено простое число p, которое не удовлетворяет условию p² ≤ N, т. е. такое, что p² > N, мы не оставляем среди оставшихся чисел ни одного составного. Но это понятно, потому что если бы среди оставшихся чисел было хотя бы одно непростое, то оно не могло бы иметь делителя, меньшего p (так как все числа, имеющее делитель, равный простому числу, меньшему чем p, уже зачёркнуты). Не может оно быть равно и p * p = p², так как p² больше N. Значит, оно должно быть произведением чисел, из которых хотя бы одно больше p, а другое не меньше p. Это невозможно, так как такое число больше p², а значит, и больше N, у нас же могут быть только числа, которые меньше или равны N.

Без труда и довольно быстро можно убедиться в том, что простыми числами, не превосходящими 100, являются: 2, 3, 5, 7, 11, 13,17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89,97. Для получения этого ряда простых чисел нам пришлось выполнять процесс для p = 2, p = 3, p = 5, p =7. Уже p = 11 дало 11² = 121 > 100, что послужило сигналом для прекращения процесса. Отбросив числа, делящиеся на первые 4 простых числа, мы получили 25 простых чисел, среди которых наибольшее 97.

Задание 4 Алгоритм разложения положительного целого числа N на простые множители для N≥2.

Составить в порядке возрастания последовательность всех простых чисел, каждое из которых не больше N. Именем p называть простое число 2. Считать, что произведение П состоит из единственного множителя, равного единице. Перейти к п. 2. Если N является простым числом (в этом случае оно стоит среди полученных простых чисел на последнем месте), то перейти к п. 7. Если наибольший общий делитель чисел N и p равен 1, перейти к п. 4, иначе перейти к п. 6. Найти следующее за p по величине простое число. Впредь его называть именем р. Перейти к п.5. Если р² > N, то перейти к п.7, иначе перейти к п.3. Разделить N на p. Частное считать новым значением N. К произведению П приписать точку ( знак умножения) и за ней число, являющееся значением р. В дальнейшем именем П называть новое произведение. Вернуться к п.3. Приписать к произведению П точку (знак умножения) и за ней число N. В дальнейшем буквой П будем обозначать новое произведение. Перейти к п.8. В произведении П произведения одинаковых простых чисел заменить их степенями, стоящую на первом месте единицу отбросить. Ответ получен. Процесс окончен.

Применив этот алгоритм к числу N= 504, получим N =2³ * 3² * 7.

Доказать корректность алгоритма разложения положительного целого на простые сомножители очень просто.

Задание 5 Алгоритм получения наименьшего кратного нескольких чисел.

Заданные числа разложить на простые сомножители и получить произведения их степеней .Перейти к п.2. Составить строку К, выписывая в порядке возрастания простые числа, присутствующие хотя бы в одном из разложений, и разделяя их знаками умножения. Перейти к п.3. Каждое из простых чисел, входящих в К, возвести в степень, показатель которой равен наибольшему показателю степени того же простого числа в разложениях . Полученный результат впредь именовать К. Перейти к п.4. В К произвести все возведения в степень и все умножения. Полученный результат является ответом. Конец.

Корректность этого алгоритма вытекает из того, что:

а) для любого (1<i<n) путем несложных преобразований и перегруппировки в составе К можно выделить группу сомножителей, совпадающих с , откуда следует, что полученный результат кратен числу

б) уменьшить полученный результат нельзя, так как уменьшение показателя степени хотя бы одного сомножителя в К привело бы к тому, что результат перестал бы быть кратным хотя бы одному из .