Контрольная ОКП

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

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

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

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

3. Алгоритмический язык – формальный язык, предназначенный для записи алгоритмов. Алгоритмический язык задается набором основных символов (алфавитом), системой точных правил построения текстов (синтаксисом). Многие языки программирования, используемые при решении задач на ЭВМ, являются алгоритмическими языками (например Паскаль).

Например: Составить алгоритм нахождения суммы чисел a и b. Результат присвоить переменной S.

Словесный способ описания:

1. Введи значения переменных a и b.

2. Вычисли сумму a+b и присвой переменной S.

3. Выведи значение переменной S.

Блок-схема:

Алгоритмический язык (Pascal)

Program summa;

Var a, b, s : real;

Begin

Readln (a, b);

S := a + b;

Writeln (’S=’, s:6:2);

End.

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

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

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

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

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

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

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

Базовые структуры блок-схем.

Разветвление

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

Подпрограмма

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

Соединитель

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

Комментарии можно записывать возле любого блока.

Структурная блок-схема – это блок-схема, которая может быть выражена как композиция из четырех элементарных блок-схем: композиции, выбора (альтернатива), цикл с предусловием, цикл с постусловием

Типы алгоритмов

Алгоритмы бывают трех типов:

1. Линейные алгоритмы

2. Разветвляющиеся алгоритмы

3. Циклические алгоритмы

Линейные алгоритмы

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

Например: вычислить у=х2

Разветвляющиеся алгоритмы

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

Разветвляющиеся алгоритмы бывают в полной и сокращенной форме.

Блок-схема разветвляющегося алгоритма:

Полная форма сокращенная форма

истинно

ложно

Например: вычислить

Циклические алгоритмы

– это алгоритмы, в которых одна и та же последовательность команд (тело цикла) выполняется несколько раз.

Циклические алгоритмы бывают:

1. с предусловием

2. с постусловием

3. с параметром

Рекурсия – это метод вычисления, допустим данной нам переменной, через предыдущие переменные, то есть рекурсия – это вызов функции самой себя.

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

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

НАЧАЛО

Ввод числа Т

Ввод размерности N

i:=1

i<= N

Ввод эл-а массива а[i]

i>n

ДА

НЕТ

А

i:=i+1

i

i:=1

a[i]<=t and

i<=n

i:=i+1

i

В массиве нет

эл-в>T

А

i=n

ДА

НЕТ

Max:=-1

i:=i+1

Эл-т >T посл

едний в массиве

i<= N

(a[i]>0) and ((max=-1) or (a[max])<=a[i]))

ДА

НЕТ

Max:=i

i:=i+1

i

Max=-1

ДА

НЕТ

Нет положительных элементов после Т

max

КОНЕЦ

2. Дана целочисленная квадратная матрица. Определить сумму элементов в тех строках, которые не содержат отрицательных элементов;

НАЧАЛО

Ввод размерности n,m

i<=n

j<=m

Ввод эл-а

a[i,j]

j

i

i<=n

Flag:=false

S:=0

j:=1

k:=0

А

m=n

ДА

НЕТ

j:=1

i:=1

l:=0

j:=j+1

i:=i+1

i:=1

B

a[i,j]<0

ДА

НЕТ

Flag:=true

k:=k+1

ДА

НЕТ

Flag:=false

s

j<=m

S:=s+a[i,j]

А

j

i

ДА

НЕТ

l=n

Нет строк с поло

жительными

эл-ми

КОНЕЦ

j:=j+1

i:=i+1

B

Задана не квадратная матрица

ДА

НЕТ

k>0

l:=l+1