![]() |
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Реализация циклических алгоритмовСтр 1 из 5Следующая ⇒
Реализация циклических алгоритмов Алгоритм называется циклическим, если при его исполнении некоторые действия неоднократно повторяются, не смотря на то, что записаны они один раз. С точки зрения структурного программирования признаком циклического алгоритма является присутствие одной из структур: - цикл с предусловием (цикл пока); - цикл с постусловием (цикл до); - цикл с параметром. В Паскале каждой из этих трех алгоритмических структур соответствует свой оператор цикла. Алгоритмическая структура цикл с предусловием Словесно структура цикл с предусловием описывается следующим образом: пока справедливо условие выполнения цикла повторять серию команд (тело цикла). На схемах алгоритма структура цикла с предусловием изображается в соответствие с рис. 15.1. Рис. 15.1. – Алгоритмическая структура цикла пока На языке математики эта структура записывается так: пока < условие>: < серия команд – тело цикла> IV.2.8. Оператор цикла пока Назначение Оператор цикла с предусловием предназначен для реализации одноименной алгоритмической структуры. Название этого оператора определяется тем, что условие расположено в начале структуры. Синтаксис Синтаксис оператора цикла пока определяется синтаксической диаграммой изображенной на рис. 15.2. Рис. 15.2. – Оператор цикла пока С точки зрения синтаксиса тело оператора цикла пока может состоять только из одного оператора (естественно, любого, в том числе и составного). Семантика При выполнении оператора: 1) вычисляется логическое выражение, являющееся условием выполнения цикла; 2) если результат FALSE, то выполнение оператора цикла прекращается (выполняется следующий оператор, стоящий за оператором цикла пока); 3) если результат TRUE, то выполняется тело цикла (оператор, стоящий за символом DO); 4) осуществляется переход к пункту 1. Алгоритмическая структура цикл с постусловием Словесно структура цикл с постусловием описывается следующим образом: повторять выполнение действий до выполнения условия окончания цикла. На схемах алгоритма структура цикла с постусловием изображается в соответствие с рис. 15.3. Рис. 15.3. – Алгоритмическая структура цикл до На языке математики эта структура записывается так: повторять < серия команд – тело цикла> до < условие>
IV.2.9. Оператор цикла до
Назначение Оператор цикла с постусловием предназначен для реализации структуры цикл с постусловием (цикл-до или цикл повторять). Название этого оператора определяется тем, что условие расположено в конце структуры. Синтаксис Синтаксис оператора цикла до определяется синтаксической диаграммой на рис. 15.4. Рис. 15.4. – Оператор цикла до Семантика При исполнении оператора: 1) выполняется тело цикла (операторы, расположенные между REPEAT и UNTIL); 2) вычисляется логическое выражение, являющееся условием окончания цикла; 3) если результат FALSE, то осуществляется переход к пункту 1; 4) если результат TRUE, то оператор цикла прекращается (выполняется следующий оператор, стоящий за оператором цикла до).
Математическая модель Этот алгоритм определяется в случае, если математическая модель сведена к вычислению значений функции y=f(x) для всех значений аргумента x, лежащих в диапазоне от начального значения xn до конечного значения xk, причем дискрет изменения аргумента (шаг) задан значением hx: x: =xn(hx)xk: y: =f(x)
Графическая интерпретация этой задачи показана на рис. 15.5.
Рис. 15.5. – Графическая интерпретация таблицы значений функции y=f(x) Метод решения Для решения поставленной задачи необходимо выполнить следующее: 1) аргументу присвоить начальное значение диапазона x: =xn; 2) использовать одну из циклических структур – цикл пока или повторять до, так как необходимо выполнять одинаковые действия (вычислять значение функции в выбранной точке, выводить полученное значение и переходить к новому значению аргумента). В условии (повторения или окончания цикла) сравнивается значение аргумента с конечным значением диапазона изменения. Для цикла пока используется условие повторения цикла x< =xk, а для цикла до используется условие окончания цикла x> xk; 3) в теле цикла - вычислить значение функции y: =f(x); - вывести значение аргумента и функции writeln(x, y); - - перейти к новому значению аргумента - изменить значение аргумента на шаг x: =x+hx. Постановка задачи В качестве примера рассмотрим вычисление таблицы синусов в заданном интервале с заданным шагом изменения аргумента. Математическая модель x: = xn(hx)xk: y=sin(x). Метод решения этой задачи приведен выше. Напишем две программы - с использованием разных операторов цикла: Метод решения с циклом пока 1) x: =xn; 2) пока x< =xk: Алгоритмическая модель Схемы алгоритмов решения задачи вычисления таблицы синусов обоими методами приведены на рис. 15.6. Рис. 15.6. – Схемы алгоритма вычисления таблицы синусов Математическая модель Математическая модель таблицы значений функции от нескольких переменных (или аргументов) формулируется следующим образом " x1: =x1n(hx1)x1k: " x2: =x2n(hx2)x2k: " x3: =x3n(hx3)x3k: …………………… " xn: =xnn(hxn)xnk: y: =f(x1, x2, x3, …xn) Метод решения Таблица должна содержать значения функции для всевозможных комбинаций значений аргументов. Т.е. необходимо перебрать все значения первого аргумента, для каждого значения первого аргумента перебрать все значения второго аргумента; для каждого значения второго аргумента перебрать все значения третьего и т.д.; для каждого значения последнего аргумента вычислить значение функции, вывести полученное значение и значения всех аргументов, при которых рассчитывалось полученное значение функции, и перейти к новому значению последнего аргумента. Алгоритм с использованием оператора цикла пока будет иметь следующую структуру:
x1: =x1n; while x1 < = x1k do begin x2: =x2n; while x2 < = x2k do begin x3: =x3n; while x3 < = x3k do begin ...
xn: =xnn; while xn < = xnk do begin y: =f(x1, x2,..., xn); writeln(x1, x2,..., xn, y); xn: =xn+hxn end; {xn}
...
x3: =x3+hx3 end; {x3}
x2: =x2+hx2 end; {x2}
x1: =x1+hx1 end; {x1} Этот же алгоритм с использованием оператора цикла до будет иметь следующую структуру:
x1: =x1n; repeat
x2: =x2n; repeat
x3: =x3n; repeat ...
xn: =xnn; repeat y: =f(x1, x2,..., xn); writeln(x1, x2,..., xn, y); xn: =xn+hxn until xn> xnk;
... x3: =x3+hx3 until x3> x3k;
x2: =x2+hx2 until x2> x2k;
x1: =x1+hx1 until x1> x1k Естественно, что в таком алгоритме можно использовать разные виды операторов цикла, главное - должно выдерживаться следующее правило: - цикл, который начинается раньше, позже заканчивается; - цикл, который начинается позже, раньше заканчивается. Это основное правило вложенности циклов. Назначение Оператор используется в алгоритмах, когда для каждого значения переменной из диапазона значений необходимо выполнять одинаковые действия. Эта переменная называется параметром цикла. Синтаксис
Синтаксическое ограничение: результаты вычислений выражений 1 и 2 и параметр цикла должны быть одного простого порядкового типа. Семантика Условием выполнения оператора цикла с параметром является существование списка значений - для возрастающего списка значений с символом TO значение выражения 1 должно быть меньше или равно значения выражения 2; для убывающего списка значений с символом DOWNTO значение выражения 1 должно быть больше или равно значения выражения 2. Порядок выполнения оператора: 1) вычисляются значения выражений 1 и 2, определяющих список значений параметра цикла; 2) вычисляется условие выполнения оператора цикла с параметром – для списка с символом TO результат выражения 1 меньше или равен результата выражения 2, для списка с символом DOWNTO результат выражения 1 больше или равен результата выражения 2 (возможен результат TRUE или FALSE); 3) если условие имеет значение FALSE, то выполнение оператора цикла прекращается (выполняется следующий оператор, расположенный за оператором цикла); 4) формируется полный список значений параметра цикла. Для списка с символом TO - это все значения подряд от результата выражения1 по результат выражения2. Для списка с символом DOWNTO – это все значения в обратном порядке от результата выражения1 по результат выражения2; 5) параметру цикла присваивается очередное значение из списка значений (первый раз - значение выражения1); 6) если список значений исчерпан (до этого уже было выбрано значение выражения2), то выполнение оператора цикла прекращается. Значение параметра цикла становится неопределенным и выполняется следующий оператор, стоящий за оператором цикла; 7) для выбранного значения параметра цикла выполняется оператор, расположенный после символа DO (тело цикла); 8) осуществляется переход к пункту 5.
Рис. 15.10. – Изображение оператора цикла с параметром на схемах алгоритма Предупреждения: 1) по завершению оператора цикла (см. пункты 3 и 6) значение параметра цикла неопределенное (зависит от реализации языка) и выполняется следующий оператор, расположенный за оператором цикла с параметром; 2) значения выражений 1 и 2 вычисляются один раз (см. пункт 1), поэтому в теле цикла не имеет смысла изменять значения, определяющие эти выражения; 3) в теле цикла запрещается изменять значение параметра цикла, так как это приводит к непредсказуемым последствиям (значение параметра цикла изменяется автоматически в пункте 5) Задача Для заданного года G определить количество дней в каждом месяце. Математическая модель Современный календарь действует с 1600 года нашей эры. " i=(janvar, fevral, mart, aprel, maj, iun, iul, avgust, sentjabr, oktjabr, nojabr, dekabr) необходимо вычислять d - количество дней в i-oм месяце заданного года G. Метод решения Вне зависимости от года G (год должен быть > =1600 ) " i: =janvar..dekabr: выбор по i из вариантов Год G считается високосным, если он кратен 4 и не кратен 100 или кратен 400 (каждый четвертый год - високосный, за исключением каждого сотого года; каждый четырехсотый год также високосный). Условие високосности: G mod 4 = 0 & G mod 100 < > 0 V G mod 400 = 0 Информационная модель Таблица 15.2. Информационная модель
Примечания: 1)выходные данные - текст с указанием названия месяца и количества дней; 2) type mes=(janvar, fevral, mart, aprel, maj, iun, iul, avgust, sentjabr, oktjabr, nojabr, dekabr) Алгоритмическая модель Схема алгоритма решения задачи приведена на рис. 15.11. Математическая модель i=1(1)10: j=1(1)10: y=i*j
Метод решения Задача сводится к вычислению таблицы значений функции от двух аргументов. Причем в данной задаче значения аргументов принадлежат диапазону значений от 1 по 10, то есть для перебора аргументов можно использовать циклы с параметром: " i=1..10: " j=1..10: y=i*j Информационная модель Входные данные - отсутствуют; выходные данные - последовательно все значения y; промежуточные переменные - значения аргументов вычисляемой функции i, j, Алгоритмическая модель Схема алгоритма вычисления таблицы умножения приведена на рис. 15.12. Программная модель program tabumn; var i, j, y: integer; begin for i: =1 to 10 do begin {вычисление одного столбца - при фиксированном значении i} for j: = 1 to 10 do Рис. 15.12. – Схема алгоритма вычисления таблицы умножения
begin y: =i*j; writeln (i, '*', j, '=', y) end; {for j} {" остановка" при просмотре результатов - до тех пор, writeln(' Для продолжения нажмите Enter') readln end {for i} end. Два других варианта решения этой задачи (с циклами пока и повторять до): Вариант с циклом пока Метод решения i: =1 пока i Алгоритмическая модель Рис. 15.13. – Схема алгоритма с циклом с предусловием Программная модель program tabumn; var i, j, y: integer; begin i: =1; while i< = 10 do begin {вычисление одного столбца - при фиксированном значении i} j: = 1; while j< =10 do begin y: =i*j; writeln (i, '*', j, '=', y); j: =j+1 end; {while j} {" остановка" при просмотре результатов - до тех пор, writeln(' Для продолжения нажмите Enter') readln; i: =i+1 end {while i} end.
Вариант с циклом повторять Метод решения i: =1 повторять до i> 10 Программная модель program tabumn; var i, j, y: integer; begin i: =1; repeat {вычисление одного столбца - при фиксированном значении i} j: = 1; repeat y: =i*j; writeln (i, '*', j, '=', y); j: =j+1 until j> 10; Алгоритмическая модель Рис. 15.14. – Схема алгоритма с циклом с постусловием {" остановка" при просмотре результатов - до тех пор, writeln(' Для продолжения нажмите Enter') readln; i: =i+1 until i> 10 end.
Алгоритм накопления суммы Такой алгоритм часто встречается в нашей повседневной жизни, например, подсчет продавцом стоимости товаров. Технология подсчета сумму стоимости заключается в том, что в начале устройство, с помощью которого ведется подсчет стоимости должно находиться в исходном состоянии (если подсчет ведется с помощью счет, то они должны быть " сброшены"; если с помощью калькулятора, то он должен быть " обнулен" - на индикаторе должен быть 0). В вычислительной технике устройство, в котором накапливается сумма, называется сумматором. Поэтому в алгоритме должна быть переменная - сумматор, которая в начале алгоритма должна быть обнулена. Затем последовательно к сумматору добавляются значения суммируемых величин - происходит процесс суммирования или накопления суммы. После выполнения этих действий в сумматоре находится общая сумма. Математическая модель Метод решения 1) s=0 2) i=1(1)n: s=s+i Реализация п.2 может быть выполнена тремя способами (наиболее эффективный – цикл с параметром) 1 способ 2) " i=1..n: s=s+i 2 способ 2.1) i: =1 2.2) пока i< =n: 3 способ 2.1) i: =1 2.2) повторять до i> n Информационная модель Входные данные - количество натуральных чисел n, которые должны быть просуммированы; Выходные данные - накопленная сумма s (целое число); Промежуточные данные - i - текущее натуральное число из интервала от 1 по n. Программная модель (1-ый способ) program sumnat; var n, s, i: word; begin {ввод исходных данных} writeln('Введите количество натуральных чисел'); readln(n);
{реализация метода решения} s: =0; for i: =1 to n do s: =s+i;
{вывод результата} writeln('сумма первых ', n, ' натуральных чисел=', s) end. Примечание: обратите внимание, что вывод результата находится после окончания цикла по накоплению суммы (сравните с методом вычисления таблицы значений функции). Математическая модель y=n! или y=1*2*3*...*n или y= Метод решения 1) у=1 2) " i=1..n: y=y*i Информационная модель Входные данные - количество натуральных чисел n, которые должны быть перемножены; выходные данные - накопленное произведение у (т.к. факториал быстро растущая функция, то целесообразно выбрать тип longint); промежуточные данные - i - текущее натуральное число из интервала от 1 по n. Программная модель
program faktorial; var n, i: word; y: longint; begin {ввод исходных данных} writeln('Введите количество натуральных чисел'); readln(n);
{реализация метода решения} y: =1; for i: =1 to n do y: =y*i;
{вывод результата} writeln('произведение первых ', n, ' натуральных чисел=', y) end. Постановка задачи Вычислить таблицу значений синусов, в которой математическая функция синус от аргумента х вычисляется, как сумма последовательности чисел Накопление суммы прекращается, когда очередной элемент меньше заданной точности (обычно 10-5 – 10-10). Метод решения План решения следующий: 1) ввод исходных данных с контролем правильности ввода; 2) очистка экрана и вывод шапки 3) вычисление таблицы Ввод исходных данных с контролем правильности ввода осуществляем следующим образом: 1.1) помечаем меткой начало ввода; 1.2) сообщаем пользователю о данных, которые он должен ввести; 1.3) отключаем систему прерываний по ошибкам ввода-вывода и выхода за диапазон значений; 1.4) выполняем ввод начального значения, конечного и шага изменения аргумента функции; 1.5) включаем систему прерываний по ошибкам ввода-вывода и выхода за диапазон значений; 1.6) анализируем наличие ошибки с помощью системной функции IOResult или несоответствие начала и конца диапазона изменения аргумента функции. Если ошибка существует то а) сообщаем об этом пользователю; б) возвращаемся к метке, которая отмечает начало ввода. Очистку экрана и вывод шапки выполняем следующим образом 2.1) очищаем экран с помощью процедуры ClrScr; 2.2) выводим текст шапки таблицы; 2.3) устанавливаем начальное значение 1 счетчика заполненных строк экрана. При вычислении таблицы определяющим является алгоритм вычисления таблицы значений функции от одной переменной. Внутри цикла для вычисления одного значения функции используется алгоритм накопления суммы. 3.1) x: =xn 3.2) пока x< =xk: В этой задаче для вычисления значения функции используем алгоритм накопления суммы. Пусть y – сумматор (для накопления значения функции), a – очередное элемент суммы, i – номер элемента суммы, . ai – i-ый элемент суммы, eps – точность. В этом случае для накопления суммы a.1) сумматор обнуляется y: =0 a.2) очередной элемент ряда - первый a: =a1 a.3) фиксируется номер первого элемента i: =1 a.4) пока очередной элемент a по абсолютной величине не соответствует точности (превышает заданную точность eps) повторяется добавление к сумматору очередного элемента, вычисляется значение нового элемента, номер элемента увеличивается на 1. пока |a|> eps: Для вычисления ai применяем следующий подход – последовательность чисел, которая суммируется представляется как геометрическая последовательность (вычисляется значение первого элемента ряда a1 и выводится формула знаменателя геометрической прогрессии q). Для нашей задачи a1=x Таким образом, зная a1(a: = a1), любой следующий элемент вычисляется по формуле b.1) Вывод результата заключается в том, что выводятся значения аргумента x, результата расчета y, стандартной функции sin(x), погрешности - |y-sin(x)|, после этого увеличивается значение счетчика заполненных строк экрана (k) на 1, затем при необходимости производится очистка экрана. b.2) Очистка экрана производится если k=23 Þ Информационная модель Таблица 15.3. - Информационная модель
Программная модель program tabsin; uses crt; label inp; const eps=0.1e-9; {точность вычисления} var x, {очередное значение аргумента} y, {сумматор - для вычисления синуса} xn, {начальное значение аргумента таблицы} xk, {конечное значение аргумента таблицы} hx, {шаг изменения аргумента} a {очередной элемент суммы} : real; i, {номер элемента суммы} k {счетчик заполненных строк экрана} : integer; begin
{ввод исходных данных с контролем правильности ввода} inp: writeln('Начало, конец, шаг для аргумента'); {$I-} {$R-} readln(xn, xk, hx); {$I-} {$R-} if (IOresult< > 0)or(xn> xk) then begin writeln('Ошибка при вводе данных! '); goto inp end;
clrscr; {очистка экрана} {вывод шапки таблицы} writeln('x ': 5, 'вычисл sin': 14, 'контр sin': 14, 'погрешность': 14); k: =1; {счетчик заполненных строк экрана}
x: =xn; {первое значение аргумента функции} while x< =xk do begin
{вычисление sin - накопление суммы} y: =0; {обнуление счетчика} a: =x; {первый элемент суммы} i: =1; while abs(a)> eps do begin y: =y+a; {накопление суммы} a: =-a*sqr(x)/(2*i*(2*i+1)); {следующий элемент суммы} i: =i+1 {номер следующего элемента суммы} end;
{вывод очередной строки таблицы} {аргумент, вычисленное и контрольное значения, погрешность} writeln(x: 5: 2, y: 14: 9, sin(x): 14: 9, abs(y-sin(x)): 14: 9); k: =k+1; {увеличение счетчика заполненных строк экрана} if k=23 then {экран заполнен} begin writeln('Для продолжения нажмите Enter'); readln; {остановка до нажатия клавиши Enter} clrscr; {очистка экрана} {вывод шапки таблицы} writeln('x ': 5, 'вычисл sin': 14, 'контр sin': 14, 'погрешность': 14); k: =1; {установка счетчика заполненных строк экрана} end; x: =x+hx {переход к новому значению аргумента} end end.
Реализация циклических алгоритмов Алгоритм называется циклическим, если при его исполнении некоторые действия неоднократно повторяются, не смотря на то, что записаны они один раз. С точки зрения структурного программирования признаком циклического алгоритма является присутствие одной из структур: - цикл с предусловием (цикл пока); - цикл с постусловием (цикл до); - цикл с параметром. В Паскале каждой из этих трех алгоритмических структур соответствует свой оператор цикла. Популярное:
|
Последнее изменение этой страницы: 2016-07-12; Просмотров: 1541; Нарушение авторского права страницы