Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
Топ:
Установка замедленного коксования: Чем выше температура и ниже давление, тем место разрыва углеродной цепи всё больше смещается к её концу и значительно возрастает...
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного хозяйства...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов...
Интересное:
Искусственное повышение поверхности территории: Варианты искусственного повышения поверхности территории необходимо выбирать на основе анализа следующих характеристик защищаемой территории...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Дисциплины:
2019-09-26 | 231 |
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 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!