Реализация циклических алгоритмов

Реализация циклических алгоритмов

Алгоритм называется циклическим, если при его исполнении некоторые действия неоднократно повторяются, не смотря на то, что записаны они один раз. С точки зрения структурного программирования признаком циклического алгоритма является присутствие одной из структур:

- цикл с предусловием (цикл пока);

- цикл с постусловием (цикл до);

- цикл с параметром.

В Паскале каждой из этих трех алгоритмических структур соответствует свой оператор цикла.

Алгоритмическая структура цикл с предусловием

Словесно структура цикл с предусловием описывается следующим образом:

пока справедливо условие выполнения цикла повторять серию команд (тело цикла).

На схемах алгоритма структура цикла с предусловием изображается в соответствие с рис. 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

Естественно, что в таком алгоритме можно использовать разные виды операторов цикла, главное - должно выдерживаться следующее правило:

- цикл, который начинается раньше, позже заканчивается;

- цикл, который начинается позже, раньше заканчивается.

Это основное правило вложенности циклов.

Назначение

Оператор используется в алгоритмах, когда для каждого значения переменной из диапазона значений необходимо выполнять одинаковые действия. Эта переменная называется параметром цикла.

Синтаксис

Рис. 15.9. – Оператор цикла с параметром

Синтаксическое ограничение:

результаты вычислений выражений 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. Информационная модель

Статус	Назначение	Имя	Тип
Входная	год	G	WORD
Промежуточная	текущий месяц	i	mes
Промежуточная	признак правильности ввода номера года (true - успешно, false – ошибка)	vvod	boolean

Примечания:

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,
которые изменяются в диапазоне 1..10.

Алгоритмическая модель

Схема алгоритма вычисления таблицы умножения приведена на рис. 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 10:

Алгоритмическая модель

Рис. 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 – номер элемента суммы, . a_i – i-ый элемент суммы, eps – точность. В этом случае для накопления суммы

a.1) сумматор обнуляется

y: =0

a.2) очередной элемент ряда - первый

a: =a₁

a.3) фиксируется номер первого элемента

i: =1

a.4) пока очередной элемент a по абсолютной величине не соответствует точности (превышает заданную точность eps) повторяется добавление к сумматору очередного элемента, вычисляется значение нового элемента, номер элемента увеличивается на 1.

пока |a|> eps:

Для вычисления a_i применяем следующий подход – последовательность чисел, которая суммируется представляется как геометрическая последовательность (вычисляется значение первого элемента ряда a₁ и выводится формула знаменателя геометрической прогрессии q). Для нашей задачи

a₁=x

Таким образом, зная a₁(a: = a₁), любой следующий элемент вычисляется по формуле

b.1) Вывод результата заключается в том, что выводятся значения аргумента x, результата расчета y, стандартной функции sin(x), погрешности - |y-sin(x)|, после этого увеличивается значение счетчика заполненных строк экрана (k) на 1, затем при необходимости производится очистка экрана.

b.2) Очистка экрана производится

если k=23 Þ

Информационная модель

Таблица 15.3. - Информационная модель

Статус	Назначение	Имя	Тип
Вход	начало диапазона	xn	Real
Вход	конец диапазона	xk	Real
Вход	шаг изменения	hx	Real
Пром	аргумент	x	Real
Выход	результат функции	y	Real
Пром	элемент суммы	a	Real
Пром	номер элемента	i	Integer
Пром	счетчик строк	k	Integer

Программная модель

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.

Реализация циклических алгоритмов

- цикл с предусловием (цикл пока);

- цикл с постусловием (цикл до);

- цикл с параметром.

В Паскале каждой из этих трех алгоритмических структур соответствует свой оператор цикла.

12 3 4 5 Следующая ⇒