Пример 1
e = 0.1 a = 5.01 b = 3 c = 4
Это прямоугольный треугольник с гипотенузой, равной 5.01.
Пример 2
e = 0.1 a = 2 b = 3 c = 3
Это не прямоугольный треугольник.
Пример 3
e = 0.1 a = 2 b = 3.5 c = 6
Это не треугольник
Разработка спецификаций на программный продукт
1. Выполните спецификацию для программы в соответствии с вариантом задания.
Варианты заданий
1. Разработать программу, упорядочивающую массив чисел в порядке возрастания его элементов методом выбора.
Алгоритм сортировки выбором:
Из массива выбираем минимальный элемент (если сортируем по возрастанию) и переставляем его с первым. Далее этот процесс повторяется для частей массива без первого элемента, затем без первых двух и т. д.
Тот же самый алгоритм можно описать иначе:
• последовательно рассматриваем части массива a[k], a[k+1], …, a[n-1], где n – размер массива; k = 0, 1, 2, …, n – 2;
• среди элементов каждой части массива выбираем элемент a[ima],
где ima – индекс элемента, который принимает наименьшее (или наибольшее) значение;
• меняем местами элемент a[ima] с a[k].
2. Разработать программу, упорядочивающую массив чисел в порядке возрастания его элементов методом пузырька.
Алгоритм сортировки методом пузырька кратко можно сформулировать так: сравниваем два соседних элемента и меняем их местами, если они нарушают порядок.
Пользуясь методом пузырька, надо:
• последовательно (в цикле) рассматривать части массива: a[k], a[k+1], …, a[n-1],где n – размер массива, k = 1, 2, …, n – 1;
• начиная с элемента a[n-1],последовательно сравнивать элемент a[j]
c a[j-1];
• если a[j] < a[j-1], то меняем местами эти элементы и a[j-1] сравниваем с a[j-2] и т. д.;
• если же a[j] > a[j-1],то сразу переходим к сравнению элемента a[j-1] с элементом a[j-2] и т. д.
Сравнение элементов следует всегда начинать либо с первого элемента, либо с последнего.
Первый проход происходит от элемента a[n-1] до a[1].
3. Разработать программу, упорядочивающую массив чисел в порядке возрастания его элементов методом шейкер-сортировки.
Алгоритм шейкер-сортировки (сортировка обменом) кратко может быть сформулирован следующим образом:
Шаг 1. Определяются начальный l и конечный r индексы неотсортированных частей массива.
Шаг 2. Производится сортировка методом пузырька массива от индекса l до индекса r. При этом элементы массива начинают перебираться от индекса r. При переборе фиксируется индекс последнего элемента, который изменил свое положение.
Шаг 3. Производится сортировка методом пузырька массива от индекса l до индекса r. При этом элементы массива начинают перебираться от индекса l. При переборе фиксируется индекс последнего элемента, который изменил свое положение.
Шаг 4. Шаги 1, 2, 3 повторяются до тех пор, пока l< r.
Подробный алгоритм:
• Шаг 1. Определяем левый и правый индексы не отсортированной части массива: l = 1, r = n-1.
• Шаг 2. Начало цикла с постусловием.
• Шаг 3. Цикл по j от r до l (от правого до левого индекса).
• Шаг 4. Если a[j-1] > a[j] (т. е. текущий больше предыдущего), то шаг 5. Иначе – шаг 7.
• Шаг 5. Меняем местами элементы a[j-1] и a[j].
• Шаг 6. Определяем (устанавливаем) k = j.
• Шаг 7. Конец цикла по j.
• Шаг 8. Устанавливаем l = k+1.
• Шаг 9. Цикл по j от l до r (от правого до левого индекса).
• Шаг 10. Если a[j-1] > a[j] (т. е. текущий больше предыдущего),то шаг 11. Иначе – шаг 13.
• Шаг 11. Меняем местами элементы a[j-1] и a[j].
• Шаг 12. Определяем (устанавливаем) k = j.
• Шаг 13. Конец цикла по j.
• Шаг 14. Устанавливаем r = k-1.
Шаг 15. Конец цикла с постусловием (пока l < r).
4. Разработать программу, упорядочивающую массив чисел в порядке возрастания его элементов методом вставок.
• Шаг 1. Определяем переменную j = k-1, где k-1 – индекс последнего элементаупорядоченной части массива.
• Шаг 2. Первый элемент неупорядоченной части массива a[k] переписывается (копируется, засылается) в некоторую переменную x для записи и хранения информации, которая может быть изменена
в процессе работы программы.
• Шаг 3. Если x < a[j], то переписываем a[j] в a[j+1] (сдвигаем a[j] вправо на одну позицию) и значение индекса j уменьшаем на 1.
• Шаг 4. Шаг 3 повторяется до тех пор, пока выполняется неравенство
x < a[j].
• Шаг 5. Если x>= a[j], то a[j] является именно тем элементом, за которым надо вставить x (т. е. первый элемент неупорядоченной части массива). Для этого x переписываем в a[j+1].
5. Разработать программу, упорядочивающую массив чисел в порядке возрастания его элементов методом Шелла
Алгоритм сортировки Шелла заключается в следующем. Массив a[n] размерности n разбивается на t частей, в каждой из которых содержится одинаковое количество k = n/t элементов.
Число элементов в последней части массива, разумеется, может быть меньше, чем n/t.
Далее производится сортировка тех элементов массива, которые отстоят друг от друга на расстоянии, равном k. То есть, на первом шаге для массива a[n] сортировка происходит для элементов, которые образуют следующие группы:
a[0], a[0+k], a[0+2k], a[0+3k],...
a[1], a[1+k], a[1+2k], a[1+3k],...
a[2], a[2+k], a[2+2k], a[2+3k],...
...
a[k-1], a[k-1+k], a[k-1+2k], a[k-1+3k],...
Далее изложенный процесс повторяется в цикле для последовательности чисел k, k,...,1, где k > k > k >... > 1.
Подробный алгоритм:
• Шаг 1. Устанавливаем значение параметра num,которыйопределяет, на сколько частей на первом шаге алгоритма разбивается массив.
• Шаг 2. Начало цикла сортировки по методу Шелла.Пока h > 1, выполнять шаги 3–10.
• Шаг 3. Устанавливаем расстояние h по формуле h = (h-1)/num
для текущего шага цикла сортировки.
• Шаг 4. Начало цикла сортировки методом пузырька.
• Шаг 5. Цикл по i = 0, 1,..., n-h – выполнять шаги 6–9.
• Шаг 6. Устанавливаем начальное значение j = h.
• Шаг 7. Группа элементов a[i], a[i+h], a[i+2h], a[i+3h] и т. д. сортируется методом пузырька.
• Шаг 8. Установить j = j+1.
• Шаг 9. Конец цикла по i.
• Шаг 10. Конец цикла сортировки по методу пузырька.
• Шаг 11. Конец цикла сортировки по методу Шелла.
В литературе нет ответа на вопрос, какую последовательность расстояний для ki надовыбирать. Необходимо только выполнять одно условие: в последнем шаге сортировки Шелла k должно равняться 1.
Шилдт рекомендует избегать последовательности шагов, которые являются степенями числа 2.В программах, которые приведены ниже, последовательность шагов выбирается по формуле:
• k = (k-1)/t, если k > 1,
• k = 1, если k < 1,
где параметр t (t < n) определяет, на сколько частей разбивается на первом шаге массив размерности n. Начальное значение параметра t задает пользователь. Параметр k определяет расстояние между элементами массива, которые, собственно говоря, и сортируются в процессе решения задачи. Начальное значение k равно размерности массива n.
6. Разработать программу, упорядочивающую массив чисел в порядке возрастания его элементов методом пирамидальной сортировки.
Алгоритм сортировки пирамиды.Рассмотрим массив размерности n, который представляет пирамиду a[1], a[2], …, a[n].
Шаг 1. Переставляем элементы a[1] и a[n].
Шаг 2. Определяем n = n-1. Это эквивалентно тому, что в массиве
из дальнейшего рассмотрения исключается элемент a[n].
Шаг 3. Рассматриваем массив a[1], a[2], …, a[n-1], который получается из исходного за счет исключения последнего элемента.
Данный массив из-за перестановки элементов уже не является пирамидой. Но этот массив легко преобразовать в пирамиду. Это достигается повторением перестановки значения элемента из a[1] с наибольшим из потомков.
Такая перестановка продолжается до тех пор, пока элемент из a[1] не окажется на месте элемента a[i] и при этом будут выполняться неравенства a[i] a[2i], a[i] a[2i+1]. Тем самым определяется новое место для значения первого элемента из a[1].
Шаг 4. Повторяем шаги 2, 3, 4 до тех пор, пока не получим n = 1. Произвольный массив можно преобразовать в пирамиду.
4. Содержание отчёта
- Название, цель работы
- Разработанные спецификации.
- Ответы на контрольные вопросы.
Вопросы к защите
1. Спецификация программного обеспечения.
2. Виды спецификаций.
3. Состав функциональной спецификации.
4. Перечислите этапы разработки программных продуктов.
5. Для чего необходимо техническое задание?
6. Кто занимается разработкой технического задания?
7. Какие пункты включает техническое задание?
8. Для чего разрабатываются спецификации на программный продукт?
9. Что должны включать спецификации на программный продукт?
10. Что должна содержать спецификация процессов
11. Что такое словарь терминов и для чего он используется?
Приложение
Самостоятельная работа по лабораторной работе № 1
«Разработка спецификаций структурных единиц»
Самостоятельная работа по теме занятия включает в себя:
- изучение теоретического материала лекционных занятий, учебной литературы, Интернет-ресурсов, раздела «Краткие сведения из теории» настоящего описания ЛР;
- выполнение практических заданий и решение задач
Задачи и практические задания
1. На основании технического задания, представленного в Приложении 2 разработать спецификацию требований к программе.
Приложение 2
Техническое задание
Введение
При проектировании сложных систем, таких как микропроцессорная автоматизированная системы или её узлы, возникает ряд комбинаторно-оптимизационных задач структурного синтеза, на всех этапах, начиная с эскизного проектирования и заканчивая разработкой конструкторской документации. К таким задачам относятся, например, схемная компоновка, размещение компонентов в монтажном пространстве, коммутации соединений и т. д. Автоматизация указанных процессов является актуальной проблемой. Поэтому целью настоящего курсового проекта является автоматизация решения комбинаторно-оптимизационных задач.
Для достижения указанных задач необходимо решить ряд инженерных задач, а именно:
- анализ области применения комбинаторно-оптимизационных задач;
- математические методы выбранных задач;
- разработка архитектуры ПС;
- выбор метода проектирования, программных средств реализации ПС;
- разработка структуры данных для хранения информации;
- разработка алгоритмов решения задач;
- тестирование ПС;
- разработка руководства программиста;
- разработка руководства пользователя;
- оценка экономической эффективности внедрения ПС;
- безопасность труда пользователя.
Решение данных задач возможно на основании методов дискретной математики, программирования на языках высокого уровня, теории баз данных, статистических методов и моделей.
Основание для разработки
Система разрабатывается на основании учебного плана подготовки специалистов 230105.65 - ПОВТАС и рабочей программе по дисциплине специализации «Системы автоматизации проектирования программного обеспечения»
Назначение
Целью данной разработки является создание программного средства, позволяющего автоматизировать работу по решению комбинаторно-оптимизационных задач коммутации.
Первая версия системы предназначена для решения небольшого круга комбинаторно-оптимизационных задач на графах (поиск кратчайшего пути, минимального покрывающего дерева и покрывающего цикла минимальной длины). В следующих версиях предполагается увеличение количества решаемых задач.
Пользователями могут выступать научные работники и инженеры, занимающиеся проектированием компьютерной техники, и студенты соответствующих специальностей. Пользователями могут также быть и специалисты других предметных областей, которым приходится решать подобные задачи.
