35. Базовые алгоритмические структуры

Алгоритмы можно представлять как некоторые структуры, состоящие из отдельных базовых (т.е. основных) элементов. Естественно, что при таком подходе к алгоритмам изучение основных принципов их конструирования должно начинаться с изучения этих базовых элементов. Для их описания используется язык схем алгоритмов.

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

Характерной особенностью базовых структур является наличие в них одного входа и одного выхода.

"Следование" или линейный вычислительный процесс — это процесс, блоки которого выполняются последовательно один за другим (порядок выполнения блоков естественный).

Базовая структура "ветвление" или разветвляющийся процесс обеспечивает в зависимости

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

36. Базовая структура "цикл"

Цикл – последовательность операторов, которая может быть выполнена более одного раза.

Базовая структура "цикл" или циклический процесс обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла.

Циклы:

- Арифметические – число повторений заранее известно: циклы с параметром.

- Итерационные – количество повторений не известно заранее (циклы с предусловием и циклы с постусловием)

37. Алгоритм вычисления суммы бесконечного ряда с использованием рекуррентной формулы.

38. Алгоритм табулирования функции.

39.Внутренняя и внешние сортировки. Мера эффективности алгоритмов сортировки.

Постановку задачи

Имеется одномерный массив чисел, состоящий из n элементов: X[n]. Переставить элементы массива так, чтобы их значения располагались в порядке возрастания. Другими словами, для любой пары элементов X[i] и X[i+1] выполняется неравенство вида:

X[i] <= X[i+1].

Устойчивая (стабильная) сортировка — сортировка, которая не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи. Большинство простых методов сортировки устойчивы, большинство сложных — нет.

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

Различают два вида сортировки данных:

- сортировка данных, расположенных в оперативной памяти компьютера (внутренняя сортировка);

- сортировка данных, расположенных на внешних запоминающих устройствах (внешняя сортировка).

43. Постановка задачи сортировки. Принцип «разделяй и властвуй». Особенности сортировки слиянием. Привести словесное описание этапов сортировки слиянием. Рассмотреть на примере идею слияния двух отсортированных массивов.

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

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