Лекции по "Языкам и методам программирования" (PascalABC)

Лекция 4.

Алгоритмы, содержащие структурные операторы циклов.

В лекции рассматриваются следующие  вопросы:

1.Понятие цикла, тела цикла,  условия цикла.

2.Структура «Повторение с предусловием».

3.Структура «Повторение с постусловием».

4.Структура «Повторение с параметром».

5.Вложенные циклы.

 

1.Понятие цикла, тела  цикла, условия цикла.

Рассмотрим пример. Пусть нужно  накопать мешок картошки, используя  имеющееся ведро. Каковы при этом будут действия человека.

Начало.

1.Мешок наполнен до  верха ? Если нет выполнять действия 2 – 3, иначе перейти на конец.

2.Накопать ведро картошки.

3.Высыпать в мешок  и перейти к пункту 1.

Конец.

В этом примере действия 1, 2, 3 образуют цикл. В действии 1 ставится вопрос (некоторое  условие). В зависимости от ответа на этот вопрос действия 2,3 либо повторяются,  либо происходит переход на конец. Вопрос «Мешок наполнен до верха?» называется условием цикла. Действия 2 и 3 образуют тело цикла.

 

2. Структура «Повторение с предусловием»

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

Словами такую структуру можно  сформулировать так: «Пока условие цикла истинно, выполняется тело цикла». Поэтому такой цикл еще называют циклом ПОКА. Эти же слова определяют порядок работы такого цикла.

Это значит, что если условие цикла  принимает значение True, то выполняется тело цикла; если условие принимает значение False, то происходит выход из цикла. Поэтому, если с самого начала условие цикла принимает значение False, то тело цикла может не выполниться ни разу.

На языке Паскаль такая структура  записывается структурным оператором цикла WHILE:

While Логическое выражение DO тело цикла;

В этом операторе слова While (в переводе – пока), Do (в переводе – выполнять) служебные слова; логическое выражение может быть как простым так и сложным, тело цикла – это любые операторы языка Паскаль, в том числе и составной оператор.

Циклу ПОКА соответствует следующая структура блок-схем:

 

Задача 1. Деньги в сумме а руб. положены на счет в сберегательном банке. В конце каждого года насчитывается в% от той суммы, которая лежит на счету. Через сколько лет сумма станет больше с руб. , если проценты со счета не снимать?

Program a1;

Var i:Integer; a,b,c:Real;

Begin

  Writeln('Сколько денег  вносите на счет');

  Readln(a);

  Writeln('Сколько процентов начисляется');

  Readln(b);

  Writeln('Какую сумму нужно получить');

  Readln(c);

  i:=0;

  While a<=c do

     Begin

     i:=i+1;

     a:=a+a/100*b;

     End;

Writeln('Через ',i:2,' лет сумма будет >= ', c:8:2,'руб.');

End.

 

Задача 2. Числа Фибоначчи получают по следующему закону:

а₁=1, а₂=1, а_n=а_n-1+a_n-2. Получить n-ое число Фибоначчи.

 

Program a2;

Var n,a,b,c,k:LongInt;

Begin

   Writeln('Ввести номер числа');

   Readln(n);

   a:=1; b:=1; k:=2;

   While k<n do

      Begin

      c:=a+b;

      a:=b;

      b:=c;

      k:=k+1;

      End;

  If n<=2

     Then Writeln(n:3,'-oe число Фибоначчи=1')

     Else Writeln(n:3,'-oe число Фибоначчи=',c:7);

End.

 

Задача 3. Задано  целое число р. Выделить цифры этого числа, начиная с младшей цифры.

Решение. Будем нацело делить число р на 10 получая остаток от деления и частное. Остатки от деления будут цифрами, а частные – это исходное число без соответствующей цифры.

Program a3;

Var n,i,a:Integer; p:Longint;

Begin

Writeln('Ввести целое число ');

Readln(p);

Writeln('цифры числа ',p,' :');

While p>0 do

   Begin

   a:=p mod 10;

   Write(a:3);

   p:=p div 10;

   End;

End.

 

Задача 4 (задача о пиратах). 13 пиратов решили поделить поровну награбленные золотые монеты. Но, когда они разделили монеты на 13 равных кучек, осталось 8 монет. Затем 2 пирата погибли в бою, и при дележе монет на 11 равных кучек осталось 3 монеты. После того, как 3 пирата умерли от оспы, при дележе монет на 8 равных кучек, осталось 5 монет. Какое минимальное количество монет могло быть у пиратов?

Решение. Из условия задачи получаем:

Генерируем числа вида x=13i+8, I=1,2,3…Затем проверяем два условия   x mod 11 = 3  и  x mod 8 = 5. Если при некотором I эти условия выполняются, то x найдено. Для выхода из цикла, когда x найдено, вводим переменную p с начальным значением p=0.

Program a4;

Var p,i,x:LongInt;

Begin

p:=0;

i:=1;

While p=0 do

   Begin

   x:=13*i+8;

   If  x mod 11=3

      Then If x mod 8=5

               Then Begin

                    p:=1;

                    Writeln('у пиратов было',x,'  монет');

                        End;

   i:=i+1;

  End;

End.

 

Задача 5. Найти НОД(m,n), где m,n>0, используя операцию деления с остатком.

Решение. При решении используем следующий алгоритм: из двух чисел выбираем большее, из большего вычитаем меньшее и ставим его на место большего. Эту операцию продолжаем до тех пор, пока числа не станут равными. Например, имеем два числа

а=9              в=21

а=9              в=21-9=12

а=9              в=12-9=3

а=9-3=6      в=3

а=6-3=3      в=3

Числа стали равны. За НОД  исходных чисел можно взять любое  из полученных.

Program a5;

Var m,n,a,b,d:Integer;

Begin

Writeln('Ввести 2 целых числа ');

Readln(n,m);

a:=abs(m);

b:=abs(n);

While a<>b do If a>b Then a:=a-b Else b:=b-a;

Writeln('НОД(',m,',',n,')=',a);

End.

 

3. Структура «Повторение с постусловием»

Структура «Повторение с постусловием» называется так потому, что в этой циклической структуре сначала выполняется тело цикла, а затем проверяется истинность условия. Если условие принимает значение False, то опять выполняется тело цикла; а если условие принимает значение True, то происходит выход из цикла. Так как сначала выполняется тело цикла, а уже потом проверяется истинность условия, то в данном цикле тело цикла всегда выполнится хотя бы один раз.

Словами «Повторение с постусловием»  можно сформулировать так: «Тело  цикла выполняется до  истинности условия». Поэтому цикл с постусловием еще называют циклом «ДО».

Формат записи оператора цикла  с постусловием на языке Паскаль:

 

Repeat     Тело цикла    Until условие;

В данном структурном операторе  цикла слова Repeat (в переводе -  повторять), Until (в переводе – до) служебные слова, тело цикла – это любые операторы языка Паскаль, условие – это логическое выражение.

Циклу ДО соответствует следующая  структура блок-схем:

Задача 6. Вывести таблицу значений функции y=e^x+sin|x| на отрезке [a, b] с шагом h. Значении a, b, h вводятся с клавиатуры.

Program a6;

Var a,b,h,x,y:Real;

Begin

   Writeln('Ввести начало отрезка'); Readln(a);

   Writeln('Ввести конец отрезка');  Readln(b);

   Writeln('Ввести шаг изменения x');Readln(h);

   x:=a;

   Repeat

     y:=exp(x)+sin(abs(x));

     Writeln('x=',x:6:2,'  y=',y:8:2);

     x:=x+h;

     Until x>b;

End.

Все программы, которые можно создать  с помощью цикла с постусловием, можно создать с помощью цикла  с предусловием. А вот наоборот не всегда это можно сделать.

 

4. Структура «Повторение с параметром»

Данный цикл используется только тогда, когда заранее известно количество повторений тела цикла. Количество повторений можно задавать как промежуток между начальным и конечным значениями некоторой переменной, которая может изменять свое значение на 1. Эта переменная называется параметром (счетчиком). Тип параметра может быть либо целый, либо символьный, либо логический.

Формат записи цикла с известным  числом повторений на языке Паскаль:

For параметр:=начальное значение To конечное значение  Do Тело цикла;

Слова For (в переводе – для), To (в переводе – до), Do (в переводе – выполнять) служебные слова, параметр – это переменная простого стандартного типа, кроме вещественного, начальное значение и конечное значение – это константы, переменные и выражения того же типа, что и параметр.

Оператор For работает следующим образом. Сначала параметр принимает начальное значение. Если значение параметра меньше либо равно конечному значению, то выполняется тело цикла. Затем значение параметра увеличивается на 1. Если новое значение параметра меньше или равно конечному значению, то опять выполняется тело цикла. Когда значение параметра станет больше конечного значения, то тело цикла не выполняется, и управление переходит на оператор, который идет по программе далее, т.е. происходит выход из цикла.

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

Циклу с параметром соответствует  следующая структура блок-схем:

Если с самого начала конечное значение меньше начального значения, то тело цикла не выполнится ни разу.

Задача 7. Вычислить факториал целого числа n. N!=1*2*3*…*n.

Program a7;

Var i,n:Integer; p:LongInt;

Begin

   Writeln('Ввести значение n');Readln(n);

   p:=1;

   For i:=1 to n do p:=p*i;

   Writeln(n:4,'!=',p:10);

End.

 

Задача 8. Найти и вывести на печать все четырехразрядные числа abcd, для которых ab-cd=a+b+c+d (*), где все цифры a, b, c, d – различны.

Решение. Из условия (*) следует, что d=(9a-11c)/2. Поскольку d целое число, то 9a-11c должно быть четным числом. А это возможно, когда a и c имеют одинаковую четность. Отсюда следует, что a=c+2. Итак получаем, что d=9-c, a=c+2.

Program a8;

Var a,b,c,d,k,m,p,x:Integer;

Begin

k:=0;

For c:=1 to 7 do

   begin

   d:=9-c;

   a:=c+2;

   for b:=0 to 9 do

       If (b<>a) and (b<>c) and (b<>d)

           Then begin

                m:=10*a+b-10*c-d;

                p:=a+b+c+d;

                If m=p Then begin

                            x:=1000*a+100*b+10*c+d;

                            Write(x:5);

                            k:=k+1;

                            end;

                 end;

    end;

Writeln;

If k=0 Then Writeln('Таких чисел нет')

       else Writeln('Вариантов таких чисел=',k);

End.

 

В языке  Pascal параметр может уменьшаться на единицу. Тогда оператор будет иметь следующий формат записи:

For параметр:=начальное значение Downto конечное значение Do тело цикла;

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

Поэтому, если с самого начала конечное значение больше начального значения, то тело цикла не выполнится ни разу.

Этому циклу с параметром соответствует следующая структура блок-схем:

Задача 9. Дан отрезок натуральных чисел [a, b]. Найти сумму чисел этого отрезка, которые при делении на целое число х, которое вводится с клавиатуры, дают в остатке 3 или 8.

Program a9;

Var a,b,s,x,d,z:Integer;

Begin

   Writeln('Ввести концы отрезка');Readln(a,b);

   Writeln('Ввести число, на которое будем делить');

   Readln(x);   

   s:=0;

   For d:=a to b do

      Begin

      z:=d mod x;

      If (z=3) or (z=8) Then s:=s+d;

      End;

   Writeln('Summa =',s:6);

End.

 

 

5. Вложенные циклы.

Если один цикл находится  внутри другого цикла, то он является вложенным. Рассмотрим это на примере.

Задача 10. Ответить на вопрос, существуют ли такие двузначные целые числа ab  и cd , что их произведение есть четырехзначное число с теми цифрами, что и исходные числа, т.е. ab*cd=abcd .

Решение. ab и  cd – это двузначные числа, которые могут изменяться независимо друг от друга от 10 до 99. Чтобы получить четырехзначное число, записанное теми же цифрами, что и числа ab и  cd, нужно найти их сумму в виде:   100*ab+cd. В самом деле, пусть число ab=34,  cd= 92. Вычислим    100*ab+cd=100*34+92=3400+92=3492.

Генерируем дважды двузначные числа от 10 до 99 и проверяем выполнение заданного условия, чтобы произведение чисел равнялось четырехзначному числу с теми же цифрами. Введем счетчик, который будет считать, сколько раз выполнится приведенное условие. Сначала начальное значение счетчика берем равным 0. Если условие выполнится, то значение счетчика увеличим на 1.

 

Program a10;

Var ab,cd,k:Integer;

Begin

k:=0;{начальное значение счетчика}

For ab:=10 to 99 do {перебор всех чисел ab}

    for cd:=10 to 99 do {перебор всех чисел cd}

       If ab*cd=100*ab+cd {условие: произведение = четырехзначному числу}

           Then begin

                Write(ab:5, 'и', cd:5); {вывод чисел удовлетворяющих условию}

                k:=k+1; {увеличение счетчика на 1}

                end;

Writeln;

If k=0

  Then Writeln('Таких чисел нет')

  else Writeln('Всего вариантов=',k);

End.

 

В этой задаче цикл по переменной cd вложен в цикл по переменной ab. Это хорошо видно из приведенной ниже блок-схемы.

 

 

 

 

 

Вопросы для самоконтроля.

Почему цикл называется циклом с  предусловием?

Как записывается оператор цикла с  предусловием?

Как словами можно сформулировать цикл с предусловием?

Что является условием в операторе  цикла с предусловием?

Что является телом цикла в операторе  цикла с предусловием?

Графическое представление цикла  с предусловием.