 |
 |
|
|
|
|
2.1. Итерационные вычисления
Реализация итерационных вычислительных процессов может быть основана на использовании оператора перехода или операторов цикла.
Оператор перехода
Оператор перехода осуществляет передачу управления в некоторую точку программы, таким образом, управление получает фактический или пустой оператор, имеющий соответствующую метку. Данный оператор универсален в том смысле, что на его основе может быть осуществлена реализация любого итерационного процесса. Синтаксическая схема оператора перехода имеет следующий вид:
<оператор перехода>::= goto <метка>
В качестве примера рассмотрим фрагмент программы, связанный с выводом чисел, соответствующим степеням числа 3 из диапазона [3, n]. Данный итерационный процесс с помощью оператора перехода мог бы быть реализован одним из следующих образов
(1)
...
GradeOfThree:= 3;
1: if GradeOfThree<= n then
begin
write ( GradeOfThree );
GradeOfThree:= GradeOfThree * 3;
goto 1
end
...
(2)
...
GradeOfThree:= 3
if n>= 3 then
begin
1: write ( GradeOfThree );
GradeOfThree:= GradeOfThree * 3;
if GradeOfThree<= n then goto 1
end
...
Необходимо отметить существование следующих ограничений на использование оператора перехода:
1) запрещается переход внутрь любого производного оператора;
2) запрещается переход с одной альтернативы на другую в выбирающем операторе.
Несмотря на простоту и универсальность реализации итерационных вычислений оператором перехода его использования следует избегать, так как потенциально, использование конструкций передачи управления в любую точку программы усложняет ее интерпретацию человеком, что может привести к ошибкам. Поэтому в рамках структурного программирования данный оператор, как правило, не используется, что и позволяет говорить о таких плюсах структурного программирования, как увеличение надежности и легкости сопровождения, упрощение модификации программных изделий. Сам структурный подход основан на применении следующих правил:
1) программа должна составляться последовательными шагами;
2) сложные задачи делятся на простые, каждая из которых имеет один вход и один выход;
3) логика программы должна базироваться на минимальное число базовых управляющих структур.
При этом для реализации итерационных процессов в рамках структурного программирования, в соответствии с п.3 сформированы специальные управляющие структуры - три оператора цикла.
Операторы цикла
Оператор цикла с предусловием
Синтаксис данного оператора имеет следующий вид:
<оператор цикла с предусловием>::= while <логическое выражение> do <оператор>
Итерационный процесс, задаваемый следующим фрагментом кода на базе оператора перехода
...
1: if not ( P ) then goto 2
S; goto 1;
2: ;
...
Может быть реализован на базе оператора цикла с предусловием следующим образом
...
while P do S
...
Данный оператор задает итерационный процесс, обладающий двумя свойствами:
1) в зависимости от условия процесс может не выполниться вообще;
2) количество итераций процесса заранее не известно, зависит также от условия.
Для реализации конечного итерационного процесса, в теле цикла должны присутствовать операторы, изменяющие значение переменных, входящих в условие.
Попытаемся реализовать пример со степенями числа три на базе оператора цикла с предусловием. Такая реализация будет по смыслу близка к варианту 1) в примере с оператором перехода:
...
GradeOfThree:= 3;
while GradeOfThree<= n do
begin
write ( GradeOfThree );
GradeOfThree:= GradeOfThree * 3
end
...
Оператор цикла с постусловием
Оператор цикла с постусловием является частным случаем оператора цикла с предусловием и отличается от него тем, что процесс, задаваемый под управлением данного оператора, выполнится хотя бы один раз. Реализуется это путем осуществления проверки на необходимость продолжения в конце тела цикла. Поэтому для реализации процесса, задаваемого оператором
while P do S
с помощью оператора цикла с предусловием требуется дополнительный условный оператор:
if P then
repeat S until not P
Синтаксис данного оператора имеет следующий вид:
<оператор цикла с постусловием>::= repeat <оператор> until <логическое выражение>
Необходимо также обратить внимание на то, что условием выхода из цикла с предусловием является ложность, тогда как условием выхода из цикла с постусловием является истинность значения предиката.
Реализация примера со степенями числа три на базе оператора цикла с постусловием по смыслу более близка к варианту 2) в примере с оператором перехода:
...
GradeOfThree:= 3;
if n>= GradeOfThree then
repeat
write ( GradeOfThree );
GradeOfThree:= GradeOfThree * 3
until GradeOfThree> n
...
Анализ реализаций данного процесса на базе операторов цикла с пред- и постусловиями приводит к выводу о том, что применение оператора while в данном случае оптимальнее по показателю сложности алгоритма, которая связана с дополнительным условным оператором, который появляется в примере с оператором цикла с постусловием. Это также очевидно для варианта 2) примера с оператором перехода и связано с тем, что значение n не определено. Наоборот, если бы имелась гарантия того, что n заведомо >= 3, то реализация данного итерационного процесса на базе цикла с постусловием, но уже без условного оператора, была бы предпочтительней. Это является хорошей иллюстрацией того, что цикл с постусловием реализует частный случай цикла с предусловием
Оператор цикла с параметром
С помощью данного оператора осуществляется дальнейшая конкретизация итерационного процесса, которая связана с тем, что до начала цикла число его итераций известно. Тогда каждая итерация будет связана с приращением (или уменьшением) параметра - переменной порядкового типа - в рамках, устанавливаемых границами цикла - выражениями того же типа, что и параметр. Приведем синтаксис данного оператора.
<оператор цикла с параметром>::= for <параметр>:= <нижняя граница> to <верхняя граница> do <оператор> | for <параметр>:= <верхняя граница> downto <нижняя граница> do <оператор>
Необходимо обратить внимание на два обстоятельства:
1) значение параметра цикла по нормальном его завершении не определено;
2) значение параметра цикла не должно изменяться в процессе выполнения операторов тела цикла.
Первая позиция связана с тем, что в различных реализациях соотнесение параметра с граничным значением происходит в различные моменты - до или после очередного его приращения (уменьшения). Сам параметр может как использоваться, так и не использоваться в операторах тела цикла, однако, изменяться ими он не должен.
Ниже представлена реализация вычислительных процессов, задаваемых циклами с постусловием и предусловием, циклом с параметром.
1) цикл с предусловием
Parametr:= LowPoint;
while Parametr<= LowPoint do
begin
S;
Parametr:= Succ ( Parametr )
end
2) цикл с постусловием
if HightPoint>= LowPoint then
begin
Parametr:= LowPoint;
repeat
S;
Parametr:= Succ ( Parametr )
until Parametr> HightPoint
end
3) соответствующий им цикл с параметром
for Parametr:= LowPoint to HightPoint do S
Наличие трех управляющих конструкций для реализации итерационных процессов обуславливается, с точки зрения структурного программирования, необходимостью представления различных по степени детерминированности процессов, соответствующими средствами. Три цикла направлены на реализацию трех типов итерационных процессов:
1) процесс, число повторений которого заранее известно;
2) процесс, который выполнится хотя бы один раз;
3) процесс, число повторений которого заранее не известно.
Необходимо также отметить наличие стандартных процедур Break и Continue, которые позволяют управлять итерациями циклов. При этом Break завершает оператор цикла, а Continue продолжает его со следующей итерации.
В рамках повышения эффективности вычислительных процессов, создаваемых на базе циклических структур применяют различные преобразования, основными из которых являются следующие:
1) Исключение инвариантных выражений. Основополагающий принцип - вынесение возможно большего числа операций за границы цикла.
for i:= 1 to 1000 do for j:= 1 to 1000 do
a:= b * c + d( i, j )
=> e:= b * c; => for i:= 1 to 1000 do
for j:= 1 to 1000 do
a:= e + d( i, j )
2) Сжатие циклов. Основной принцип - объединение тел двух циклов с одинаковыми параметрами.
for i:= 1 to 1000 do a( i ):= i;
for j:= 1 to 1000 do < >
b( j ):= 10 * j
=> for i:= 1 to 1000 do begin
a( i ):= i;
b( j ):= 10 * j
end
3) Разъединение циклов. Бывает полезно в случаях, подобных следующему:
{условный оператор выполняется 1000 раз, хотя логическая переменная c не изменяется} {условный оператор выполняется 1 раз} for i:= 1 to 1000 do if c then
b( i ):= a( i ) + b( i )
else
b( i ):= a( i ) √ b( i )
if c then for i:= 1 to 1000 do
b( i ):= a( i ) + b( i )
else
for i:= 1 to 1000 do
b( i ):= a( i )√b( i )
Пример использования операторов цикла
Разберем решение типичной задачи, связанной с итерационными вычислениями.
Текст задания
Пусть необходимо определить k √ количество трехзначных натуральных чисел, сумма цифр которых равна n (1 <= n <= 27 ). При этом операции деления ( /, div, mod ) не использовать.
Решение
Организуем три цикла √ по одному на каждую из цифр числа. Задача √ перебрать все возможные комбинации из трех цифр. Каждая цифра может принимать значение от 0 до 9 √ ти, что позволяет в качестве управляющих конструкций для организации трех итерационных процессов воспользоваться циклом с параметром. Будем складывать счетчики этих циклов и сравнивать с заранее введенным n. В случае равенства, будем инкриминировать счетчик k √ количества трехзначных чисел.
program CycleSample;
var
n, k, Digit1, Digit2, Digit3: Integer;
begin
writeln( ▒Введите n▓);
repeat
readln( n );
until (n>= 1) and (n<= 27);
k:= 0;
for Digit1:= 1 to 9 do {цикл по 1-ой цифре числа}
for Digit2:= 0 to 9 do {цикл по 2-ой цифре числа}
for Digit3:= 0 to 9 do {цикл по 3-ей цифре числа}
if Digit1 + Digit2 + Digit3= n then k:= k + 1;
writeln( ▒Результат - ▓, k);
end.
На рис. 1 изображена граф-схема алгоритма данной задачи.
Рис.1. Граф-схема алгоритма.
Варианты заданий
1. Дано 20 целых чисел. Определить, сколько из них принимает наибольшее значение.
2. Дано натуральное k. Вывести k-ую цифру последовательности 1123581321┘, в которой выписаны подряд все числа Фибоначчи.
3. Дана последовательность из не менее чем 2-х натуральных чисел, за которой следует 0. Вычислить сумму тех из них, порядковые номера которых - простые числа.
4. Дано натуральное k. Вывести k-ую цифру последовательности 149162536┘, в которой выписаны подряд квадраты всех натуральных чисел.
5. Дана непустая последовательность из натуральных чисел, за которой следует 0. Вычислить сумму тех из них, порядковые номера которых - числа Фибоначчи.
6. Вывести все простые делители заданного натурального числа.
7. Дано целое n>2. Вывести все простые числа из диапазона [2,n].
8. Дано 10 натуральных чисел. Найти их наибольший общий делитель.
9. Определить, является ли заданное натуральное число совершенным, т.е. Равным сумме всех своих (положительных) делителей, кроме самого этого числа (напр. Число 6 совершенно: 6=1+2+3).
10. Дана непустая последовательность ненулевых чисел, за которой следует 0. Определить, сколько раз в этой последовательности меняется знак (напр., в последовательности 1, -34, 8, 14, -5 знак меняется 3 раза).
11. Дано 20 вещественных чисел. Определить, сколько из них больше своих "соседей", т.е. Предыдущего и последующего чисел.
12. Дано не менее 3-х различных натуральных чисел, за которыми следует 0. Определить 3 наибольших числа среди них.
13. Определить число, получаемое выписыванием в обратном порядке цифр заданного натурального числа.
14. Дана последовательность из 20 целых чисел. Определить количество чисел в наиболее длинной подпоследовательности из подряд идущих нулей.
15. Дано 20 вещественных чисел. Найти порядковый номер того из них, которое наиболее близко к какому-нибудь целому числу.
16. Вывести в возрастающем порядке все трехзначные числа, в десятичной записи которых нет одинаковых цифр (операции деления не использовать).
17. Дано 10 вещественных чисел. Вычислить разность между максимальным и минимальным из них.
18. Дано натуральное k. Вывести k-ую цифру последовательности 12345678910111213┘, в которой выписаны подряд все натуральные числа.
19. Дана последовательность из 20-ти целых чисел. Определить, со скольких отрицательных чисел она начинается.
20. Определить, является ли заданное натуральное число палиндромом, т.е. Таким, десятичная запись которого читается одинаково слева направо и справа на лево.
21. Дано 20 вещественных чисел. Определить, образуют ли они возрастающую последовательность.
22. Даны целое n>0 и последовательность из n вещественных чисел, среди которых есть хотя бы одно отрицательное число. Найти величину наибольшего среди отрицательных чисел этой последовательности.
23. Найти сумму цифр заданного натурального числа.
24. Дана непустая последовательность различных натуральных чисел, за которой следует 0. Определить порядковый номер наименьшего из них.
25. Дано 20 вещественных чисел. Вычислить разность между максимальным и минимальным из них.
26. Логической переменной t присвоить значение true или false. в зависимости от того, можно или нет натуральное число n представить в виде суммы трех полных квадратов.
27. Логической переменной p присвоить значение true, если целое n (n > 1) √ простое число, и значение false иначе
28. Подсчитать k √ количество цифр в десятичной записи целого неотрицательного числа n.
29. Логической переменной t присвоить значение true или false, в зависимости от того, является ли заданное натуральное число k степенью 3 или нет.
30. Вычислить: y= sin1 + sin1.1 + sin1.2 + ┘+ sin2.
|
|
|
