Доведення теоретико-математичних тотожностей і тверджень (стр. 2 из 5)

Розробити алгоритм та написати програму обчислення множини:

Проектування рішення задачі

Проект рішення задачі представляється в формі принципової блок-схеми.

Обчислення:

= M₄Вхід: M_1,M₃Вихід: M₄

Мал.1.Принципова блок-схема обчислення множин

Примітка:При розробці алгоритму даної задачі ми вводимо множини А, В, D вже в упорядкованому вигляді, але ми нижче приводимо опис методу впорядкування множин методом простого включення.

2.3. Організація структури прграми

Для обчислення операцій

використовують метод, який базується на методі злиття. Він пропонує, що вихідні множини повинні бути відсортованими. Тому в програмі для сортування вихідних масивів будемо користуватись процедурою SYS (сортування методом простого виключення).

Представимо структуру програми у вигляді наступної блок-схеми (для програми обрано модульний принцип організації програми):

Процедура RIZ

Мал.2.Принципова блок-схема програми

У програмі вирішення даної задачі ми використовуємо наступні процедури:

1. SYS- призначена для сортування цілих додаткових чисел;

2. ОBED- призначена для організації виконання операцій об’єднання двох відсортуваних множин;

3. PERET- призначена для організації виконання операцій перетину двох відсортуваних множин;

4. RIZ- призначена для організації виконання операцій різниці двох відсортуваних множин.

2.5.Опис процедур

2.5.1. Опис процедури SYS.

2.5.1.1. Постановка задачі.

Задана послідовність чисел A = {a_і, а₂, а₃, … ,а_n}.

Необхідно упорядкувати її елементи по зростанню,тобто створити послідовність чисел В={

}, такий, щоб

Задачу вирішимо методом простого виключення.

2.5.1.2. Математична модель

Як математичну модель представимо логічну схему роботи методом простого включення. Описуємо суть методу.

Побудуємо таблицю з 3 стовбців:

1-й стовбець предначений для вказування ітерацій методу.

2-й —для несортованої послідовності (А).

3-й —для відсортованої послідовності (В).

На першому кроці ітерацій 1-й елемент з А вставляється в В, потім цей елемент видаляється з А. Далі на кожному кроці ітерацій 1-й елемент з поточної невідсортованої послідовності А вставляється в відповідне йому місце відсортованої послідовності В; потім він удаляєть з послідовності А. Покажемо роботу методу простого виключення на прикладі:

А=

і	Невідсортований список,(А)	Відсортований список,(В)
0	7, 2, 21, 17, 6, 1, 13, 5, 8.
1	2, 21, 17, 6, 1, 13, 5, 8.	7
2	21, 17, 6, 1, 13, 5, 8.	2, 7
3	17, 6, 1, 13, 5, 8.	2, 7, 21
4	6, 1, 13, 5, 8.	2, 7, 17, 21
5	1, 13, 5, 8.	2, 6, 7, 17, 21
6	13, 5, 8.	1, 2, 6, 7, 17, 21
7	5, 8.	1, 2, 6, 7,13, 17, 21
8	8.	1, 2, 5, 6, 7,13, 17, 21
9	1, 2, 5, 6, 7, 8, 13, 17, 21

Алгоритм призначений для впорядкування чисел методом простого виключення.

Крок 1: Визначити перші два елемента масива В.

Алгоритм вирішення задачі базується на методі злиття двох множин. Приведемо загальний опис вирішення алгоритму задачі.

Блок 1:використовуємо ProcedureSYS ,яка описана в лабораторній pоботі №1.

Блок 2,3: не відсортовані масиви; відсортовані масиви.

Призначений для об’єднання двох відсортованих множин А і В з використанням методу злиття.

інакше: записати в кінці масиву С елементи масиву В,