t1l2.md 32 KB
| Предыдущая лекция | Следующая лекция | |
|---|---|---|
| Основные понятия алгоритмизации | Содержание | Логические основы алгоритмизации |
Основные алгоритмические конструкции
Алгоритм применительно к вычислительной машине — точное предписание, т.е. набор операций и правил их чередования, при помощи которого, начиная с некоторых исходных данных, можно решить любую задачу фиксированного типа.
Алгоритмы в зависимости от цели, начальных условий задачи, путей ее решения, определения действий исполнителя подразделяются следующим образом:
Линейный алгоритм
Линейный алгоритм — набор команд (указаний), выполняемых последовательно друг за другом.
Основным элементарным действием в линейных алгоритмах является присваивание значения переменной величине. Если значение константы определено видом ее записи, то переменная величина получает конкретное значение только в результате присваивания. Присваивание может осуществляться двумя способами: с помощью команды присваивания и с помощью команды ввода.
Рассмотрим пример. В школьном учебнике математики правила деления обыкновенных дробей описаны так:
- Числитель первой дроби умножить на знаменатель второй дроби.
- Знаменатель первой дроби умножить на числитель второй дроби.
- Записать дробь, числитель которой есть результат выполнения пункта 1, а знаменатель — результат выполнения пункта 2.
В алгебраической форме это выглядит следующим образом:
$$\frac{a}{b} : \frac{c}{d} = \frac{a * d}{b * c} = \frac{m}{n}$$
Построим алгоритм деления дробей для ЭВМ. В этом алгоритме сохраним те же обозначения для переменных, которые использованы в записанной выше формуле. Исходными данными являются целочисленные переменные а, Ь, с, d. Результатом — также целые величины m и n. Блок-схема и текст алгоритма на C# приведены ниже.
flowchart TD
begin([Начало])
begin-->input[/Ввод a, b, c, d/]
input-->proc["`m = a * d
n = b * c`"]
proc-->output[/Вывод m, n/]
output-->finish([Конец])
Console.WriteLine("Enter a, b, c, d: ");
var a = int.Parse(Console.ReadLine());
var b = int.Parse(Console.ReadLine());
var c = int.Parse(Console.ReadLine());
var d = int.Parse(Console.ReadLine());
var m = a * d;
var n = b * c;
Console.WriteLine($"m={m}, n={n}");
Формат команды присваивания следующий:
переменная = выражение
Знак = нужно читать как «присвоить».
Команда присваивания обозначает следующие действия, выполняемые компьютером:
- Вычисляется выражение.
- Полученное значение присваивается переменной.
В приведенном выше алгоритме присутствуют две команды присваивания. В блок-схемах команда присваивания записывается в прямоугольнике. Такой блок называется вычислительным блоком.
В описаниях алгоритмов необязательно соблюдать строгие правила в записи выражений. Их можно писать в обычной математической форме. Это еще не язык программирования со строгим синтаксисом.
В приведенном алгоритме присутствуют команды ввода:
var a = int.Parse(Console.ReadLine());
var b = int.Parse(Console.ReadLine());
var c = int.Parse(Console.ReadLine());
var d = int.Parse(Console.ReadLine());
В блок-схеме команда ввода записывается в параллелограмме — блоке ввода-вывода. При выполнении данной команды процессор прерывает работу и ожидает действий пользователя. Пользователь должен набрать на устройстве ввода (клавиатуре) значения вводимых переменных и нажать на клавишу ввода Enter. Обычно с помощью команды ввода присваиваются значения исходных данных, а команда присваивания используется для получения промежуточных и конечных величин.
Полученные компьютером результаты решения задачи должны быть сообщены пользователю. Для этих целей предназначена команда вывода:
Console.WriteLine($"m={m}, n={n}");
С помощью этой команды результаты выводятся на экран или на устройство печати на бумагу.
Поскольку присваивание является важнейшей операцией в вычислительных алгоритмах, обсудим ее более подробно.
Рассмотрим последовательное выполнение четырех команд присваивания, в которых участвуют две переменные величины a и b.
В приведенной ниже таблице напротив каждой команды присваивания указываются значения переменных, которые устанавливаются после ее выполнения.
| Команда | a | b |
|---|---|---|
| a=1 | 1 | - |
| b=a*2 | 1 | 2 |
| a=b | 2 | 2 |
| b=a+b | 2 | 4 |
Этот пример иллюстрирует три основных свойства команды присваивания:
- пока переменной не присвоено значение, она остается неопределенной;
- значение, присвоенное переменной, сохраняется в ней вплоть до выполнения следующей команды присваивания этой переменной;
- новое значение, присваиваемое переменной, заменяет ее предыдущее значение.
Рассмотрим один очень полезный алгоритм, который приходится часто использовать при программировании. Даны две величины: Х и Y. Требуется произвести между ними обмен значениями. Например, если первоначально было Х=1, Y=2, то после обмена должно стать: Х=2, Y=1.
Хорошей моделью для решения этой задачи является следующая ситуация: имеются два стакана — один с молоком, другой с водой. Требуется произвести обмен их содержимым. Всякому ясно, что в этом случае нужен дополнительный третий пустой стакан. Последовательность действий будет следующей: 1) перелить из первого стакана в третий; 2) перелить из второго в первый; 3) перелить из третьего во второй. Цель достигнута!
По аналогии для обмена значениями двух переменных нужна третья дополнительная переменная. Назовем ее Z. Тогда задача обмена решается последовательным выполнением трех команд присваивания:
| Команда | X | Y | Z |
|---|---|---|---|
| ввод X, Y | 1 | 2 | - |
| Z = X | 1 | 2 | 1 |
| X = Y | 2 | 2 | 1 |
| Y = Z | 2 | 1 | 1 |
Аналогия со стаканами не совсем точна в том смысле, что при переливании из одного стакана в другой первый становится пустым. В результате же присваивания (Х = Y) переменная, стоящая справа (Y), сохраняет свое значение.
Алгоритм для деления дробей имеет линейную структуру. В нем все команды выполняются в строго однозначной последовательности, каждая по одному разу. Линейный алгоритм составляется из команд присваивания, ввода, вывода и обращения к вспомогательным алгоритмам (об этом позже).
При описании алгоритмов в блок-схемах типы, как правило, не указываются (но подразумеваются). В алгоритмах для всех переменных типы указываются явно. В них используются следующие обозначения типов: Int — целый тип, Float — вещественный тип, String — символьный (литерный) тип, Boolean — логический тип. В алгоритме для деления дробей для всех переменных указан тип Int.
Разветвляющийся алгоритм
Разветвляющийся алгоритм — алгоритм, содержащий хотя бы одно условие, в результате проверки которого ЭВМ обеспечивает переход на один из двух возможных шагов.
Циклический алгоритм
Циклический алгоритм — алгоритм, предусматривающий многократное повторение одного и того же действия (одних и тех же операций) над новыми исходными данными. К циклическим алгоритмам сводится большинство методов вычислений, перебора вариантов. Цикл программы — последовательность команд (серия, тело цикла), которая может выполняться многократно (для новых исходных данных) до удовлетворения некоторому условию.
Составим алгоритм решения квадратного уравнения: ax2+bx+c=0
Задача хорошо знакома из математики. Исходными данными здесь являются коэффициенты а, b, с. Решением в общем случае будут два корня х1 и х2, которые вычисляются по формуле:
$$x_{1,2} = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$$
Console.WriteLine("Введите a, b, c: ");
var a = int.Parse(Console.ReadLine());
var b = int.Parse(Console.ReadLine());
var c = int.Parse(Console.ReadLine());
var d = b * b - 4 * a * c;
var x1 = (-b + Math.Sqrt(d)) / (2 * a);
var x2 = (-b - Math.Sqrt(d)) / (2 * a);
Console.WriteLine($"x1={x1}, x2={x2}");
Введите a, b, c:
3
2
1
x1=NaN, x2=NaN
Слабость такого алгоритма видна невооруженным глазом. Он не обладает важнейшим свойством, предъявляемым к качественным алгоритмам, — универсальностью по отношению к исходным данным. Какими бы ни были значения исходных данных, алгоритм должен приводить к определенному результату и завершать работу. Результатом может быть число, но может быть и сообщение о том, что при определенных данных задача решения не имеет. Недопустимы остановки в середине алгоритма из-за невозможности выполнить какую-то операцию. Упомянутое свойство называют результативностью алгоритма (в любом случае должен быть получен какой-то результат).
Чтобы построить универсальный алгоритм, сначала требуется тщательно проанализировать математическое содержание задачи.
Решение уравнения зависит от значений коэффициентов а, b, с. Вот анализ рассмотренной выше задачи (ограничиваемся только поиском вещественных корней):
если а = 0, b = 0, с = 0, то любое х — решение уравнения;
если а = 0, b = 0, с <> О, то уравнение действительных решений не имеет;
если а = 0, b <> О, то это линейное уравнение, которое имеет одно решение х = -c/b;
если а<>0 и d=b2-4ac >= 0, то уравнение имеет два вещественных корня (формулы приведены выше);
если a<>0 и d<0, то уравнение не имеет вещественных корней.
flowchart TD
begin([Начало])
begin-->input[/Ввод a, b, c/]
input-->if1{a = 0}
if1-->|Да|if2{b = 0}
if2-->|Да|if3{c = 0}
if3-->|Да|out1[/Любое x/]
if3-->|Нет|out2[/Нет решений/]
out1-->finish([Конец])
out2-->finish
if2-->|Нет|case1[x := -c/b]
case1-->out3[/Вывод x/]
out3-->finish
if1-->|Нет|case2[d := b<sup>2</sup> - 4ac]
case2-->if4{d < 0}
if4-->|Да|out4[/Нет вещественных корней/]
out4-->finish
if4-->|Нет|case3["$${x1 := (-b + \sqrt{d}) / 2a}$$"]
case3-->proc1["$${x2 := (-b - \sqrt{d}) / 2a}$$"]
proc1-->out5[Вывод x1, x2]
out5-->finish
В этом алгоритме многократно использована структурная команда ветвления. Общий вид команды ветвления в блок-схемах и на ЯП следующий:
flowchart TD
A{условие}
A-->|да|B[Процесс 1]
A-->|нет|C[Процесс 2]
if (условие) {процесс 1}
else {процесс 2}
Вначале проверяется условие (вычисляется отношение, логическое выражение). Если условие истинно, то выполняется процесс 1 — последовательность команд, на которую указывает стрелка с надписью «да» (положительная ветвь). В противном случае выполняется процесс 2 (отрицательная ветвь).
Если на ветвях одного ветвления содержатся другие ветвления, то такой алгоритм имеет структуру вложенных ветвлений. Именно такую структуру имеет алгоритм «Корни квадратного уравнения».
Рассмотрим следующую задачу: дано целое положительное число n. Требуется вычислить n! (n-факториал). Вспомним определение факториала:
$$n! = \begin{cases} 1, & \text{если n = 0} \\ 1 * 2 ... n, & \text{если n $\geq$ 0} \end{cases} $$
Ниже приведена блок-схема алгоритма. В нем используются три переменные целого типа: n — аргумент; i — промежуточная переменная; F — результат. Для проверки правильности алгоритма построена трассировочная таблица. В такой таблице для конкретных значений исходных данных по шагам прослеживается изменение переменных, входящих в алгоритм. Данная таблица составлена для случая п = 3.
flowchart TD
begin([Начало])
begin-->input[/Ввод n/]
input-->proc1[F := 1]
proc1-->proc2[i := 1]
proc2-->if{i $$\leq$$ n}
if-->|Да|proc3[F := F * i]
proc3-->proc4[i := i + 1]
proc4-->if
if-->|Нет|output[/Вывод F/]
output-->finish([Конец])
| Шаг | n | F | i | Условие |
|---|---|---|---|---|
| 1 | 3 | |||
| 2 | 1 | |||
| 3 | 1 | |||
| 4 | 1<=3, да | |||
| 5 | 1 | |||
| 6 | 2 | |||
| 7 | 2<=3, да | |||
| 8 | 2 | |||
| 9 | 3 | |||
| 10 | 3<=3, да | |||
| 11 | 6 | |||
| 12 | 4 | |||
| 13 | 4<=3, нет | |||
| 14 | вывод |
Трассировка доказывает правильность алгоритма. Теперь запишем этот алгоритм на ЯП.
fun main(){
println("Введите n:")
val n = readLine()!!.toInt()
var F = 1
var i = 1
while (i<=n){
F *= i // F = F*i
i++ // i = i+1
}
println("F=$F")
}
Этот алгоритм имеет циклическую структуру. В алгоритме использована структурная команда цикл-пока, или цикл с предусловием. Общий вид команды цикл-пока в блок-схемах и в ЯП следующий:
flowchart TD
start([Начало])
start-->if{условие}
if-->|Да|case[код]
case-->if
if-->|Нет|finish([Конец])
while (условие) {
//серия
}
Выполнение серии команд (тела цикла) повторяется, пока условие цикла истинно. Когда условие становится ложным, цикл заканчивает выполнение.
Цикл с предусловием — это основная, но не единственная форма организации циклических алгоритмов. Другим вариантом является цикл с постусловием. Вернемся к алгоритму решения квадратного уравнения. К нему можно подойти с такой позиции:
если а = 0, то это уже не квадратное уравнение и его можно не рассматривать. В таком случае будем считать, что пользователь ошибся при вводе данных, и следует предложить ему повторить ввод. Иначе говоря, в алгоритме будет предусмотрен контроль достоверности исходных данных с предоставлением пользователю возможности исправить ошибку. Наличие такого контроля — еще один признак хорошего качества программы.
flowchart TD
start([Начало])
start-->input[/Ввод a, b, c/]
input-->if1{a $$\neq$$ 0}
if1-->|нет|input
if1-->|Да|proc1[$$d := b^2 - 4ac$$]
proc1-->if2{$$d \geq 0$$}
if2-->|Нет|output[/Нет вещественных корней/]
output-->finish
if2-->|Да|proc2["$$x1 := (-b + \sqrt{d})/(2a)$$"]
proc2-->proc3["$$x2 := (-b - \sqrt{d})/(2a)$$"]
proc3-->output2[/Вывод x1, x2/]
output2-->finish([Конец])
fun main(){
var a: Int
do {
println("Введите a:")
a = readLine()!!.toInt()
} while(a!=0)
val d = b*b-4*a*c
if(d<0) println("нет вещественных корней")
else{
val x1 = (-b+sqrt(d.toFloat()))/(2*a)
val x2 = (-b-sqrt(d.toFloat()))/(2*a)
println("x1=$x1, x2=$x2")
}
}
В общем виде структурная команда цикл с постусловием или цикл — до представляется так:
flowchart TD
start([начало цикла])
start-->proc[серия]
proc-->if{условие}
if-->|нет|proc
if-->|да|finish([конец цикла])
do {
//серия
} while (условие)
Здесь используется условие окончания цикла. Когда оно становится истинным, цикл заканчивает работу.
Составим алгоритм решения следующей задачи: даны два натуральных числа М и N. Требуется вычислить их наибольший общий делитель — НОД(M, N).
Эта задача решается с помощью метода, известного под названием алгоритма Евклида. Его идея основана на том свойстве, что если M>N, то НОД(М, N) = НОД(М-N, N). Другой факт, лежащий в основе алгоритма, тривиален — НОД(М, М) = М. Для «ручного» выполнения этот алгоритм можно описать в форме следующей инструкции:
- Если числа равны, то взять их общее значение в качестве ответа; в противном случае продолжить выполнение алгоритма
- Определить большее из чисел
- Заменить большее число разностью большего и меньшего значений
Вернуться к выполнению пункта 1
flowchart TD start([Начало]) start-->input[/Ввод N, N/] input-->if1{M ≠ N} if1-->|Да|if2{M > N} if2-->|Да|proc1[M := M - N] proc1-->if1 if2-->|Нет|proc2[N := N - M] proc2-->if1 if1-->|Нет|output[/Вывод M/] output--->finish([Конец])fun main(){ println("Введите m, n: ") var m = readLine()!!.toInt() var n = readLine()!!.toInt() while (m!=n){ if(m>n) m = m-n else n = n-m } println("НОД = $m") }
Алгоритм имеет структуру цикла с вложенным ветвлением. Проделайте самостоятельно трассировку этого алгоритма для случая М = 18, N = 12. В результате получится НОД = 6, что, очевидно, верно.
Вспомогательные алгоритмы и процедуры
В теории алгоритмов известно понятие вспомогательного алгоритма. Вспомогательным называется алгоритм решения некоторой подзадачи из основной решаемой задачи. В таком случае алгоритм решения исходной задачи называется основным алгоритмом.
В качестве примера рассмотрим следующую задачу: требуется составить алгоритм вычисления степенной функции с целым показателем $$у = х^к$$, где к — целое число, х<>0. В алгебре такая функция определена следующим образом:
$$x^n = \begin{cases} 1 & n = 0 \\ \frac{1}{x^{-n}} & n < 0 \\ x^n & n > 0 \end{cases} $$
Для данной задачи в качестве подзадачи можно рассматривать возведение числа в целую положительную степень.
Учитывая, что $$\frac{1}{х^{-n}} = (\frac{1}{х})^{-n}$$, запишем основной алгоритм решения этой задачи.
fun main(){
println("Введите x, n: ")
var x = readLine()!!.toFloat()
var n = readLine()!!.toInt()
var y: Float
if(n==0) y = 1F
else {
if(n>0) y = stepen(x, n)
else y = stepen(1/x, -n)
}
println("y = $y")
}
Здесь дважды присутствует команда обращения к вспомогательному алгоритму с именем stepen. Это алгоритм возведения вещественного основания в целую положительную степень путем его многократного перемножения. Величины, стоящие в скобках в команде обращения к вспомогательному алгоритму, называются фактическими параметрами.
В котлине вспомогательные алгоритмы оформляются в виде функций. Запишем функцию stepen.
fun stepen(x: Float, n: Int): Float {
var res = 1F
var i = 1
while(i<=n){
res = res * x
i++
}
return res
}
Заголовок вспомогательного алгоритма начинается с ключевого слова fun, после которого следует имя функции, в скобках — список формальных параметров и после скобок тип результата (не обязателен). В списке параметров перечисляются переменные-аргументы с указанием их типов. Здесь x и n — формальные параметры-аргументы. Следовательно, процедура stepen производит вычисления по формуле ак. В основном алгоритме «Степенная функция» обращение к процедуре производится путем указания ее имени с последующим в скобках списком фактических параметров. Между формальными и фактическими параметрами процедуры должны выполняться следующие правила соответствия:
- по количеству (сколько формальных, столько и фактических параметров)
- по последовательности (первому формальному соответствует первый фактический параметр, второму — второй и т.д.)
- по типам (типы соответствующих формальных и фактических параметров должны совпадать)
Фактические параметры-аргументы могут быть выражениями соответствующего типа.
Обращение к процедуре инициирует следующие действия:
- Значения параметров-аргументов присваиваются соответствующим формальным параметрам.
- Выполняется тело процедуры (команды внутри процедуры).
- Значение результата возвращается командой return, и происходит переход к выполнению следующей команды основного алгоритма.
В функции stepen нет команд ввода исходных данных и вывода результатов. Здесь присваивание начальных значений аргументам (x, n) производится через передачу параметров-аргументов. А получение результата происходит командой return. Таким образом, передача значений параметров процедур — это третий способ присваивания (наряду с командой присваивания и командой ввода).
Использование процедур позволяет строить сложные алгоритмы методом последовательной детализации.
Программы для графического отображения алгоритмов
https://draw.io (онлайн)
Microsoft Visio
Dia (бесплатная)
КОНТРОЛЬНЫЕ ВОПРОСЫ
- Линейный алгоритм
- Разветвляющийся алгоритм
- Циклический алгоритм
- Вспомогательные алгоритмы и процедуры
| Предыдущая лекция | Следующая лекция | |
|---|---|---|
| Основные понятия алгоритмизации | Содержание | Логические основы алгоритмизации |