Презентация "Циклические алгоритмы" по информатике – проект, доклад

Лекция №5

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

План лекции

Оператор безусловного перехода Повторяющиеся действия Циклы с предусловием Циклы с постусловием Циклы со счетчиком Сложноциклические структуры Решение задач.

Оператор безусловного перехода

Оператор безусловного перехода – goto. goto <метка>; Для его использования, необходимо описать метки в разделе описаний, на которые будет осуществляться переход. Label metka1, metka2; Меткой может быть число от 1 до 9999, либо последовательность латинских букв и цифр.

Оператор перехода предназначен для указания того, что выполнение программы должно продолжаться с точки программы, обозначенной меткой, значение которой стоит в операторе перехода. Метка в тексте программы располагается непосредственно перед помеченным оператором и отделяется от него двоеточием. Пример: ….. goto m1; ….. ….. m1: write (a,b); ….

Пример использования оператора безусловного перехода: Label Var m1, m2; a,b,c : real; Var Begin a,b,c : real; read(a,b); Begin if b=0 then read (a,b); write (‘На 0 делить нельзя!’) if b=0 then else goto m1; begin c:=a/b; c:=a/b; write (c); write (c); goto m2; end m1 : write (‘На 0 делить нельзя !’); End. m2: End. Из пример очевидна неэффективность использования оператора безусловного перехода.

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

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

Повторяющиеся действия

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

Задача 1. Найти максимальное число из десяти положительных чисел. Решение задачи можно построить по следующему алгоритму: 1) i=0 2) p=0 3) задать очередное значение x 4) если x>p, то p=x 5) i=i+1 6) если i<10 перейти к пункту 3. 7) выдать значение p

Label m1; Var p, i, x : integer; Begin p:=0; i:=0; m1 : read(x); if x>p then p:=x; inc(i); if i<10 then goto m1; writeln (p); End.

начало x P= 0; I=0 P x>P I<10 P=x I=I+1 конец + -

В данном примере продемонстрированы повторяющиеся действия (циклические, цикл). Телом цикла называют те операторы, которые повторяются. … m1 : read(x); if x>p then p:=x; inc(i); if i<10 then goto m1; … Управляющей переменной цикла называют переменную, от которой зависит количество повторений. В нашем примере, управляющей переменной цикла является переменная i.

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

На языке Паскаль различают следующие операторы цикла: Циклы с предусловием ( while ); Циклы с постусловием ( repeat … until ); Циклы со счетчиком ( for ).

Циклы с предусловием

While – это оператор цикла итеративного типа с предусловием, так как в нем анализ конца цикла производится до выполнения операторов тела цикла. Он используется, когда количество повторений операторов тела цикла заранее неизвестно и определяется в процессе выполнения цикла. По операторам continue и break можно перейти на анализ условия конца цикла или первый оператор после цикла соответственно. while <логическое выражение> do begin <тело цикла, состоящее из группы операторов> end; Таким образом, организовывать повторяющиеся (циклические) действия в программе будет более правильно без использования операторов безусловного перехода.

while B(x) do S; где B(x) – логическое выражение , в том случае, когда это выражение будет иметь значение Ложь, произойдет выход из цикла; S – один оператор, простой или составной; он должен включать операторы тела цикла, в том числе оператор изменения операторов логического выражения B(x)

Условие при котором выполняются итерации цикла

Тело цикла

Задача 2. Лист бумаги делят пополам, полученную половину снова делят пополам и т.д. Определить, какое количество делений потребуется, для того чтобы получить частицу размером с атом. Начальная масса листа 1 грамм, масса атома 10-24 грамм. Var m,ma : real; k :integer; Begin k:=0; m:=1; ma:=1e-24; while m>ma do begin m:=m/2; inc (k); end; writeln (k) End.

k m>10-24 m=1 k=0 m=m/2 k=k+1

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

Задача 2. Определить значение суммы S=1/x1+1/x2+…1/xn, где n – количество слагаемых. Var s, x : real; i, n :integer; Begin i:=0; s:=0; read (n); while i

Var s, x : real; i, n :integer; Begin i:=0; s:=0; read (n); while i

Программа завершит выполнение с сообщением об ошибке (Деление на 0).

Var s, x : real; i, n :integer; Begin i:=0; s:=0; read (n); while i

В случае использования оператора break исполнение программы завершится, т.е. произойдет выход из цикла и вывод накопленной суммы до введенного значения x=0. В случае использования оператора continue произойдет переход на выполнение первого оператора тела цикла, и как следствие будет пропущены операторы стоящие после continue в теле цикла. Таким образом будет пропущена операция деления на 0. Операторы break и continue могут использоваться так же и в других циклах : циклах с постусловием и циклах со счетчиком.

Циклы с постусловием

Repeat … until – это оператор цикла итеративного типа с постусловием, так как в нем анализ конца цикла производится после выполнения операторов тела цикла. Он используется, когда количество повторений операторов тела цикла заранее неизвестно и определяется в процессе выполнения цикла. Операторы тела цикла выполняются хотя бы 1 раз. repeat <операторы тела цикла> until <логическое выражение>

Условие завершения цикла

repeat S; until B(x); где B(x) – логическое выражение, при истинности которого происходит выход из цикла; S – один или несколько операторов тела цикла.

Задача 3. Дано x>1. Вычислить и вывести степени x. Вычисления производятся до тех пор, пока вычисляемое значение не станет более 108 Var k,x : integer; y : longint; Begin read (x); k:=0; y:=1; repeat y:=y*x; inc (k); write (x,’ в степени ’,k,’ есть ‘,y); until y>1e8; End.

x,k,y y>108 y=y*x k=0 ; y=1 k=k+1

Сравнение циклов с постусловием и предусловием

Есть небольшое отличие в организации цикла repeat по сравнению с while: для выполнения в цикле repeat нескольких операторов не следует помещать эти операторы в операторные скобки begin ... end. Зарезервированные слова repeat и until действуют как операторные скобки.

Конструкция repeat ... until работает аналогично циклу while. Различие заключается в том, что цикл while проверяет условие до выполнения действий, в то время как repeat проверяет условие после выполнения действий. это гарантирует хотя бы одно выполнение действий до завершения цикла. Так же истинность логического выражения в операторе repeat … until свидетельствует о завершении цикла, тогда как в операторе while – выполнение тела цикла.

Циклы со счетчиком

Циклы со счетчиком составляют такую конструкцию, в которой выполнение исполнительной части должно повторяться заранее определенное число раз. Циклы со счетчиком используются довольно часто, и поэтому в языке Паскаль для этих целей имеется специальная конструкция. for <управл. переменная цикла> :=<нач. зн-е> to/downto <кон. зн-е> do <один оператор, являющийся телом цикла> to – используется при шаге изменение управляющей переменной цикла равном 1. downto – используется при шаге изменение управляющей переменной цикла равном -1.

Примеры : for x:=1 to 10 do begin …. end; for y:=100 downto 10 do begin …. end;

Задача 4. Найти максимальное число из десяти положительных чисел. Var p, i, x : integer; Begin p:=0; for i:=1 to 10 do begin read (x); if x>p then p:=x; end; writeln(p); End.

P= 0 i=1;10

Управляющая переменная цикла со счетчиком не может быть вещественного типа. В тех случаях, когда тело цикла выполняется заданное, известное количество итераций, но шаг цикла отличен от 1 или -1, то используют циклы while, repeat … until. Пример: … x:=0; repeat x:=x+2; … until x=10; …

Ситуации «зацикливания»

Рассмотрим несколько примеров циклов : for i:=100 to 10 do 2) while true do …. …. 3) x=5; 4) y:=10; repeat while y>5 do inc (x); begin … … until x<2; y:=y+2; end; Такие циклы будут выполняться, до тех пор пока не будет прервано исполнение такой «зацикленной» программы. Эту ситуацию можно разрешить используя оператор break в теле цикла. Однако всегда следует следить за тем, чтобы циклы завершались корректно, т.е. в циклах были установлены такие параметры, которые бы не приводили к «зацикливанию».

Сложноциклические структуры

Циклы могут быть простые и вложенные (кратные, циклы в цикле). Для решения многих задач так же используют структуру вложенных циклов, которую и называют сложноциклической. Вложенными могут быть циклы любых типов : for, while, repeat … until. Пример : … for x:=1 to 10 do begin …. for y:=1 to 5 do begin … end; … end; …

i=NI;KI

Операторы тела цикла 1 уровня

J=NJ;KJ

Операторы тела цикла 2 уровня

K=NK;KK

Операторы тела цикла 3 уровня

3 2 1

i=1;N Bs=0 j=1;5 Bs=Bs+B G=Sbg/N N Sbg=0 B Sbg=Sbg+Bs Bs G

Задача 5. Подсчитать рейтинг (суммарный балл) каждого студента по информатике при решении 5 задач. Определить средний балл группы из N студентов.

Var i, j, n: integer; b, bs, sbg, g: real; Begin writeln (‘Введите количество учеников : ‘); read (n); sbg:=0; for i:=1 to n do begin writeln (‘ Введите баллы ‘,i ,-го ученика’); bs:=0; for j:=1 to 5 do begin printf (‘ Количество баллов за решение ‘,j, ‘–й задачи: ‘); read (b); bs:=bs+b; end;

writeln (‘----------------------------------------------------------------’); writeln (‘ Суммарный балл ‘, i , ‘-го ученика равен ‘ ,bs:6:2); writeln (‘----------------------------------------------------------------’); sbg:=sbg+bs; end; g:=sbg/n; writeln (‘*************************************’); writeln (‘ Средний балл группы равен ‘,g:6:2,’ балла’); writeln (‘*************************************’); End.

Решение задач

Задача 6. Вычислить , где xi - i-тый член суммы. Var s, i, n : integer; Begin read (n); s:=0; for i:=1 to n do begin read (x); s:=s+x; end; write (s); End.

Задача 7. Вычислить знакопеременную сумму Var i, p : integer; s: real; Begin s:=0; p:=-1; for i:=1 to 20 do begin p:=p*(-1); s:=s+p/i; end; write (s); End.

p=p*(-1) S=0 P=-1 s=s+p/i i=1;20

Задача 8. Вычислить Var p, i, n : integer; Begin read (n); p:=1; for i:=1 to n do begin read (x); p:=p*x; end; write (p); End.

Задача 9. Вычислить Var i, j : integer; p: real; Begin p:=1; j:=23; for i:=1 to 12 do begin p:=p* i / j; j:=j-2; end; write (p); End.

p=p*i/j J=23 j=j-2 i=1;12 P=1

Задача 10. Напишите программу табулирования функции для получения таблицы функции y=x*sin(x) при изменении х на отрезке от - π до π с шагом π /5 . Var x,y: real; Begin x:=-3.14; repeat y:=x*sin(x); writeln (x:6:2, ‘ | ‘ , y:6:2); x:=x+pi/5; until x>3.14; End.

y=x*sin x x,y x=- π; π ; π /5

Задача 11. Вычислить приближенно площадь фигуры, ограниченной функцией y=x2 и прямой y=25, разбивая отрезок изменения х на 10 частей и суммируя площади прямоугольников с основаниями равными 1/10 отрезка изменения х, и высотой, определяемой значением функции в середине основания.

y 0 y=x2 y=25 y= 25 x=±5 y=x2 

Т.к. высота определяется в середине основания прямо- угольника, тогда x должен изменяться от -4.5 до 4.5 вследствие того, что h=1 h=|-5 – 5|/10=1 Высота прямоугольника L=25-x2 Площадь прямоугольника P=h*L=(25-x2)*1

Задача 11. Вычислить приближенно площадь фигуры, ограниченной функцией y=x2 и прямой y=25, разбивая отрезок изменения х на 10 частей и суммируя площади прямоугольников с основаниями равными 1/10 отрезка изменения х, и высотой, определяемой значением функции в середине основания. Var s, x, p : real; Begin s:=0; x:=-4.5; while x<=4.5 do begin p:=25-sqr(x); s:=s+p; x:=x+1; end; writeln (s); End.

p=(25-x2 )*1 S=0 S=S+p x=-4.5;4.5;1

Задача 12. Одноклеточная амеба каждые 3 часа делится на 2 клетки. Определить сколько клеток будет через 3,6,9,12, ... , 24 часа. Var a,t : integer; Begin t:=0; a:=1; while t<=24 do begin t:=t+3; a:=a*2; writeln (‘через ‘,t,’час. будет ‘,a,’амеб’) ; end; End.

T=T+3 A=1 A=A*2 T<=24 T=0 T, A

Задача 13. Начав тренировки, спортсмен в первый день пробежал 5 км. Каждый следующий день он увеличивал дневную норму на 10% от нормы предыдущего дня. Через сколько дней он будет пробегать в день более 20 км. ? Var d : word; s : real; Begin d:=1; s:=5; repeat inc (d); s:=s*1.1; until s>20; writeln (d) ; End.

D=D+1 S=5 S=S*1.1 S>20 D=1 D

Задача 14. Определить m – количество трехзначных натуральных чисел, сумма цифр которых равна n(1

Задача 15. Вычислить Var i, j, n : integer; p, s : real; Begin read (n); p:=1; for i:=1 to n do begin s:=0; for j:= 1 to 2*n do s:=s+i/(2*i*i+1); p:=p*s; end; writeln (p) ; End.

j=1;2*N s=s+i/(2i2+1) p=1 p=p*s