История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Топ:
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного хозяйства...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов...
Техника безопасности при работе на пароконвектомате: К обслуживанию пароконвектомата допускаются лица, прошедшие технический минимум по эксплуатации оборудования...
Интересное:
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Дисциплины:
2019-09-26 | 229 |
5.00
из
|
Заказать работу |
|
|
Наиболее часто используются три разновидности алгоритма Евклида нахождения НОД(а,в).
· Алгоритм на основе операции вычитания
· Алгоритм на основе операции получения остатка от деления
· Двоичный алгоритм
Рассмотрим алгоритм на основе нахождения общих простых делителей для заданных чисел.
Обозначим НОД(а,в) – значение нахождения наибольшего общего делителя двух натуральных чисел а и в.
Справедливы следующие утвеждения.
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 с
|
|
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!