Сложные алгоритмы
Декомпозиция сложной задачи
В предыдущих главах мы познакомились с тремя базовыми элементарными алгоритмическими конструкциями:
1) следование, линейные алгоритмы (см. рис. 7.1а);
2) ветвление (см. рис. 7.1б);
3) циклы:
а) с предусловием (см. рис. 7.1в);
б) с постусловием. (см. рис. 7.1г)
В чистом виде при решении прикладных задач эти алгоритмы встречаются весьма редко. Обычно приходится использовать различные их комбинации и сочетания. Каким бы сложным ни был алгоритм решения задачи, его реализация всегда сводится к рассмотренным выше элементарным конструкциям. Продемонстрируем сказанное на примере.
Задание 7.1.
Постановка задачи
Заданы целые положительные числа nиm. Вычислить значение
.
Выбор метода решения и проектирование
В соответствии с заданием требуется вычислить произведение, каждый сомножитель которого вычисляется как сумма ряда. Очевидно[1]:
Ни одна из рассмотренных выше базовых алгоритмических конструкций в чистом виде здесь не применима: мы уже умеем вычислять отдельно суммы, отдельно произведения, а с их сочетанием, когда одна конструкция входит в состав другой, сталкиваться не приходилось. Переформулируем постановку исходной сложной задачи, выделив в ее составе более простые. Процесс разбиения сложной задачи на составляющие ее более простые подзадачи, установления иерархических связей между этими подзадачами принято называть декомпозицией.
Вычислить 
, где 
Выделяя простые задачи, мы абстрагируемся от малозначительных для соответствующего уровня деталей. Так, при вычислении P в представленной постановке нас абсолютно не интересует, как вычисляется Si. Оно как-то вычисляется и бог с ним – нам сейчас (на данном, высоком уровне абстракции) важно, чтобы правильно был организован алгоритм вычисления произведения. При вычислении же Si(следующий, более низкий уровень абстракции), наоборот, мы абсолютно не заботимся о том, как будет использоваться вычисленное значение – важно правильно организовать алгоритм суммирования. Как решать эти задачи по отдельности, мы уже знаем, соответствующие блочные схемы показаны на рисунках 7.2а и 7.2 б. Подробнее с примененным здесь принципом абстракции можно познакомиться в главе 13. Окончательный алгоритм решения задачи 7.2 в получается в результате простой подстановки[2] блочной схемы, представленной на рисунке 7.2 б в схему 7.2 а.
Текст программы:
program ItIsEase;
var
N,M,I,J: Integer;
S,P: Real;
begin
Write(’n, m –? ’);
ReadLn(N,M);
P:= 1;
for I:= 1 to n do
begin;
S:= 0;
for J:= 1 to M do
S:= S+Sqr(I+J);
P:= P*S
end
WriteLn(’Результат P= ’,P:10:1);
ReadLn;
end.
Отладка и тестирование.
Протокол 7.1
Работа программы ItIsEasy
В качестве контрольного примера возьмем N=3, M=3. При правильной работе программы должно получиться P=111650.
1) На экран выводится сообщение:
n, m –?
2) Программа останавливается и ожидает, когда пользователь наберет строку ввода:
3€3¿
В результате N=3, M=3.
3) P:=1
4) Выполняется цикл по параметру I, меняющемуся с единичным шагом от 1 до 3.
4.1) I=1.
4.2) S:=0;
4.3) Выполняется цикл по параметру J, меняющемуся с единичным шагом от 1 до 3.
4.3.1) J:=1;
4.3.2) S:=S+Sqr(I+J)=0+Sqr(1+1)=4.0;
4.3.3) J:=2;
4.3.4) S:=S+Sqr(I+J)=4.0+Sqr(1+2)=13.0;
4.3.5) J:=3;
4.3.6) S:=S+Sqr(I+J)=13.0+Sqr(1+3)=29.0;
4.3.7) Цикл по параметру J закончен;
4.4) P:=P*S=1*29.0=29.0.
4.5) I=2.
4.6) S:=0;
4.7) Выполняется цикл по параметру J, меняющемуся с единичным шагом от 1 до 3.
4.7.1) J:=1;
4.7.2) S:=S+Sqr(I+J)=0+Sqr(2+1)=9.0;
4.7.3) J:=2;
4.7.4) S:=S+Sqr(I+J)=9.0+Sqr(2+2)=25.0;
4.7.5) J:=3;
4.7.6) S:=S+Sqr(I+J)=25.0+Sqr(2+3)=50.0;
4.7.7) Цикл по параметру J закончен;
4.8) P:=P*S=29.0*50.0=1450.0.
4.9) I=3.
4.10) S:=0;
4.11) Выполняется цикл по параметру J, меняющемуся с единичным шагом от 1 до 3.
4.11.1) J:=1;
4.11.2) S:=S+Sqr(I+J)=0+Sqr(3+1)=16.0;
4.11.3) J:=2;
4.11.4) S:=S+Sqr(I+J)=16.0+Sqr(3+2)=41.0;
4.11.5) J:=3;
4.11.6) S:=S+Sqr(I+J)=41.0+Sqr(3+3)=77.0;
4.11.7) Цикл по параметру J закончен;
4.12) P:=P*S=1450.0*77.0=111650.0.
4.13) Цикл по параметру I закончен;
5) Печать сообщения
Результат P=€€111650.0
6) Конец сеанса работы программы.
Задание 7.2.
Постановка задачи
Заданы целые положительные числа n иm, действительные числа – a иb. Вычислить
.
Выбор метода решения и проектирование
Проведем декомпозицию исходной задачи, вычленив в ее составе более простые и установив между ними иерархические связи:
Вычислить
, где 
, 
.
Как видим, и в этом случае нам удалось свести достаточно сложную задачу к комбинации простейших типовых задач. Окончательный алгоритм представляет собой комбинацию базовых алгоритмов (рисунок 7.2).
Текст программы:
program ItIsEasyToo;
var
I,N,M: Integer;
Sn,Sm,A,B,Y: Real;
begin
Write(‘Количество слагаемых в первой сумме? ’);
ReadLn(N);
Write(‘Количество слагаемых во второй сумме? ’);
ReadLn(M);
Write(‘Коэффициенты A и B? ’);
ReadLn(A,B);
Sn:= 0; {Вычисляем первую сумму}
for I:= 1 to N do
Sn:=Sn+Sqr(I);
Sm:=0; {Вычисляем вторую сумму}
for I:=1 to M do
Sm:=Sm+I;
Y:= A*Sn+B*Sqr(Sm);
WriteLn(‘Y= ‘, Y);
ReadLn;
end.