Циклические алгоритмы

Алгоритмический процесс для решения многих задач содержит повторяющуюся последовательность действий – цикл, перед циклом выполняются некоторые подготовительные действия, а после него - завершающие действия.

Если число повторений известно до начала выполнения цикла, то используется цикл типа ДЛЯ. Если число повторений заранее неизвестно (или шаг параметра цикла не равен 1 или –1 в языке Pascal), то используется цикл типа ПОКА. Цикл типа ПОКА позволяет запрограммировать любые повторяющиеся последовательности действий (более универсален, чем цикл типа ДЛЯ).

Задача 6.6. Задано натуральное число N >=0. Составить программу для вычисления суммы

S= 1² + 2² + 3² + 4² + … + N²

Схема алгоритма (два варианта) задачи 6.6. представлена на рис. 6.8.

Рис. 6.8. Схема алгоритма задачи 6.6 (два варианта).

Решение задачи 6.6. на языке Turbo Pascal:

Program Summa;

Var N, {заданное число}

S, {искомая сумма}

I: Integer; {параметр цикла, а также очередное слагаемое}

BEGIN

Write('Введите N = '); ReadLn(N);

S:=0;

For i:=1 to N do

S:=S + i*i;

WriteLn('Сумма = ', S);

ReadLn

END.

Пояснения к программе:

1) Начальное значение суммы S равно 0.

2) Оператор For i:=1 to N do обеспечивает повторение тела цикла (оператора S:=S + i*i;) N раз. На каждом шаге к сумме добавляется одно слагаемое, равное квадрату номера шага - i.

Тест. Вход: N=3

Выход: Сумма= 14

Трассировочная таблица:

Номер шага=

N=

i=

I<=N

1<=3 да

2<=3 да

3<=3 да

4<=3 нет

S=

0+12=1

1+22=5

5+32=14

Ответ: Сумма = 14

Решение задачи 6.6. на языке QBasic:

INPUT "Введите N = "; N

S = 0

FOR I = 1 TO N

S = S + I*I

NEXT I

PRINT "Сумма = "; S

END

Задача 6.7. Составить программу для решения следующей задачи. Задано натуральное число N >=0. Для заданного значения X вычислить сумму

где n! = 1^. 2^. 3...^. n (читается как "n-факториал").

Тест. Вход: x=1 n=3

Выход:

Решение задачи 6.7. на языке Turbo Pascal:

Program Sum;

Var x, S, а: Real; {а - очередное слагаемое}

i, n: Integer;

BEGIN

Write('Введите n = '); ReadLn(n);

Write('Введите x = '); ReadLn(x); WriteLn;

S:= 1; а:= 1;

For i:= 1 to n do begin

а:= - а*x /i; {вычисление очередного слагаемого}

S:= S + а

end;

WriteLn('О т в е т: S = ', S); ReadLn

END.

Пояснения к программе:

1) Формулу для вычисления очередного слагаемого можно получить, разделив n-й член последовательности на (n-1)-й член:

a_n / a_n-1 =

(-1)ⁿ xⁿ / n! = (-1)¹ x¹ (n-1)! = - x (n-1)! = - x

(-1)^(n-1) x^(n-1) / (n-1)! n! (n-1)! n n

тогда a_n = - a_n-1 * x / n (формула 6.1.)

2) Начальное значение суммы S=1, значение первого слагаемого а =1.

3) Значение искомой суммы вычисляется за n шагов. На каждом шаге пересчитывается очередное слагаемое по формуле 6.1. и добавляется к сумме.

Решение задачи 6.7. на языке QBasic:

INPUT "Введите n = ", n

INPUT "Введите x = ", x

S = 1: а = 1

FOR i = 1 TO n

а = -а * x / i

S = S + а

NEXT i

PRINT: PRINT "О т в е т: S = "; S

END

В ряде задач необходимо обработать последовательность входных элементов. Если каждый элемент используется не более одного раза и обрабатывается в том же порядке, в каком вводится, то в оперативной памяти не требуется хранить сразу все элементы. Достаточно одной (в некоторых задачах двух-трех) переменной для текущего элемента. В эту переменную по очереди вводятся все входные элементы.

Входная последовательность может быть задана с указанием количества элементов n >= 0 следующим образом:

n, X₁, X₂,..., X_n

Алгоритм последовательной обработки элементов в этом случае удобно записывать в виде цикла типа ДЛЯ (пример на языке Pascal):

ReadLn (n);

for i:=1 to n do begin

ReadLn (X);

Обработка X;

End

Входная последовательность может быть задана с признаком конца последовательности:

X₁, X₂,..., X_n, W

где n - количество элементов последовательности (n >= 0), заранее неизвестно, W - признак конца последовательности, известен заранее, должен отличаться от всех элементов последовательности. Алгоритм обработки последовательности элементов удобно записывать в виде цикла типа ПОКА (пример на языке Pascal):

ReadLn (X);

while X <> W do begin

Обработка X;

ReadLn (X);

End

Задача 6.8. Задано натуральное число N >=1 и последовательность из N вещественных чисел. Составить программу для определения наибольшего значения в заданной последовательности.

Решение задачи 6.8. на языке Turbo Pascal:

Program MAX;

Var N, {заданное количество}

I: Integer; {параметр цикла}

A, {текущий элемент последовательности}

maxA: Real; {текущий максимум}

BEGIN

Write('Введите N = '); ReadLn(N);

WriteLn ('Введите последовательность элементов ');

ReadLn(maxA);

For i:=2 to N do begin

ReadLn(A);

If A> maxA then maxA:=A;

End;

WriteLn('Наибольшее значение равно ', maxA);

ReadLn

END.

Пояснения к программе:

В программе использован следующий метод определения максимума. Пусть maxА обозначает максимальный член просмотрен­ной части последовательности (текущий максимум). Начальное зна­чение maxА принимается равным первому элементу последовательности.

В переменную А вводится очередной текущий элемент последовательности. Если текущий элемент А оказался больше maxА, то текущий максимум - maxA заменяется на значение величины А.

Решение задачи 6.8. на языке QBasic:

INPUT "Введите N = "; N

PRINT "Введите последовательность элементов "

INPUT MAXA

FOR i=2 TO N

INPUT A

IF A> MAXA THEN MAXA=A;

NEXT i

PRINT "Наибольшее значение равно "; MAXA

END

Тест:

Вход: 4

6 9 15 7

Выход: Наибольшее значение равно 15

Трассировочная таблица:

Номер шага=

N=

i=

I<=N

2<=4 да

3<=4 да

4<=4 да

5<=4 нет

A=

MAXA=

A> MAXA

9>6 да

15>9 да

7> 15 нет

Ответ: Наибольшее значение равно 15

Задача 6.9. Задана последовательность натуральных чисел, завершающаяся числом 0. Определить, является ли заданная последовательность чисел a₁ , a₂ ,..., a_N, 0 монотонно убывающей.

Тест1. Вход: 89 56 45 12 2 0

Выход: Последовательность монотонно убывает.

Тест2. Вход: 89 56 65 12 2 0

Выход: Последовательность монотонно не убывает.

Решение задачи 6.9. на языке Turbo Pascal:

Program Posl;

Var

I, {параметр цикла}

Apred, { предыдущий элемент последовательности }

A: Integer; {текущий элемент последовательности}

P: Boolean; {признак убывания P= TRUE -убывает}

{ P= FALSE – не убывает }

BEGIN

P:= TRUE;

WriteLn('Введите последовательность чисел и 0 ');

ReadLn(A);

While (A <> 0) and P do begin

Apred:= A;

ReadLn(A);

If A> =Apred then P:=FALSE;

End;

If P then WriteLn (' Последовательность монотонно убывает.')

else WriteLn (' Последовательность монотонно не убывает.')

ReadLn

END.

Пояснения к программе:

1) Переменные Apred и А предназначены для хранения предыдущего и текущего членов входной последовательности соответственно. Перед вводом очередного элемента его значение сохраняется как предыдущее:

Apred:= A;

ReadLn(A);

2) В программе использована булевская переменная Р, которая служит признаком убывания. Начальное значение переменной Р =TRUE (истина). Значение переменной Р меняется на FALSE, если текущий член последовательности окажется равным или большим предыдущего члена, т.е. нарушится условие монотонного убывания.

3) В программе используется цикл типа ПОКА:

While (A <> 0) and P do begin

….

End;

Цикл работает при выполнении двух условий: очередное число А не равно 0 и переменная Р истинна. Нарушение хотя бы одного из условий приведет к завершению цикла.

4) После завершения цикла проверяется значение признака убывания Р. По результату сравнения формируется ответ:

If P then WriteLn (' Последовательность монотонно убывает.')

else WriteLn (' Последовательность монотонно не убывает.')

Решение задачи 6.9. на языке QBasic:

P=1;

PRINT "Введите последовательность чисел и 0 "

INPUT A

WHILE (A <> 0) and (P=1)

Apred= A

INPUT A

IF A> =Apred THEN P=0

WEND

IF P=1 THEN

PRINT "Последовательность монотонно убывает. "

ELSE

PRINT " Последовательность монотонно не убывает. "

END IF

END

Задача 6.10. Числа Фибоначчи (F_i) определяются по формулам F₀ = F₁ = 1; F_i = F_{i –1} + F_{i –2} при i = 2, 3,... (каждое очередное число равно сумме двух предыдущих). Вычислить сумму всех чисел Фибоначчи, которые не превосходят заданного натурального числа М (M>1).

Тест. Вход: M=10

Выход: S=1+1+2+3+5+8=20

Решение задачи 6.10. на языке Turbo Pascal:

Program Fib;

Var M, {заданное число }

F0, F1, F2, {три последовательных числа Фибоначчи}

S: Integer; {сумма чисел Фибоначчи}

BEGIN

Write(’Введите натуральное М >1: ’);

ReadLn(M);

F0:=1; F1:=1;

Write(’Числа Фибоначчи, не превосходящие ’, M, ’:’, F0:4, F1:4);

If (M<3) then S:=M;

else begin

S:=2; F2:=2;

While F2<M do begin

Write(F2: 4);

S:=S+F2;

F0:=F1; F1:=F2;

F2:=F0+F1;

End;

End;

WriteLn(’О т в е т: Сумма этих чисел равна ’, S);

ReadLn

END.

Решение задачи 6.10. на языке QBasic:

INPUT "Введите натуральное М: ", M

F0 = 1: F1 = 1

PRINT "Числа Фибоначчи, не превосходящие "; M; ": "; F0; F1;

IF M < 3 THEN

S =M;

ELSE

S = 2: F2 = 2;

WHILE F2 < M

PRINT F2;

S=S+F2

F0=F1: F1=F2

F2=F0+F1

WEND

END IF

PRINT: PRINT "О т в е т: Сумма этих чисел равна "; S

END