Некоторые приемы вычислений значений полиномов и сумм числовых и функциональных рядов

Лекция 18

Тема: Операторы цикла

Цель : Изучение операторов цикла объем 1ч

Одной из важнейших алгоритмических структур является цикл. Цикл представляет собой последовательность операторов, которая выполняется неоднократно. В программах, связанных с обработкой данных или вычислениями, часто приходится выполнять циклически повторяющиеся действия. Циклы позволдяют записать такие действия в компактной форме.
В языке программирования Паскаль имеется три разновидности цикла - цикл со счетчиком, цикл с предусловием и цикл с постусловием.
Циклические действия могут быть реализованы при помощи инструкций for, while, repeat.

Оператор for

Оператор цикла for служит для организации цикла с известным числом повторений.
В общем виде оператор for записывается так:
For счетчик:= начальное значение to конечное значение do
Begin
{Последовательность операторов}
End;

Примечание: если между begin и end находится только одна инструкция, то слова begin и end можно не писать.
Обычно в качестве выражений, определяющих значения начального и конечного состояния счетчика циклов, используются переменные или константы.
Например
For i:=1 to 10 do
Begin
Writeln(i);
End;
На экран будут выведены числа 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 - каждое число на отдельной строке.
Если в инструкции For вместо слова to записать, то после очередного цикла значение переменной цикла будет не увеличиваться, а уменьшаться.
Например
For i:=100 downto 0 do
Begin
Writeln(i);
End;
На экран будут выведены числа от 100 до 0.

Пример программы
Вывести на экран таблицу значений функции y=x, х изменяется от 1 до 20 с шагом 1.
Program cikl;
uses crt;
var
i, x: integer;
y: real;
begin
clrscr;
writeln ('Таблица значений функции');
for i:=1 to 24 do
write (' - ');
writeln;
writeln('x y');
for i:=1 to 24 do
write (' - ');
writeln;
for i:=1 to 20 do
begin
y:= sqrt (x);
writeln(x:5, ' ',y:5:2);
end;
readln
end.

Оператор while

Оператор позволяет организовать цикл, число повторений вычислений которого зависит от записанного в нем условия.
В общем виде оператор while записывается так:
While условие do
Begin
{Последовательность операторов}
End;
Где условие - выражение логического типа, определяющее условие выполнение цикла - операторов, находящихся между begin и end.
Примечание: если между begin и end находится только одна инструкция, то слова begin и end можно не писать.
Оператор while выполняется следующим образом: если логическое выражение имеет значение true, то выполняются операторы, входящие в тело цикла. Как только логическое выражение примет значение false, выполнение операторов цикла прекращается. Если логическое выражение с самого начала имеет значение false, то оператор не выполняется. Значение переменных, входящих в условие, должны изменяться в теле цикла, иначе оператор никогда не будет завершен.
Например:
X:=1;
While x<100 do
Begin
Y:=a*x*x;
Writeln (y);
X:=x+2;
End;

Пример программы.
Определить остаток от деления двух чисел(а и b>0), не используя операции div и mod.
uses crt;
var
a, b, r: integer;
begin
clrscr;
writeln ('введите число а');
readln(a);
writeln ('введите число b');
readln(b);
r:=a
while r>b do
r;=r-b;
writeln('остаток от деления r=',r);
readln
end.

Оператор repeat

Оператор Repeat, как и оператор While , позволяет организовать цикл с неизвестным числом повторений. В отличие от оператора While в этом операторе проверка условия проводится после каждой итерации; обеспечивается выполнение, по крайней мере, одного вычисления в цикле (когда значение логического выражения ложно); тело цикла может содержать не один, а несколько операторов без записи их в составном операторе.
В общем виде оператор repeat записывается так:
Repeat
{Последовательность операторов}
until условие;
Где условие - выражение логического типа, определяющее условие завершения цикла.
Например:
I:=1;
Repeat
Writeln (i);
I:=i+3;
Until i:=19;

Пример программы.
Расмотрим программу определения простых чисел в диапазоне от 1 до 700 (число называется простым, если оно делится только на единицу и на себя).

Program prost;
uses crt;
var
i, n, d, r: integer;
begin
clrscr;
for n:=1 to 700 begin
d:=2 ;{ будем делить на два}
repeat
r:=n mod d;
if r<> 0 {n не разделилось на d}
then d:=d+1;
until r=0; {пока не нашли число, на которое делится n}
if d=n
then write (n, ' ');
end;
readln
end.

Cимволы

Для хранения и обработки отдельных символов используются переменные типа char. Значением переменной типа char может быть любой символ.
Переменная символьного типа должна быть объявлена в разделе описания переменных так:
Имя: char;
Где имя - имя переменной символьного типа,char - ключевое слово обозначения символьного типа.
Например
A:char;
X:char;
Как и любая переменная программы, переменная типа char может получить значение в результате выполнения оператора присваивания или ввода (read, readln). Если переменная типа char получает значение в результате выполнения операции присваивания, то справа от знака := должно стоять выражение типа char, например, переменная типа char или символьная константа - символ, заключенный в кавычки.
Например, в результате выполнения программы
Program otvet;
Var
f1, f2, a: char;
begin
f1:='+';
f2:=c1;
write '(продолжить программу?)';
readln (a);
writeln ('Ваш ответ:', a);
end.
Переменная f1 получит значение присвоением значения константы, f2- присвоением значения переменной f1, а значение переменной а вводится с клавиатуры.
Переменная а объявлена как char, т.е. один символ, поэтому если в ответ на вопрос программы будет введено, например, слово "да", то значением переменной а будет один символ - буква "д".
Каждый символ кодируется числом. Однако не все символы есть на клавиатуре, например, на клавиатуре нет символов, с помощью которых рисуются рамки. Если в программе нужно ввести на экран символ, которого нет на клавиатуре, то можно воспользоваться функцией char, возвращающей в качестве значения символ, код которого указывается при обращении к функции.
Пример программы
Program kod;
uses crt;
var i, j, a: integer;
begin
clrscr;
for i:=0 to 15 do
begin
a:=i+32;
for j:=2 to 15 do
begin
write(chr(186));
if a <100 then write (' ');
write (a, chr(a));
a:=a+16;
end;
writeln;
end;
readln
end.
Результат работы программы.

Cтроки

Помимо массива символов для хранения и обработки строк можно использовать переменные типа String.
Переменная типа string должна быть объявлена в разделе переменных так:
Имя:String;
или
Имя:String[длина];
где имя - имя переменной строкового типа;
String - ключевое слово обозначения строкового типа;
длина - константа целого типа, определяющая, что значением объявляемой переменной может быть любая строки, длина которой (количество символов) не превышает указанное в объявлении значение.
Например:
Name: string [25];
K: string;
Если при объявлении переменной длина строки не указывается, то предполагается, что длина строки равняется 255 символам, т.е. объявления:
Str:String[255];
Str: String; эквивалентны.
В тексте программы последовательность символов, являющаяся в одинарные кавычки.
Например:
fio:='Андреев';
или
Parol:='1949';
Функция Lenght(str) определяет длину аргумента str строкового типа.
Процедура Delete (строка, p, n) используется для того, чтобы удалить n символов в строковой переменной строка, начиная с позиции p.
Имеется также процедура Insert для вставки одной строки в другую.
Функция Copy (строка, p, n) копирует n символов строки строка, начиная с позиции p. Возвращаемое функцией строковое значение можно присвоить другой строковой переменной.
Функция Pos (подстрока, строка) определяет начальную позицию подстроки в строке.
Например, результат вызова Pos('F(x)','Let F(x)=2x') равен 5.
Если подстрока не вставляется в строке, значение Pos будет равно нулю.
Имееются процедура преобразования изображения числа в число - Val.
Процедура Val имеет вид:
Val (строка, число, код);
Например:
Val ('1, 2529',n, code);
Функция Concat возвращает строку, являющуюся объединением строк, указанных при вызове функции.
Concat (s1[,s2,..sn]:string):string;
Например:
a1:='студент'; a2:='отличник';
a3:=concat (a1,'Макаров',a);
Пример программы
Рассмотрим программу объединения двух строк, введенных с клавиатуры.
Program Simvol;
uses crt;
Var S1, S2, S3:String;
begin
clrscr;
writeln('Введите первую строку');
readln(s1);
writeln('Введите вторую строку');
readln(s2);
S3:=Concat (s1,s2);
writeln('Результат конкатенации двух строк:',S3);
Readln;
end.

Операторы цикла используются при организации циклов. Цикл – это последовательность операторов, которая может выполняться более одного раза. В Паскале существуют три вида операторов цикла: for, - если число повторений цикла известно, и while или repeat – в противном случае.

Оператор FORможет быть представлен в двух форматах:

for <переменная> := < нач.значение> to <конечное> do <оператор>

или

for <переменная> := < нач.значение> downto <конечное> do <оператор>

Оператор for обеспечивает выполнение тела цикла до тех пор, пока не будут перебраны все значения параметра цикла от начального до конечного. Например, оператор

for i:=1 to 20 do write(‘*’);

20 раз выведет на экран в одной строке символ «*», а оператор

for i:=1 to 20 do writeln(sqrt(i));

выведет 20 результатов извлечения квадратного корня из i, причем каждый результат будет находиться в отдельной строке.

Начальный и конечный параметры цикла должны быть одинаковых типов. Это может быть любой скалярный тип. Если используются типы integer, byte и интервальный, то значение параметра цикла последовательно увеличивается (при for..to) или уменьшается (при for.. downto) на единицу при каждом повторе. Если начальное значение меньше конечного, то используется форма вида:

for i:=1 to n do <оператор>

Если начальное значение больше конечного, то используется форма вида:

for i:=1 downto n do <оператор>

Оператор	Результат
for i:=10 to 14 do write(i:3)	10 11 12 13 14
for i:=14 to 10 do write(i:3)	14 13 12 11 10
for ch:=’a’ to ‘e’ do write(ch:2)	a b c d e
for ch:=’e’ downto ‘a’ do write(ch:2)	e d c b a

В теле цикла его параметр меняться не должен. В операторе for после do может находиться составной оператор, в теле которого запрещены операторы, меняющие значение параметра цикла:

for i:=1 to 10 do

Begin

rez:= i / 3.14;

write(rez)

end;

В теле оператора for могут находиться другие операторы for. Это позволяет строить циклы, содержащие внутренние циклы. Такие внутренние циклы называются вложенными:

for i := 1 to 10 do

for j := 1 to 5 do

a[i, j] := 0; {обнуление элементов матрицы}

При нормальном выходе из цикла значение его параметра равно конечному значению (верхней границе); иначе – не определено. Из цикла можно выходить до момента достижения параметром цикла конечного значения по оператору goto.

for i:=1 to 45 do

Begin

f := f + i;

if(f >100) or (i = 39) then goto m1

end;

m1 : …

Однако с точки зрения структурного программирования, такой путь не является правильным. В связи с этим во всех случаях, где возможен преждевременный выход из цикла, следует применять операторы repeat и while.

Пример 6.4 Программа вычисляет произведение 100 чисел.

program p64;

var i : integer; a, s : real;

begin s := 1;

for i := 1 to 100 do

Begin

read(a); s := s * a

end;

writeln(s)

End.

Пример 6.5 Вводится последовательность из n целых чисел. Найти наибольшее число.

program p65;

var n, x, max, i : integer;

Begin

write(‘Введите длину последовательности n=’); readln(n);

write(‘Введите х = ’); readln(x);

max := x;

for i := 2 to n do

Begin

write(‘Введите х = ’); readln(x);

if x > max then max := x;

end;

writeln(‘Наибольшее из чисел равно ‘, max);

End.

Пример 6.6Вычислить значение функции для х Î [10, 20].

program p66;

var x : integer; y : real;

Begin

for x := 10 to 20 do

Begin

y := sqrt((x-1)/(x+1));

write(‘При х=’, x, ‘y=’:4, y:7:5);

End

End.

Но в задачах бывают случаи, когда надо вычислить значение функции f(x) при x, изменяющимся от 0 до 1 с шагом 0,05. В этом случае вводится новая переменная, например, k : integer такая, что:

x := 0;

for k := 0 to 20 do begin

y := 3.5*(x+exp(x));

write(‘При х=’, x, ‘y=’:4, y:7:5);

x := x + 0.05;

end;

Пример 6.7 Дано натуральное число n. Определить, является ли оно простым (простое число – число, которое имеет только два делителя – само число и единица).

program p67;

var i, n, f : integer;

Begin

write(‘Введите натуральное число n=’); readln(n);

f:=0;

for i := 2 to n div 2 do

if n mod i = 0 then f := 1;

if f = 0 then writeln(‘Число ‘, n:7, ‘ простое’)

else writeln(‘Число ‘, n:7, ‘ не является простым’)

End.

Пример 6.8 Даны натуральные числа m и n. Определить их наибольший общий делитель.

program p68;

var i, n, m, k, nod : integer;

Begin

write(‘Введите натуральное число m=’); readln(m);

write(‘Введите натуральное число n=’); readln(n);

if n > m then k:=m else k := n;

for i := 1 to k do

if (n mod i = 0) and (m mod i = 0) then nod := i;

writeln(‘Наибольший общий делитель чисел ’, n, ‘ и ‘, m, ‘ равен ‘, nod)

End.

Задание 6.4

1. Дан интервал натуральных чисел от n до m. Определите все простые числа в этом интервале.

2. Дано натуральное число n. Определите все простые числа, не превосходящие n.

3. Дано натуральное число n. Разложите его на простые множители.

4. Дано натуральное число n. Определите, является ли оно совершенным (совершенное число n равно сумме всех своих делителей, не превосходящих само n).

5. Даны натуральные числа m и n. Определите, являются ли они взаимно простыми (взаимно простые числа не имеют общих делителей, кроме 1).

6. Даны натуральные числа m и n. Определите их наименьшее общее кратное.

7. Определите наименьшее из чисел 0,001×sin⁴k для k = 1, 2, …, n.

8. Вводится последовательность из n целых чисел. Найдите сумму всех отрицательных чисел.

9. Вводится последовательность из n целых чисел. Найдите, сколько в ней нулей.

10. Вводится последовательность из n целых чисел. Найдите наибольшее отрицательное число.

Оператор WHILE

while <условие> do <оператор>

Тип условия – boolean; оператор выполняется, пока значение выражения условия остается истинным. Проверка истинности условия осуществляется перед выполнением тела цикла. Поэтому этот оператор называется оператором цикла с предусловием. Если условие не выполняется, то тело цикла может не выполниться ни одного раза и произойдет переход к следующему оператору:

i := 30;

while i<0 do i:=i+1;

write(i);

В данном случае наращивание i не произойдет, так как условие с самого начала имеет значение false.

Пример 6.9 На вход программы поступают числа. Программа подсчитывает количество чисел, принадлежащих заданному интервалу [a, b]. Признаком конца входной последовательности служит число 0.

program p69;

const a = 2.71; b = 8.54;

var x : real; n : integer; m : boolean;

begin read(x); n := 0;

while x <> 0 do

Begin

m := (x >= a) and (x<=b);

if m then n:=n+1;

read(x)

end;

write(n)

End.

Оператор REPEAT

Repeat

<оператор>

<оператор>

…

until <условие>;

Тело цикла (т.е. операторы, находящиеся между ключевыми словами repat/until) выполняется, пока значение выражения условия – false.

Проверка истинности условия осуществляется после выполнения тела цикла. Поэтому этот оператор называется оператором цикла с постусловием.

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

Так как условие проверяется после выполнения тела цикла, оператор repeat выполняется по крайней мере один раз. Поэтому важно четко проследить правильность вхождения в цикл и выхода из него. При неправильной организации выхода может также возникнуть ошибка переполнения, поскольку наращивание какой-либо величины в теле цикла будет продолжаться до бесконечности.

Пример 6.10 Программа вычисляет сумму четных чисел в интервале от 0 до 10 включительно.

program p610;

uses crt;

var i, sum : integer;

Begin

i :=0; sum := 0;

Repeat

sum := sum + i;

i := i + 2

until i>10;

writeln(‘Сумма четных чисел равна ‘, sum)

End.

Пример 6.11 Написать фрагмент программы, вычисляющей n! с использованием разных операторов цикла:

с использованием оператора for

s := 1; for i := 2 to n do s := s*i;

с использованием оператора repeat

i := 0; s := 1; repeat i := i+1; s := s*i until i = n;

с использованием оператора while

i := 1; s := 1; while i <n do begin i := i+1; s := s*i end;

Очевидно, что в данном случае запись с использованием for самая короткая.

Задание 6.5

1. Дано натуральное число n. Определите, является ли оно автоморфным (автоморфное число n равно последним разрядам своего квадрата: 5 ~ 25, 6 ~ 36, 25 ~ 625.

2. Дано натуральное число n. Определите, является ли оно палиндромом (палиндром одинаково читается слева направо и справа налево: 3; 77; 353; 789987).

3. Вводится последовательность целых чисел, 0 – конец последовательности. Найдите два наименьших числа.

4. Вводится последовательность целых чисел, 0 – конец последовательности. Определите, содержит ли последовательность хотя бы два равных соседних числа.

5. Вводится последовательность целых чисел, 0 – конец последовательности. Определите, сколько раз последовательность меняет знак.

6. Вводится последовательность произвольных чисел, 0 – конец последовательности. Определите, сколько раз последовательность меняет знак.

7. Вводится последовательность ненулевых чисел, 0 – конец последовательности. Определите, является ли последовательность возрастающей.

8. Вводится последовательность целых чисел, 0 – конец последовательности. Определите, является ли последовательность знакопеременной.

9. Вычислить значение функции y = для х Î [2,8; 5,8] с шагом 0,3 всеми тремя видами операторов цикла.

10. Вычислить значение функции y = 1 – е^{-(х + 0,7)} для х Î [-0,7; 2,3] с шагом 0,4 всеми тремя видами операторов цикла.

Некоторые приемы вычислений значений полиномов и сумм числовых и функциональных рядов

Пример 6.12 Вычислить значение полинома 8-ой степени

f(x) = a₀x⁸ + a₁x⁷ + … a₈,

где a_i = (-1)ⁱa₀(i!). Воспользоваться схемой Горнера:

f(x) = (…((a₀x + a₁) x + a₂) x…a₇) x + a₈.

Если предварительно присвоить значение коэффициента а₀ переменной f, то весь процесс сведется к многократному повторению двух операторов f := f*x; f := f+a;

program p612;

var x, a, f : real; i : integer;

begin read(a, x); f := a;

for i := 1 to 8 do

Begin

f := f * x; a := -a * i; f := f + a

end;

writeln(f)

End.

Пример 6.13 Вычислить сумму числового ряда s = .

Обозначим a_k = (-1)^k-1 , a_k – функция параметров цикла. Здесь каждое слагаемое приходится вычислять заново, но для хранения его значения можно использовать одно и то же поле памяти, записывая очередное значение на место предыдущего.

Распишем сумму следующим образом:

s = - + - … + (-1)^k-1 +…+(-1)^n-1 .

Тогда программы вычисления суммы числового ряда примет вид:

program p613;

const n = 25;

var z, k : integer; a, s : real;

begin s := 0; z := 1;

for k := 1 to n do

Begin

a := z/sqrt(k);

s := s + a; z := -z;

end;

writeln(s)

End.

Пример 6.14 Вычислить сумму функционального ряда s = 1 + .

Выпишем несколько слагаемых: a₁ = ln u × x, a₂ = ln² u × , …, a_k = ln^k u ×

и найдем рекуррентное (повторяющееся) соотношение для вычисления значений слагаемых a_k+1 = a_k× ln u × x/(k+1) или a := a * ln(u) * x/k.

До входа в цикл установим начальные значения a := 1; s := a; v := x*ln(u), тогда программа вычисления суммы функционального ряда примет вид:

program p614;

const n = 20;

var x, u, v, s, a : real; k : integer;

Begin

read(u,x); a :=1; s := a; v := x*ln(u);

for k := 1 to n do begin a := a * v / k; s := s + a end;

writeln (‘u=’, u:5:3, ‘ x=’, x:5:3, ‘ s=’, s:5:3)

end.

Операторы цикла с предусловием и постусловием удобно применять при последовательном приближении искомых значений. Итерационные циклы (итерация – последовательное приближение) нельзя описывать оператором for, поскольку заранее невозможно определить их число повторений. В таких циклах вычисления повторяются до тех пор, пока выполняется, или наоборот, нарушится некоторое условие.

Пример 6.15 Вычислить сумму ряда s = с точностью до

10^-7. Определить номер члена ряда, при добавлении которого достигается заданная точность.

Ряд 1, - , , - , … является знакопеременным, поэтому добавление новых членов ряда при вычислении суммы необходимо продолжать до тех пор, пока |a|>=10^-7. Члены ряда можно вычислить рекуррентно:

|a_n-1| = ; |a_n| =

т.е. a_n = - a_n-1/k, а значит, k := k * (k +1); a := -a / k. Перед циклом установим начальные значения: n := 0; a := 1; s := a; в теле цикла n будем изменять на единицу n := n +1. Воспользуемся оператором while. Обратите внимание, что выбор условия в заголовке цикла влияет на последовательность операторов в теле цикла. Если заголовок цикла while abs(a) > 1.0E-07 do, то за оператором a := a / k должен следовать оператор s := s + a. Если заголовок while abs(a) >= 1.0E-07 do, то наоборот, s := s + a; a := a / k.

program p615;

const e = 1.0E-07;

var a, s : real; k, n : integer;

Begin

n := 0; a := 1; s := 1;

while abs(a)>e do

Begin

n := n +1; k := 2*n; k := k*(k+1);

a := - a / k; s := s+a

end;

writeln(s:7, n)

End.

Задание 6.6

1. Решите эту задачу с применением оператора repeat.

2. Найти сумму первых n членов ряда y = 1+ + + +…, где х – любое число.

3. Найти сумму первых n членов ряда y = 1+ + + +… при |х|<1.

4. Найти сумму ряда y = 1+ + + +… при |х|<1. Расчет продолжать до тех пор, пока приращение |y| будет больше заданной точности e, e<=x.

5. Найти сумму ряда y = 1+ - + -… при |х|<=1. Расчет продолжать до тех пор, пока приращение |y| будет больше заданной точности e, e<=x.

6. Найти сумму первых n членов ряда y = 1- + - +… при |х|>1.