|
|
Пример исполнения алгоритма KVKOR12 Реализация разветвляющихся алгоритмов Разветвляющимся алгоритмом называется такой алгоритм, при исполнении которого от начала алгоритма до конца можно пройти разными путями (выполняя различные действия, некоторые из действий пропускаются) в зависимости от исходных данных. Определяющим разветвляющийся алгоритм являются наличие либо структуры ветвления, либо структуры выбора. Структура ветвления Начнем изучение со структуры ветвления. Обе формы структуры – полная и короткая приведены на рис. 12.1.
a) полная структура ветвления b) короткая структура ветвления Рис. 12.1. –Структура ветвления IV.2.5. Условный оператор Назначение Для реализации структуры ветвления используется условный оператор (полный и короткий). Синтаксис Синтаксис определяется синтаксической диаграммой, приведенной на рис. 12.2.
Рис. 12.2. –Условный оператор Существует две формы условного оператора: - полный условный оператор с ветвью else; - короткий условный без ветви else.
Семантика 1) вычисляется логическое выражение между IF и THEN (возможен ответ true или false); 2) Если результат true, то выполняется оператор1, оператор2 не выполняется. Семантическая неоднозначность Синтаксис позволяет в качестве операторов, вложенных в условный оператор, использовать любые операторы языка, в том числе и условные. Исходя из этого, возникает неоднозначность в использовании следующей конструкции: if <условие1> then if <условие2> then <операторA> else <операторB> Эту конструкции можно трактовать двояко. Первый вариант (рис.12.3):
Рис. 12.3. –Семантическая неоднозначность (первый вариант трактовки) внутрь полного условного оператора if <условие1> then <оператор1> else <операторB> в качестве оператора1 по ветви then вложен короткий условный оператор if <условие2> then <операторA> Второй вариант (рис. 12.4): внутрь короткого условного оператора if <условие1> then <оператор> в качестве оператора вложен полный условный оператор if <условие2> then <операторA> else <операторB>
Рис. 12.4. –Семантическая неоднозначность (второй вариант трактовки) Естественно, разные варианты трактовки, дают разный семантический смысл (получаются различные результаты). Для устранения такой неоднозначности принято следующее синтаксическое правило: Ветвь else относится к ближайшему слева if , т.е. в нашем примере справедлив второй вариант - внутрь короткого условного оператора в качестве оператора вложен полный условный оператор Для поддержки первого варианта вложенный по ветви оператор, расположенный по ветви then, необходимо заключить в операторные скобки begin end, т.е. сделать из него составной оператор: if <условие1> then begin if<условие2> then <операторA> end else <операторB> Рассмотрим примеры реализации разветвляющихся алгоритмов со структурой ветвления. Задача вычисление квадратного корня из вещественного числа Математическая модель
Метод решения Решается эта задача по следующим правилам: при x>=0 извлекается квадратный корень при x<0 решения нет. На языке математики этот метод можно записать следующим образом
Информационная модель: Таблица 12.1.Информационная модель
Набор тестов Таблица 12.2.Набор тестов
Алгоритмическая модель Алгоритмическая модель приведена на рис. 12.5. Алгоритм обрабатывает вещественные данные (переменные X и Y вещественного типа). Вначале необходимо получить исходное значение. Затем осуществить расчет по формулам, не забывая о выводе результирующей информации. Если в качестве определяющего процесс решения условия возьмем логическое выражение Х>=0, то при выполнении этого условия должны вычислить корень квадратный из Х и вывести полученный результат, а при невыполнении этого условия вывести информацию о том, что решения нет. Таким образом, эти действия можно выполнить с помощью условного оператора, в котором - в качестве условия используется логического выражения Х>=0; - оператора по ветви then - составной оператор, состоящий из оператора присваивания Y:=SQRT(X) и оператора обращения к процедуре WRITELN, обеспечивающей вывод значения результата Y; - оператора по ветви else - оператор обращения к процедуре WRITELN, обеспечивающей вывод сообщения об отсутствии решения.
Рис. 12.5. –Схема алгоритма вычисления квадратного корня
Программная модель PROGRAM KVKOR; { Назначение: вычисление квадратного корня из заданного вещественного числа } VAR X {исходное число}, Y {результат} : REAL; BEGIN {ввод исходной информации} WRITELN('Введите число'); READLN(X); {вычисление и вывод результата} IF X>=0 THEN BEGIN Y:=SQRT(X); WRITELN('Корень квадратный из ',X,'=',Y) END ELSE WRITELN('Корень из отрицательного ',X,' НЕ СУЩЕСТВУЕТ') END. Пример исполнения алгоритма KVKOR 0) До выполнения программы осуществляется распределение свободного участка памяти под переменные величины, описанные в разделе переменных программы:
Рис. 12.6. –Распределение ОП 1) выполняется обращение к процедуре вывода: WRITELN('Введите число') Вычисляется фактический параметр-выражение. Получается строка символов. Она выводится на экран. На экране, начиная с текущего положения курсора, появляется сообщение: Введите число , и курсор переводится в начало следующей строки экрана дисплея; 2) выполняется обращение к процедуре ввода: READLN (Х) Программа ожидает получения информации в виде одного вещественного числа с клавиатуры ПЭВМ. Человек набирает эту информацию, например, -4 и нажимает клавишу ввод (Return или Enter). Значение –4 поступает в память под именем Х. (рис. 12.7).
Рис. 12.7. –Содержимое ОП после ввода 3) начинает выполняться условный оператор: IF X>=0 THEN BEGIN Y:=SQRT(X); WRITELN('Корень квадратный из ',X,'=',Y) END ELSE WRITELN('Корень из отрицательного ',X,' НЕ СУЩЕСТВУЕТ') Первым действием вычисляется логическое выражение, стоящее между IF и THEN и являющееся условием X>=0:
4) так как получен ответ FALSE, то оператор по ветви THEN пропускается, и выполняется оператор стоящий по ветви ELSE – обращение к процедуре вывода WRITELN('Корень из отрицательного ',X,' НЕ СУЩЕСТВУЕТ') В результате исполнения на экране, начиная с текущего положения курсора, появляется сообщение: Корень из отрицательного -4.0000000000E+00 НЕ СУЩЕСТВУЕТ Решение квадратного уравнения Классическим примером разветвляющегося алгоритма является решение квадратного уравнения с произвольными коэффициентами a, b и c. Математическая модель
Метод решения С точки зрения метода решения такое уравнение рассматривается, как квадратное, если первый коэффициент a отличен от нуля. В этом случае вычисляется дискриминант Если же первый коэффициент задан равным 0, то квадратное уравнение вырождается в линейное со всеми возможными вариантами решений. При b отличном от 0 имеется единственное решение X=-c/b. При b=0 линейное уравнение вырождается в тождество, которое справедливо только в одном случае, если задано значение с=0. Таким образом, в случае с=0 решением уравнения считается любое существующее вещественное значение, а, если с отлично от 0, то тождество не выполняется, и, значит, решений исходное уравнение не имеет. Информационная модель В нашем алгоритме, если учесть, что комплексное число можно представить как пару вещественных чисел, используются только вещественные величины - A, B, С, D, X1, X2, REX, IMX, X. Таблица 12.3.Информационная модель
Набор тестов Таблица 12.4.Набор тестов
Алгоритмическая модель Последовательность разработки алгоритма проиллюстрирована ниже фрагментами текста программы. Однако приведем и схему алгоритма (рис. 12.8).
Рис. 12.8. –Схема алгоритма решения квадратного уравнения Программная модель Вспомним, что программа на Паскале состоит из разделов. Первый раздел - заголовок текста программы. Назовем ее KVUR : PROGRAM KVUR; Второй радел программы - описание используемых модулей. Модулями пока не пользуемся, поэтому второй раздел отсутствует. Третий раздел программы - описание используемых меток. Мы знаем, что хорошие (структурированные) программы не должны содержать меток. А мы пишем только хорошие программы – поэтому третий раздел отсутствует. Четвертый раздел текста программы - описание поименованных констант. Если мы посмотрим на метод решения, то увидим только простейшие константы, давать им имена не имеет смысла. Поэтому четвертого раздела программы не будет. Пятый раздел программы - описание нестандартных типов данных. В информационной модели у нас используется только вещественный тип данных REAL. Он стандартный. Поэтому раздел пять в программе отсутствует. Шестой - обязательный раздел каждой программы – описание переменных величин. В информационной модели указаны девять вещественных переменных. Опишем их: VAR A, B, С, D, X1, X2, REX, IMX, X:REAL; Не забываем, что по этому разделу распределяется оперативная память. В свободной части ОП выделяются участки соответствующего размера под каждую переменную. Эти участки получают имена переменных:
Рис. 12.9. –Распределение ОП Седьмой раздел программы - описание (тексты) собственных процедур и функций. С такими типами текстов мы не знакомы, поэтому этот раздел в нашей программе отсутствует. Восьмой - обязательный раздел - раздел операторов. Все операторы текста программы располагаются между операторными скобками BEGIN и END с точкой. Последовательность разработки раздела операторов программ обычно следующая: вначале между операторными скобками в виде комментариев пишутся пункты плана алгоритма. Затем по каждому пункту плана вставляются операторы, которые реализуют этот пункт. Для нашей задачи это выглядит следующим образом. Составим план: BEGIN {Ввод исходной информации} {Расчет по математической модели с выводом результатов} END. Перейдем к реализации каждого пункта плана. При реализации ввода исходных данных мы должны ориентироваться не на себя, а на пользователя нашей программы. Поэтому наша программа должна указывать пользователю - какую информацию он должен вводить. Сообщение об этой информации выдается с помощью обращения к стандартной процедуре вывода с фактическим параметром - строкой символов: WRITELN('Введите коэффициенты кв. уравнения A, B и С') Непосредственный ввод информации осуществляется с помощью обращения к стандартной процедуре ввода READLN с фактическими параметрами - именами вводимых переменных: READLN (A, B, С) Второй пункт плана реализует выбранный метод решения, поставленной задачи в виде математической модели. В зависимости от значения первого коэффициента A (A равно 0 или нет), мы должны либо решать чисто квадратное уравнение, либо исследовать линейное уравнение. Эти действия записываются условным оператором, в котором в качестве - условия используется логическое выражение A<>0; - оператора по ветви then - действия обеспечивающие решения чисто квадратного уравнения; - оператора по ветви else - действия обеспечивающие исследование линейного уравнения: IF A<>0 THEN {решение чисто квадратного уравнения} ELSE {исследование линейного уравнения} Рассмотрим процесс решения чисто квадратного уравнения. Здесь необходимо вычислить дискриминант (оператор присваивания D:=SQR(B)-4*A*С ). А затем проанализировать его (выяснить положительный он или нет), и, в зависимости от результата анализа, вычислить и вывести либо два вещественных корня, либо вычислить и вывести действительную и мнимую части двух комплексных корней. Эта последовательность действий реализуется с помощью условного оператора, в котором в качестве - - условия используется логическое выражение D>=0; - - оператора по ветви then - составной оператор, обеспечивающий вычисление двух вещественных корней (два оператора присваивания X1:=(-B+SQRT(D))/(2*A); X2:=(-B-SQRT(D))/(2*A)) и вывод полученных результатов (оператор обращения к процедуре вывода WRITELN('Два вещественных корня X1=', X1, ' X2=',X2) ); - - оператора по ветви else - составной оператор, обеспечивающий вычисление вещественной и мнимой частей двух комплексных корней (два оператора присваивания REX:=-B/(2*A); IMX:=SQRT(-D) /(2*A) ) и вывод полученных результатов (оператор обращения к процедуре вывода WRITELN('Два комплексных корня X1=', REX, ' +i',IMX,' X2=', REX, ' -i',IMX) ). Все действия процесса решения чисто квадратного уравнения записываются в виде составного оператора BEGIN D:=SQR(B)-4*A*С; IF D>=0 THEN BEGIN X1:=(-B+SQRT(D))/(2*A); X2:=(-B-SQRT(D))/(2*A)); WRITELN('Два вещественных корня X1=', X1, ' X2=',X2) END ELSE BEGIN REX:=-B/(2*A); IMX:=SQRT(-D)/(2*A); WRITELN('Два комплексных корня X1=', REX, ' +i', IMX, ' X2=', REX, ' -i', IMX ) END END Теперь запишем процесс исследования линейного уравнения. В зависимости от значения коэффициента B (неравен или равен он нулю), необходимо либо вычислять единственный корень и выводить его значение, либо проводить дальнейший анализ на тождество. Таким образом, эта часть программы представляется так IF B<>0 THEN BEGIN X:=-С/B; WRITELN('Один корень Х=',X) END ELSE {анализ на тождество} Анализ на тождество реализуется также с помощью условного оператора: IF С=0 THEN WRITELN ('Х - любое') ELSE WRITELN ('Решений нет') Теперь весь алгоритм в целом: PROGRAM KVUR; {Назначение: решение квадратного уравнения с произвольными вещественными коэффициентами } VAR A , B, C,{коэффициенты квадратного уравнения} D {дискриминант квадратного уравнения}, X1, X2,{два вещественных корня} REX, IMX,{действительная и мнимая части комплексных корней} X {один вещественный корень линейного уравнения} : REAL; BEGIN
{Ввод исходной информации} WRITELN('Введите коэффициенты кв.уравнения A, B и С'); READLN (A, B, C);
{Расчет по математической модели с выводом результатов} IF A<>0 THEN {решение чисто квадратного уравнения} BEGIN D:=SQR(B)-4*A*C; IF D>=0 THEN BEGIN X1:=(-B+SQRT(D))/(2*A); X2:=(-B-SQRT(D))/(2*A); WRITELN('Два вещественных корня X1=', X1, ' X2=',X2) END ELSE BEGIN REX:=-B/(2*A); IMX:=SQRT(-D)/(2*A); WRITELN('Два комплексных корня X1=', REX, ' +i', IMX, ' X2=', REX, ' -i', IMX ) END END ELSE {исследование линейного уравнения} IF B<>0 THEN BEGIN X:=-C/B; WRITELN('Один корень Х=',X) END ELSE {анализ на тождество} IF С=0 THEN WRITELN ('Х - любое') ELSE WRITELN ('Решений нет')
END. 
12 Не нашли, что искали? Воспользуйтесь поиском по сайту: ©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.
|
.
. И, если D>=0, то существуют два корня X1 и Х2, определяемые по формуле 
, причем они получаются равные, в случае равенства D=0. Если D<0, то решение в области вещественных чисел отсутствует, а существуют только решения в области комплексных чисел, причем действительная часть обоих корней одинаковая 
, а мнимая отличается только знаком 
.
3
