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

ПРИЛОЖЕНИЕ Б

АЛГОРИТМИЗАЦИЯ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ

1. Этапы подготовки и решения задачи на ЭВМ

 

 При разработке, отладке и внедрении программ решения различных типов задач на ЭВМ необходимо выполнять следующие виды работ:

1. Постановка задачи (техническое задание на разработку программы).

2. Математическая формулировка задачи.

3. Разработка алгоритма решения задачи.

4. Составление программы на выбранном языке программирования.

5. Подготовка исходных данных (в том числе отладочных и тестовых).

6. Ввод программы и исходных данных в ЭВМ.

7. Отладка программы с использованием исходных данных.

8. Тестирование программы на контрольном примере.

9. Решение задачи с фактическими исходными данными и получение результатов.

 

Алгоритмы циклической структуры

 

Цикл с простой переменной

При решении многих задач возникает необходимость многократного повторения отдельных этапов вычислительного процесса. Многократно повторяемый этап вычислений называют циклом, а вычислительный процесс, который содержит такие этапы, — циклическим.

В циклах повторение отдельных вычислений и их этапов целесообразно выполняется при различных значениях переменной, которая называется параметром цикла.

При организации цикла можно использовать или блок “решение” в объединении с блоками “процесс”, или специальный блочный символ “модификация”. И в том и в другом случае необходимо задать начальное значение параметру цикла, правило его изменения для перехода к новому повторению, а также условие окончания цикла.

Эта группа действий подготавливает условия для работы цикла. Кроме того, циклический алгоритм содержит группу действий, которые реализуют многократно повторяющийся участок вычислений – рабочую часть или тело цикла.

Цикл, в состав которого не входят другие циклы называется простой. На рис. 3 приведены две возможных способа организации циклического процесса. В обоих случаях параметром цикла является переменная i, которая изменяется от своего начального значения in до конечного ik c шагом  di. Если di =1, то в блоке модификации значение шага опускается.

Таким образом, рабочая область цикла повторяется тогда, когда значение параметра цикла i изменяется в границах от in до ik c шагом di.

                                  а)                                б)

                           

Рисунок 3 - Схемы организации простого цикла

 

Первый способ организации цикла (рис. 3а) предусматривает присвоение начального значения параметру цикла и его изменение с помощью блоков “Процесс”. Условие окончания цикла проверяется в блок “Решение”.

Второй вариант организации цикла (рис. 3б) предполагает автоматическое выполнение этих действий в блоке “модификация”.

Алгоритмы сортировки

       Сортировка применяется во всех без исключения областях программирования: в математических вычислениях, инженерных расчетах, при обработке данных и др.

Практически каждый алгоритм сортировки можно разбить на три части:

- сравнение, определяющее упорядоченность пары элементов;

- перестановку, меняющую местами пару элементов;

- сам сортирующий алгоритм, который в цикле осуществляет сравнение и перестановку элементов до тех пор, пока все элементы множества не будут упорядочены.

       Ниже рассмотрены четыре алгоритма сортировки, в которых производится упорядочение массива А по возрастанию значений элементов. Если требуется отсортировать массив по убыванию, то условие сравнения или выбора элементов изменяется на противоположное.

 

8.1. Сортировка обменом (пузырьковая сортировка)

Этот метод называется также пузырьковой сортировкой. Идея этого метода отражена в его названии. Самые "легкие" элементы массива "всплывают" наверх подобно пузырькам. Алгоритм метода следующий. Слева направо поочередно сравниваются два соседних элемента, и если их взаиморасположение не соответствует заданному условию упорядоченности, то они меняются местами. Далее берутся два следующих элемента и так далее до конца массива. После одного такого прохода на последней n-ой позиции массива будет стоять максимальный элемент («всплыл» первый «пузырек»). Поскольку максимальный элемент уже стоит на своей последней позиции, то второй проход обменов выполняется до n-1-го элемента. И так далее. Всего требуется n-1 проход, где n – длина массива.

Блок-схема алгоритма сортировки массива А по возрастанию значений его элементов методом обмена (пузырька) приведена на рис. 11.

  

 

Рисунок 11 - Блок-схема алгоритма сортировки массива А методом пузырька

 

Сортировка выбором

     В массиве производится поиск минимального элемента, начиная с первого его элемента. Если такой элемент найден, поменяем его местами с первым. Затем эта процедура повторяется, начиная со следующего элемента, т.е. со второго. Этот процесс продолжается подобным образом, пока не будет упорядочен весь массив.

       Блок-схема алгоритма сортировки массива А по возрастанию значений его элементов методом выбора приведена на рис. 12.

 

           

 

Рисунок 12 - Блок-схема алгоритма сортировки массива А методом выбора

 

Метод перестановок

В этом методе в цикле производится попарное сравнение двух соседних элементов. Если встречается неупорядоченная пара элементов, у которых первый элемент больше второго, то они меняются местами, т.е. производится их перестановка и цикл просмотра массива начинается сначала. Если при просмотре массива не встретилось ни одной неупорядоченной пары элементов, то цикл завершает свою работу и массив является отсортированным.

Блок-схема алгоритма сортировки массива А методом перестановок приведена на рис. 13.

          

 

Рисунок 13 - Алгоритм сортировки массива А методом перестановок

Сортировка вставкой

Массив разделяется на две части: на отсортированную и не отсортированную. Элементы из не отсортированной части поочередно выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов. Первоначально, в качестве отсортированной части массива, принимают только один первый элемент, а в качестве не отсортированной части - все остальные элементы.

Таким образом, алгоритм будет состоять из n -1 прохода (где n – длина массива), каждый из которого, будет включать четыре действия:

1. Взятие очередного, начиная со второго, i -го не отсортированного элемента и сохранение его в дополнительной переменной B;

2. Сравнение переменной B с j -ми элементами отсортированной части массива и поиск позиции j _ vst, в которой вставка взятого элемента не нарушит упорядоченности элементов этой части массива;

3. Сдвиг элементов массива вправо от j _ vst -го до i -го элемента, для того чтобы освободить найденную позицию вставки;

4. Вставка взятого элемента в найденную j _ vst позицию.

Блок-схема алгоритма сортировки массива А методом вставок приведена на рис. 14.

 

Рисунок 14 - Блок-схема алгоритма сортировки массива А методом вставок

ПРИЛОЖЕНИЕ Б

АЛГОРИТМИЗАЦИЯ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ

1. Этапы подготовки и решения задачи на ЭВМ

 

 При разработке, отладке и внедрении программ решения различных типов задач на ЭВМ необходимо выполнять следующие виды работ:

1. Постановка задачи (техническое задание на разработку программы).

2. Математическая формулировка задачи.

3. Разработка алгоритма решения задачи.

4. Составление программы на выбранном языке программирования.

5. Подготовка исходных данных (в том числе отладочных и тестовых).

6. Ввод программы и исходных данных в ЭВМ.

7. Отладка программы с использованием исходных данных.

8. Тестирование программы на контрольном примере.

9. Решение задачи с фактическими исходными данными и получение результатов.