Лекция 7. Базовые алгоритмические структуры
Рассматриваются основные понятия об алгоритме в программах и алгоритмизации решения задач.
Алгоритм – это упорядоченная совокупность формализованных и полных команд исполнителю алгоритма (человек, ЭВМ), задающих порядок и содержание действий, которые он должен выполнить для нахождения решения любой задачи из рассматриваемого класса задач.
Алгоритм удовлетворяет следующим основным свойствам:
- Конечность (дискретность) команд и выполняемых по ним действий алгоритма.
- Выполнимость в определенной операционной среде (в определенном классе исполнителей).
- Результативность отдельных команд и всего алгоритма.
- Применимость алгоритма ко всем возможным входным данным конкретного класса задач.
- Определенность (детерминированность) команд и всего алгоритма для всех входных данных.
- Формализованное, конструктивное описание (представление) команд алгоритма.
- Минимальная полнота системы команд алгоритма.
- Непротиворечивость любых команд алгоритма на любом наборе входных данных.
На алгоритмическом языке Паскаль любой алгоритм простой (не модульной, не составной) структуры имеет следующий стандартный вид:
Program <имя (заголовок) алгоритма>; Uses <список подключаемых библиотек, если они нужны>; { комментарии, если нужны } Label <список меток (имен участков программ), если они нужны>; { комментарии } Const <список констант (не изменяемых величин), если они нужны>; { комментарии } Type <список имен и типов структур данных, если они нужны>; { комментарии } Var <список имен и типов переменных, если они нужны>; { комментарии } { < условия задачи и применимости алгоритма > } { < цель составления и выполнения алгоритма > }Begin <команды ввода входных данных, если они нужны>; { комментарии } <тело алгоритма (команды управления и преобразования алгоритма)>; { комментарии } <команды вывода результатов (выходных данных), если они нужны>; { комментарии }End.Пример. Программа вычисления объема v правильного цилиндра с радиусом основания r и высотой h.
Program VСil;Uses Crt { подключение библиотеки ввода/вывода на экран "в звуке и цвете" }Const pi = 3.14;Var r, h, v: real; { для правильного цилиндра с радиусом основания r и высотой h } { вычислить и выдать на экран значение его объема v }Begin ClrScr; { команда очистки экрана (от данных предыдущей задачи) } ReadLn (r, h); { ввод входных параметров } v:=pi*r*r*h; { вычисление объема по формуле для цилиндра } WriteLn (‘Вычисленный объем цилиндра равен ’, v) { вывод результата }End.Приведем таблицу наиболее часто используемых в языке Паскаль функций и процедур.
| Обычная запись | Паскаль |
| Квадрат числа х | sqr(x) |
| Корень квадратный из x | sqrt (x) |
| Модуль |х| | abs (x) |
| sin x | sin(x) |
| cos x | cos(x) |
| tg x | tg(x) |
| ctg x | ctg(x) |
| arcsin x | arcsin (x) |
| arccos x | arccos(x) |
| arctg x | arctg(x) |
| Натуральный логарифм ln x | ln(x) |
| Степень числа е = 2, 7... или еx | exp(x) |
| Остаток от деления целого х на целое у | x mod y |
| Частное от деления целого х на целое y | x div y |
| Целая часть числа х (вещественного) | int(x) |
| Случайное число от 0 до х | rnd(x) |
| Длина текста х в символах | length (x) |
Пример. Результаты применения этих функций: sqrt(9) = 3, abs(–5) = 5, sin(0) = 0, cos(0) = 1, ln(1) = 0, exp(1 ) =e, 23 mod 5 = 3, 20 mod 5 = 0, 23 div 5 = 4, 20 div 5 = 4, int(2.7) = 2, int(2) = 2, rnd(0) = 0.231356, length(‘информ’) = 6.
Порядок выполнения операций (старшинство операций – по убыванию) в языке Паскаль:
- вычисление выражений в скобках;
- вычисление стандартных функций;
- умножение и деление (обозначаются "*" и "/");
- сложение и вычитание (обозначаются "+" и "–").
Пример. Выражение b*c + (d/t*(v/n/m))*sin(x) вычисляется в следующем порядке (слева направо): v/n, (v/n)/m, d/t, (d/t)*(v/n/m), sin(x), b*c, (d/t*(v/n/m))*sin(x), b*c+(d/t*(v/n/m))*sin(x) и эквивалентно математическому выражению: 
.
Рассмотрим базовые простые команды языка Паскаль.
1. Команда описания (заголовка) алгоритма (программы) :
Program <имя алгоритма>;,где <имя алгоритма> – имя, задаваемое составителем программы (краткое, полное, грамотное отражение сути алгоритма ).
2. Ввод – команда ввода в рассмотрение (в тело алгоритма ) тех или иных входных параметров:
Read (<список вводимых параметров>);или
ReadLn (<список вводимых параметров>);.Первая команда вводит данные с текущей позиции экрана (где стоит курсор), вторая – с новой строки экрана.
3. Вывод – команда вывода на экран тех или иных входных или выходных параметров алгоритма:
Write (<список выводимых параметров>);или
WriteLn (<список выводимых параметров>);.Первая команда выводит данные с текущей позиции экрана (где стоит курсор), вторая – с новой строки экрана.
4. Присваивание – команда изменения текущего значения переменной вида:
<идентификатор> := <выражение>;,где <идентификатор> соответствует имени переменной, <выражение> – корректно записанное выражение. Знак ":=" означает последовательное выполнение двух действий: определение текущего значения <выражения> и замена текущего значения переменной, имя которой задано <идентификатором>, на новое значение, равное значению <выражения>.
- Команда начала алгоритма (блока) – команда Begin.
- Команда завершения алгоритма (блока) – команда End.
7. Команда вставки комментариев в текст алгоритма имеет вид:
<комментируемое в программе> <текст комментария>.
Комментировать можно любой объект в программе. Обычно комментируют переменную, структуру данных, команду, группу команд.
Различают три базовые алгоритмические структуры: следование, ветвление, повторение.
1. Структура следование состоит из двух команд с указанной очередностью их выполнения и имеет вид:
<команда – предшественник>;<команда – преемник>.2. Структура типа ветвления в полной форме состоит из некоторого условия, проверяемого на истинность при выполнении структуры, команды, выполняемой при выполнении проверяемого условия, и команды, выполняемой при невыполнении условия. Структура имеет вид
if <условие> then <команда, выполняемая при выполнении условия> else <команда, выполняемая при невыполнении условия>;.Ключевые (служебные) слова Паскаля – if (если), then (то), else (иначе). Ключевые слова нельзя изменять, заменять, так как их эталоны закреплены в переводчике с языка Паскаль (о нем подробнее – ниже).
Пример. Команда вида
if (х>y) { если текущее значение х больше текущего значения y, } then у := х { то текущее значение у полагаем равным текущему значению х, } else x:= y; { иначе (при х <= y) текущее значение x заменяем на текущее значение y }.Структура типа ветвления в неполной форме – частный случай ветвления в полной форме, в которой, при невыполнении условия, управление просто передается следующей команде и больше никаких действий команда ветвления не осуществляет. Эта структура имеет вид
if <условие> then <команда, выполняемая при исполнении условия>; .3. Структура повторения (цикл) служит для компактной записи одного и того же набора команд, повторяемых для различных значений параметров команд.
Структура повторения типа "пока ( while )" записывается в виде:
while <условие продолжения повторения> do <повторяемая команда>;или
while <условие продолжения повторения> do begin <повторяемая команда номер 1>; <повторяемая команда номер 2>; . . . <повторяемая команда номер N> end;.Дошел до сюда 01.11.14 Сделал примеры по каждой структуре
Ключевые слова Паскаля – while (пока), do (выполнять), begin (начало), end (конец).
Телом цикла называется последовательность повторяемых команд, которая может быть и пустой (редко встречаемый случай).
Часть команды цикла " while <условие продолжения повторения>" – заголовок цикла.
Данный цикл выполняется по правилу: если условие повторения для текущих его параметров не выполнено, то повторение команд (тела) цикла на этом завершается; если же оно выполнено, то выполняется тело цикла и опять проверяется условие повторения команд тела цикла.
Пример. Пусть необходимо находить сумму всех нечетных элементов натурального ряда чисел до тех пор, пока эта сумма не превысит значение n. Слагаемое, при котором эта сумма превысит n – включать в сумму.
"Забудем" временно чисто математическое решение этой задачи – с использованием суммы арифметической прогрессии с шагом 2. Алгоритм программа) имеет вид
Program Summa;Uses Crt; { подключение библиотеки ввода/вывода на экран "в звуке и цвете"}Var i, n, s: real; { для ряда чисел 1, 3, 5, …, } { найти и выдать сумму s всех первых чисел ряда, для которых впервые s > n }Begin ClrScr; { команда очистки экрана (от данных предыдущей задачи) } ReadLn (n); { ввод входного параметра } s:=1; { начальное значение суммы до входа в цикл } i:=1; { количество просуммированных чисел в начале } while (s<=n) do { заголовок цикла (проверка условия выхода из цикла) } begin i:=i+2; { находим новое слагаемое } s:=s+i { добавили к предыдущему значению суммы новое слагаемое } end; WriteLn ('Вычисленная сумма равна ', s); { вывод результата }End.Вторая форма повторения – цикл типа "до" ( for ), которая имеет вид
for <переменная> := <начальное значение переменной> to <конечное ее значение> do <команда>;или
for <переменная> := <начальное значение переменной> to <конечное ее значение> do begin <повторяемая команда номер 1>; <повторяемая команда номер 2>; . . . <повторяемая команда номер N> end;.Здесь <переменная> – имя, идентификатор пересчитываемой переменной.
Ключевые слова Паскаля – for (для), to (к).
Этот цикл выполняется по правилу: для начального значения переменной выполняются команды тела цикла по порядку и затем проверяется, превысило ли текущее значение переменной ее заданного конечного значения; если превысило – цикл заканчивается, иначе значение переменной увеличивается на единицу и снова повторяется тело цикла и т.д.
Пример. Необходимо вычислить среднюю стоимость единицы всех n видов товаров (единица измерения – одна и та же, например, тонна), если стоимость единицы каждого товара увеличивается на 10, а наименьшая стоимость единицы товара равна 2. Если "забыть" временно лучшее, "чисто математическое" решение этой задачи, то алгоритм будет иметь вид
Program ST;Uses Crt { подключение библиотеки ввода/вывода на экран "в звуке и цвете"}Var i, n, s, x: integer; { стоимость единицы товара дается рядом n чисел вида: 2, 12, 22, 32, … } { найти и выдать среднюю стоимость s всех n товаров s }Begin ClrScr { команда очистки экрана (от данных предыдущей задачи) } ReadLn (n); { ввод входного параметра } s:=0; { начальное значение суммы до входа в цикл } x:=2; { начальное значение стоимости товара – стоимость первого товара } for i:=1 to n do { заголовок цикла (проверка условия выхода из цикла) } begin s:=s+x; { находим новую сумму товаров } x:=x+10 { находим стоимость следующего товара } end; WriteLn ('Вычисленная средняя стоимость товаров равна ', s/n : 5:5); { вывод результата }End.Рассмотрим примеры алгоритмизации (программирования) задач на языке Паскаль.
Пример. Составим алгоритм вычисления факториала заданного натурального числа n, то есть произведения n! = 1 * 2 * 3 * ... * (n – 1) * n c использованием рекуррентной формулы n! = (n – 1)! * n. Опишем метод решения. Для этого заметим цепочку справедливых равенств:
1! = 1, 2! = 1 * 2 = 1! * 2, 3! = 1 * 2 * 3 = 2! * 3, ..., m! =1 * 2 * 3 * ... * (m – 1) * m = (m – 1)! * m.
Следовательно, для вычисления факториала m! необходимо факториал (m – 1)! домножить на m, где m = 1, 2, ..., n. Программа на Паскале имеет вид
Program Factorial;Uses Crt;Var n, f, i: integer; { дано натуральное число n } { найти и выдать произведение всех натуральных чисел до n включительно }Begin ClrScr; WriteLn('Введите число n : '); { приглашение к вводу входного параметра } ReadLn(n); { ввод входного параметра } f:=1; { начальному значению f присваивается 1, то есть 1!=1 } for i:=1 to n do { цикл умножения текущего произведения f на текущее i } f:=f*i; { предыдущее значение факториала умножаем на текущее значение i } WriteLn('Полученный результат f : ',f); { вывод результата }End.Пример. Составим алгоритм перевода заданного десятичного натурального числа n в двоичную систему. Метод решения определяется процедурой перевода – последовательными делениями числа n на 2 и последующим сбором остатков от деления. Если последовательно выдавались с равные 1,0,1,0,0,1, то двоичное изображение c равно 100101. Алгоритм имеет вид