Алгоритм Евклида нахождения наибольшего общего делителя

 Наиболее часто используются три разновидности алгоритма Евклида нахождения НОД(а,в).

· Алгоритм на основе операции вычитания

· Алгоритм на основе операции получения остатка от деления

· Двоичный алгоритм

Рассмотрим алгоритм на основе нахождения общих простых делителей для заданных чисел.

Обозначим НОД(а,в) – значение нахождения наибольшего общего делителя двух натуральных чисел а и в.

Справедливы следующие утвеждения.

1) Всегда существует общий делитель чисел а и в равный единице.

2) Существует разложение чисел а и в на простые множители(основная теорема арифметики)
Пример . –факторизация числа а.
Для а=18, факторизация имеет вид 18=2×3×3

3) Тогда НОД(а, в) будет равен произведению общих делителей чисел а и в.
Пример. НОД(12,18)=НОД((2×2×3), (2×3×3))= 2×3=6

… и т.д.

3. Задания на лабораторную работу.

3.1. Задание 1

Составить алгоритм нахождения количества квадратов, на которые можно разрезать  прямоугольник размером n×m в следующем порядке – выделяется максимальный квадрат, затем в оставшейся части вырезается очередной максимальных квадрат и т.д.

3.1.1. Постановка задачи

Заданы два натуральных числа n×m – длины сторон прямоугольника.

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

Пример. m=9, n=5.

Первый разрез.	Второй разрез.	…

3.1.2. Технические условия

1. Числа n,m <1000

2. Формат входных данных.
Числа n,m записаны в файле in.txt в одной строке и разделены одним пробелом.

3. Формат выходных данных
Результат запиывается в выходной файл out.txt в виде:
НОД(n,m)=число

4. Время работы приложения не превышает 1 с.

3.1.3. Математическое обеспечение

Математические методы

Утверждается что число разрезов N=GCD(n,m).

Доказательство.

Процесс разрезания соответствует алгоритму Евклида нахождения НОД(n,m) на основе вычитания. Поэтому можно применить данный алгоритм для нахождения N.

Алгоритмы

Алгоритм нахождения N на основе алгоритма GCD(n,m)

1.  Положить N=0

2.  Положить R=|n-m|

3.  Цикл Пока (R не равно нулю)

3.1. N=N+1

3.2. n=min{n,m}

3.3. m=R

3.4. R=|n-m|

3.5. Конец цикла

4.  Вернуть N

3.1.4. Эксспериментальная часть

1.  Проверить работоспособность приложения для нескольких пар чисел, удовлетворяющих техническим условиям. Резултаты тестирования см в Приложении 1.

2.  Проверить работоспособность приложения для нескольких пар чисел, не удовлетворяющих техническим условиям. Резултаты тестирования см в Приложении 1.

3.  

 

3.2. Задание n

Составить бинарный  алгоритм нахождения GCD(n×m

3.2.1. Постановка задачи

3.2.2. Технические условия

3.2.3. Математическое обеспечение

Математические методы

Алгоритмы

3.2.4. Эксспериментальная часть

…

Список литературы

1. Шилдт Г. ….

2. Итернет ресурс. Сайт MetaNit.com …

3. …

 

Приложения

Приложение 1

Задание 1. Листинг программы

…

Задание 1. Результаты тестирования

…

Приложение 2

Задание 2. Листинг программы

…

Задание 2. Результаты тестирования

…

 

 

Список литературы

Программирование на языке высокого уровня C#/ Т.А. Павловская Т.А. Национальный Открытый Университет «ИНТУИТ», 2016

2. Г. Шилдт Полный справочник по С# М.: Издательский дом "Вильяме", 2004. — 752 с