Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Алгоритмический процесс для решения многих задач содержит повторяющуюся последовательность действий – цикл, перед циклом выполняются некоторые подготовительные действия, а после него - завершающие действия.
Если число повторений известно до начала выполнения цикла, то используется цикл типа ДЛЯ. Если число повторений заранее неизвестно (или шаг параметра цикла не равен 1 или –1 в языке Pascal), то используется цикл типа ПОКА. Цикл типа ПОКА позволяет запрограммировать любые повторяющиеся последовательности действий (более универсален, чем цикл типа ДЛЯ).
Задача 6.6. Задано натуральное число N >=0. Составить программу для вычисления суммы
S= 12 + 22 + 32 + 42 + … + N2
Схема алгоритма (два варианта) задачи 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)-й член:
an / an-1 =
(-1)n xn / n! = (-1)1 x1 (n-1)! = - x (n-1)! = - x
(-1)(n-1) x(n-1) / (n-1)! n! (n-1)! n n
тогда an = - an-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, X1, X2,..., Xn
Алгоритм последовательной обработки элементов в этом случае удобно записывать в виде цикла типа ДЛЯ (пример на языке Pascal):
ReadLn (n);
for i:=1 to n do begin
ReadLn (X);
Обработка X;
End
Входная последовательность может быть задана с признаком конца последовательности:
X1, X2,..., Xn, 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. Определить, является ли заданная последовательность чисел a1 , a2 ,..., aN, 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. Числа Фибоначчи (Fi) определяются по формулам F0 = F1 = 1; Fi = Fi –1 + Fi –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
Дата публикования: 2015-01-14; Прочитано: 430 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!