9)Типовые структуры в алгоритмах: ветвление, обход, циклы.

Отказ от естественного языка требует формализации способа записи алгоритма и использования стандратных приемов построения алгоритмов в виде комбинаций базовых алгоритсмических структур.Их всего три : обход(следование) ветвление и цикл.

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

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

Структура цикла –строки инициализации(подготавливают выполнение цикла) –тело цикла(группа операторов ,выполнение которых повторяется) – условие завершение ( используется для завершения работы цикла)

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

Обход- следование действий друг за другом.  В таких алгоритмах все блоки имеют последовательное соединение логической связью передачи информационных потоков. В них могут использоваться все блоки, за исключением блоков проверки условия и модификации. Линейные(обходные,следованные) алгоритмы, как правило, являются составной частью любого алгоритмического процесса.

10)Типовые алгоритмы обработки данных: ввод-вывод одномерных и двухмерных массивов, сортировка массивов, поиск наибольшего или наименьшего элемента в массиве.

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

Одномерные и двухмерные массивы. Ввод и вывод

Массивы с одним индексом- одномерные .Они представляют собой списки данных.Для многих задач выделяют многомерные массивы, с несколькими индексами.Например, двухмерный массив можно рассмотреть как таблицув которой один индекс задает номер столбца, а другой – номер строки.Чтот бы объявить двухмерный массивы, надо указать диапазон изменения обоих индексов .Необходимые зн-я обычно задаются через запятую.

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

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

• количество шагов алгоритма, необходимых для упорядочения;

• количество сравнений элементов;

• количество перестановок, выполняемых при сортировке.

• Сортировка отбором ('Очевидный' алгоритм сортировки - перебором находится наименьший элемент, он меняется местами с элементом, стоящим на нулевом месте, затем находится наименьший среди оставшихся и меняется местами с элементом, стоящим на первом месте... Цикл заканчивается когда будут выбраны все элементы)

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

• Пузырьковая сортировка (

• Сортировка слиянием ( 'разделяй и властвуй' - исходный массив делится пополам, каждая половинка упорядочивается, затем производится слияние. Для сортировки половинок используется та же функция, что и для сортировки всего массива, функция слияния выделена для экономии места в стеке)

• Сортировка с помощью кучи (

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

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

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

Переменные:

m - массив;

n - количество элементов в массиве;

i - переменная цикла;

max - значение наибольшего элемента;

numer_max - его порядковый номер.

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

 

max := m[1]; {Cчитать 1-й элемент максимальным} numer_max := 1; {Запомнить номер максимального элемента}

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

Сравнение очередного элемента массива с максимальным осуществляется оператором if m[i] > max then. Если очередной элемент массива больше, чем максимальный, то следует считать его значение максимальным и запомнить его индекс. Данный фрагмент кода записывается таким образом:

 

for i:= 2 to n do begin if m[i]> max then begin max:= m[i]; numer_max:= i; end; end;

 

Текст процедуры получится таким:

 

procedure Maximum(m:myarray; var max,numer_max:integer); { Процедура нахождение максимального элемента массива и его номера. m : имя массива; max : значение максимального элемента; maxi : номер максиального элемента в массиве. } var i: integer; begin max:=m[1]; numer_max:=1; for i:= 2 to n do begin if m[i]> max then begin max:= m[i]; numer_max:= i; end; end; end;

Составим программу. В ней воспользуемся для заполнения массива уже знакомой процедурой - Init2, которая заполняет массив случайными числами из заданного интервала.

 

program Max_elem; const n = 20; type myarray= array[1..count] of byte; var m:myarray; i, max, maxi: integer; Procedure Init2(a,b: integer; Var m : myarray); ... procedure Maximum(m:myarray; var max,numer_max:integer); ... begin {main} init2(0, 50, m); maximum(m, max, maxi); writeln('Максимальный элемент - ', max); writeln('Он расположен на ',maxi, ' месте.'); end.

Для поиска минимального элемента и его порядкового номера  меняем обозначения:

min - значение наименьшего элемента;

numer_min - его порядковый номер.

Перед началом поиска предполагаем, что первый элемент массива минимальный, и его индекс -  номер минимального элемента. При сравнении очередного элемента с минимальным,  меняем знак отношения на противоположный.