Лабораторная работа № 4 (Алгоритм рекурсивного вычисление наибольшего общего делителя)

Рекурсивными процедурами (recursive procedure) называются процедуры, вызывающие сами себя.

Наибольшим общим делителем (greatest common divisor, GCD) двух чисел называется наибольшее целое, на которое делятся два числа без остатка. Например, наибольший общий делитель чисел 12 и 9 равен 3. Два числа называются взаимно простыми (relatively prime), если их наибольший общий делитель равен 1.

Математик Эйлер, живший в восемнадцатом веке, обнаружил интересный факт:

Если A нацело делится на B, то GCD(A, B) = A

Иначе GCD(A, B) = GCD(B Mod A, A).

Этот факт можно использовать для быстрого вычисления наибольшего общего делителя.

Например: GCD(9, 12) = GCD(12 Mod 9, 9)

= GCD(3, 9)

= 3

На каждом шаге числа становятся все меньше, так как 1<= B Mod A < A, если A не делится на B нацело. По мере уменьшения аргументов, в конце концов, A примет значение 1. Так как любое число делится на 1 нацело, на этом шаге рекурсия остановится. Таким образом, в какой то момент B разделится на A нацело, и работа процедуры завершится.

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

Для выполнения работы используются два компонента SpinEdit и командная кнопка Button (рис.1).

Рис.1

Декларирование функции

private { Private declarations } Function GCD(A, B:integer): Integer;

Тело функции

{Для функции безразлично (А,В) или (В,А)} Function TForm1.GCD(A, B:integer): Integer; begin If B Mod A = 0 Then // Делится ли B на A нацело? Result := A // Да. Функция выполнена. else Result := GCD(B mod A, A); //' Нет. Рекурсия (вызов самой себя). end;

Команда вызова функции

procedure TForm1.Button1Click(Sender: TObject); var A, B, X : integer; begin A := 12; B := 9; //числа А и B X := GCD(A,B); // результат работы функции {вывод информации} if X = 1 then Form1.Caption := 'Нет НОД !' else Form1.Caption := 'НОД = ' + IntToStr(X); end;

Лабораторная работа №5 (Простые числа)

Натуральное число p, большее единицы, называется простым, если оно делится нацело только на 1 и на себя. Основная теорема арифметики гласит, что любое натуральное число n, большее единицы, может быть разложено в произведение простых чисел, причем это разложение единственно с точностью до порядка простых сомножителей. Каноническое разложение натурального числа n имеет вид: , где: p1 < p2 < ...< pk - различные простые числа, .

Задача проверки простоты натурального числа и задача построения больших простых чисел имеют важные приложения в криптографии.

Элементарные методы проверки простоты чисел

Пусть n N. Как проверить, является ли n простым?

Метод пробных делений

Если n – составное число, то n = ab, где: 1< a b, причем .

Поэтому для d = 2, 3, . . ., проверяем, делится лиn на d? Если, делитель числа n не будет найден, то n – простое число. В противном случае будет найден минимальный простой делитель числа n, т.е. мы даже разложим n на два множителя.

Возможны модификации этого метода. Например, мы можем проверить, делится ли n на 2 и на 3 , и если нет, то перебираем далее только числа d вида: 1 + 6j и 5+ 6j где, j =1, 2, . ..

Решето Эратосфена

Если необходимо составить таблицу всех простых чисел в диапазоне чисел 2, 3, . . . , N, то нужно в начале вычеркнуть все числа, делящиеся на 2, кроме 2. Затем взять число 3 и вычеркнуть все последующие числа, делящиеся на 3 . Затем взять следующее, не вычеркнутое число (т. е. 5) и вычеркнуть все последующие делящиеся на него числа, и так далее.

В итоге останутся лишь простые числа.

В примере используется компонент Momo и командная кнопка Button, в обработчике события OnClick которой реализуется вычисление (Рис. 1).

Рис.1

Текст программы, демонстрирующей создание таблицы простых чисел в диапазоне 2 – 255.

procedure TForm1.Button1Click(Sender: TObject); const N = 255; // Диапазон чисел type NP = set of 2..N; //Множество чисел var simple: NP; i,K,L: integer; begin Memo1.Clear; // Очиска окна вывода Memo1.Lines.Add('Простые числа меньшие N,: '); simple :=[2..N]; // Инициализация множества L := trunc(sqrt(N+1)); K := 1; while K <= L do //Выполнять цикл до K <= L begin repeat K := K+1 until K in simple; // Повторять K := K+1 до K Memo1.Lines.Add(intToStr(K)); //Вывести числа до 17 for i := 2 to N div K do simple := simple - [K*i]; //Удалить из множества не простые end; for K := L+2 to N do // Вывести числа в диапазоне 17 - 255 if K in simple then Memo1.Lines.Add(intToStr(K)); end;

Тест на основе малой теоремы Ферма

Для проверки простоты чисел n порядкаметод пробных делений уже неприменим. Следующий тест основан на малой теореме Ферма: еслиn простое, то для любого a Z выполнено сравнение:

если же при этом (a, n) = 1, то:

Поэтому для проверки простоты n необходимо выбрать какое-либо a Z и проверить выполнение малой теоремы Ферма за log n арифметических операций (с помощью бинарного возведения в степень в кольце Z/nZ). Если малая теорема Ферма не выполнена, то n является составным числом.

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

Например, для 100-значных чисел n вида: , гдепроверялось выполнение теста, и первые десять чисел, прошедших этот тест, оказались впоследствии простыми.

Однако существуют такие большие числа, называемые числами Кармайкла, для которых условия теста Ферма выполняются, тем не менее, эти числа являются составными. Наименьшим числом Кармайкла является число 561, которое образуется произведением простых чисел 561=3*11*17. Для обнаружения таких чисел имеются специальные алгоритмы, основанные на теоремах Лагранжа, Эллера и ряда других математиков.

Современные методы

Ниже рассматривается пример, наглядно демонстрирующий процедуру генерирования простых положительных чисел в выбранном диапазоне значений для типа Integer.

В примере использованы компоненты SpinEdit 1,2 (для выбора значений диапазона чисел), компонент Memo – для отображения результатов и командная кнопка Button.

Рис. 2 Расположение элементов в форме

Функция проверки на простоту числа

(Так, как функция не декларируется в разделах декларирования то, тело функции необходимо располагать в Unit'e выше тела команды теста.)

{------------------------------------------------------------} {--- функция проверки чисел на их простоту ---} {----- возвращает TRUE, если число простое ---} {-----------------------------------------------------------} function Simple(n:integer):Boolean; var k:Boolean; i:integer; begin k:=true; if n<>2 then for i:=2 to trunc(sqrt(n))+1 do if n mod i = 0 then begin k := false; break; end; Result:=k; end;

Команда теста функции

// Команда вывода простых чисел в диапазоне N:M procedure TForm1.Button1Click(Sender: TObject); var i:integer; begin Memo1.Clear; for i := SpinEdit1.Value to SpinEdit2.Value do if Simple(i) = true then Memo1.Lines.Add(IntToStr(i)); end;