ОКП вар 21

1. Определение алгоритма

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

2. Свойства алгоритмов

• последовательность – все действия располагаются друг за другом, и переход к следующему действию возможен только после завершения предыдущего действия;

• определенность – каждое действие алгоритма должно быть четко определено и однозначно выполнено, не оставляя места произволу;

• дискретность – исполнение алгоритма должно распадаться на выполнение отдельных шагов. Выполнение следующего шага происходит только после выполнения предыдущего шага;

• конечность – выполнение алгоритма завершается после конечного числа шагов;

• результативность – завершение алгоритма за конечное число шагов и получение искомого результата. Сообщение о том, что алгоритм не имеет решения, тоже является результатом.

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

3. Способы описания алгоритмов

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

Блок-схема – графическая форма записи алгоритма.

Программа – алгоритм, записанный на понятном компьютеру языке программирования.

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

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

• Базовая структура «следование». Образуется последовательностью действий, следующих одно за другим:

• Базовая структура "ветвление". Обеспечивает в зависимости от результата проверки условия (да или нет) выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран. Структура «ветвление» существует в четырех основных вариантах:

1. «если - то»

2. «если – то - иначе»;

3. «выбор»;

4. «выбор - иначе».

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

5. Структурированные схемы и их построение

Структурированная схема строится из фрагментов, каждый из которых имеет одну входную и одну выходную стрелку. Простейший фрагмент— пустой— состоит из одной стрелки, входной и выходной одновременно:

Далее идет фрагмент, состоящий из одного оператора

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

6. Линейные и разветвляющиеся структуры

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

Ветвление(развилка) – такая форма организации действий, при которой в зависимости от выполнения или невыполнения конкретного условия совершается либо одна либо другая последовательность действий.

7. Циклические структуры. Типы циклов

Циклом называют повторение одних и тех же действий (шагов).

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

В цикле с предусловием условие проверяется до тела цикла, в цикле с постусловием – после тела цикла.

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

В цикле с предусловием проверяется условие продолжения цикла, в цикле с постусловием – условие выхода из цикла.

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

8. Предопределенные процессы. Рекурсия

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

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

Прямой (непосредственной) рекурсией является вызов функции внутри тела этой функции.

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

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

Задача №1.

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

i<n&&

a[i]=T

i=i+1

да

нет

i=i+1

нет

max=0

нет

да

max=a[i]

i=i+1

нет

да

нет

n=7, T=3
-4 6 8 -4 1 -1 -2	При i=7 вывод «Нет элементов, равных Т». Стоп
-7 1 -5 -10 -3 1 3	При i=7 и а[7]=3 вывод «Т-последний элемент». Стоп
9 -2 2 -7 3 2 9	Вывод «После Т нету отрицательных элементов». Стоп
4 3 -7 6 -1-3 -4	При i=3, max=-7; num=3; При i=5, max=-1, num=5; При i=6, max=-1, num=5; При i=7, max=-1, num=5; Вывод «5». Стоп.

Задача №2.

Проверить, все ли столбцы матрицы упорядочены по убыванию. Если нет, то упорядочить первый неупорядоченный столбец.

i=0, j=0, count=0

нет

да

нет

да

нет

buf=a[i,j]

нет

a[i,j]=a[i+1,j]

нет

a[i+1,j]=buf

нет

count=1

нет

i=i+1

нет

j=j+1

нет

да

нет

n=4, m=5
28 19 7 29 0 24 22 3 4 0 15 23 21 3 12 0 9 1 27 18	Вывод «Матрица с упорядоченным столбцом» 28 23 7 29 0 24 22 3 4 0 15 19 21 3 12 0 9 1 27 18 Стоп.
29 16 16 29 14 18 14 13 20 11 11 11 11 10 7 10 9 8 2 0	Вывод «Все столбцы матрицы упорядочены по убыванию» 29 16 16 29 14 18 14 13 20 11 11 11 11 10 7 10 9 8 2 0 Стоп.

11