Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


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



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

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

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

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

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

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

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

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

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

На схемах алгоритма структура цикла с предусловием изображается в соответствие с рис. 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 – номер элемента суммы, . 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. - Информационная модель

Статус Назначение Имя Тип
Вход начало диапазона 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.

 

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

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

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

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

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

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


Поделиться:



Популярное:

  1. В четвёртых, творческая реализация человека необходима окружающим людям, всему человечеству.
  2. Влияние циклических процессов на судьбы людей и щинициации
  3. Выбор и реализация стратегии фирмы
  4. Известны различные способы записи алгоритмов: словесная запись, формульная, табличная, на языке блок-схем или алгоритмическом языке.
  5. Кинематический анализ эпициклических механизмов, суть метода Виллиса.
  6. Лекция №8 Средства для реализации алгоритмов управления.
  7. Методика расчета алгоритмов физической нагрузки при использовании тренажеров нового поколения
  8. Непосредственная реализация права: понятие, признаки, формы.
  9. Объединение регионов: проекты и их реализация.
  10. Определение адекватных способов разрешения конфликта и их реализация.
  11. ОРГАНИЗАЦИЯ ОБСЛУЖИВАНИЯ ОТ ЭВМ ЦИКЛИЧЕСКИХ ПРОЦЕССОВ В РЕЖИМЕ РАЗДЕЛЕНИЯ ВРЕМЕНИ
  12. ПМ. 01. «Реализация лекарственных средств


Последнее изменение этой страницы: 2016-07-12; Просмотров: 1486; Нарушение авторского права страницы


lektsia.com 2007 - 2024 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.204 с.)
Главная | Случайная страница | Обратная связь