Ветвления и циклы в вычислительных алгоритмах
Составим алгоритм решения квадратного уравнения
ах2 + bх + с = 0.
Задача хорошо знакома из математики. Исходными данными здесь являются коэффициенты a, b, с. Решением в общем случае будут два корня x1 и х2 которые вычисляются по формуле:
Все используемые в этой программе величины вещественного типа.
алг корни квадратного уравнения
вещ а,b,с,xl,x2,d
нач ввод а,b,с
d:=b2- 4ac
xl: = (-b+sqr(d) / (2а)
x2: = (-b-sqr(d)) /(2а)
вывод xl,x2
кон
Слабость такого алгоритма видна невооруженным глазом. Он не обладает важнейшим свойством, предъявляемым к качественным алгоритмам, — универсальностью по отношению к исходным данным. Какими бы ни были значения исходных данных, алгоритм должен приводить к определенному результату и завершать работу. Результатом может быть число, но может быть и сообщение о том, что при определенных данных задача решения не имеет. Недопустимы остановки в середине алгоритма из-за невозможности выполнить какую-то операцию. Упомянутое свойство в литературе по программированию называют результативностью алгоритма (в любом случае должен быть получен какой-то результат).
Чтобы построить универсальный алгоритм, сначала требуется тщательно проанализировать математическое содержание задачи.
Решение уравнения зависит от значений коэффициентов я, Ь, с. Вот анализ рассмотренной выше задачи (ограничиваемся только поиском вещественных корней):
если а = 0, b = 0, с = 0, то любое х — решение уравнения;
|
|
|
если (7 = 0, b = Q, с ^ 0, то уравнение действительных решений не имеет;
если а = 0, Ъ ф 0, то это линейное уравнение, которое имеет одно решение х = -с/Ь;
если аф0ис1=Ь2- Аас > 0, то уравнение имеет два вещественных корня (формулы приведены выше);
если а*0и d<0, то уравнение не имеет вещественных корней.
Блок-схема алгоритма приведена на рис. 3.
Этот же алгоритм на алгоритмическом языке:
В этом алгоритме многократно использована структурная команда ветвления. Общий вид команды ветвления в блок-схемах и на алгоритмическом языке следующий:
|
Вначале проверяется условие (вычисляется отношение, логическое выражение). Если условие истинно, то выполняется серия 1 — последовательность команд, на которую указывает стрелка с надписью «да» (положительная ветвь). В противном случае выполняется серия 2 (отрицательная ветвь). В АЯ условие записывается после служебного слова если, положительная ветвь — после слова то, отрицательная — после слова иначе. Буквы кв обозначают конец ветвления.
Если на ветвях одного ветвления содержатся другие ветвления, то такой алгоритм имеет структуру вложенных ветвлений. Именно такую структуру имеет алгоритм «Корни квадратного уравнения».
|
|
|
В общем виде структурная команда цикл с постусловием или цикл — до представляется так:
Здесь используется условие окончания цикла. Когда оно становится истинным, цикл заканчивает работу.
Составим алгоритм решения следующей задачи: даны два натуральных числа М и N. Требуется вычислить их наибольший общий делитель — НОД (М, N).
Эта задача решается с помощью метода, известного под названием алгоритма Евклида. Его идея основана на том свойстве, что если М >N, то НОД (M,N) - НОД (M— N,N)- Попробуйте самостоятельно доказать это свойство. Другой факт, лежащий в основе алгоритма, тривиален — НОД (M, М) = М. Для «ручного» выполнения этот алгоритм можно описать в форме следующей инструкции:
1. Если числа равны, то взять их общее значение в качестве ответа; в противном случае продолжить выполнение алгоритма.
2. Определить большее из чисел.
3. Заменить большее число разностью большего и меньшего значений.
4. Вернуться к выполнению пункта 1.
5. Блок-схема и алгоритм на АЯ будут следующими:
Алгоритм имеет структуру цикла с вложенным ветвлением. Проделайте самостоятельно трассировку этого алгоритма для случая М = 18, N = 12. В результате получится НОД = 6, что, очевидно, верно.
|
|
|
Дата добавления: 2015-12-17; просмотров: 20; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!