Цели:

  1. Закрепить знания по использованию различных типов циклов;
  2. Получить навыки решения алгоритмов с вложенными циклами;
  3. Закрепить навыки написания алгоритмов с повторениями;
  4. Осуществить промежуточный контроль знаний.

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

Рассмотрим несколько примеров:

|| Дано натуральное число S. Требуется написать программу для нахождения всех прямоугольников, площадь которых равна S и стороны выражены натуральными числами.


                program zadacha4_6;                                           // название программы
                var
                    s, a, b: longint;                                         // описание переменных
                Begin                                                         // начало
                    writeln('Введите s');                                     // вывод сообщения
                    readln(s);                                                // ввод s
                    for a:=1 to s do                                          // запускаем арифметический цикл с параметром FOR для i от 1 до s делать
                        for b:=1 to s do                                      // запускаем внутри этого цикла вложенный арифметический цикл с параметром FOR для i от 1 до s делать
                            if a*b=s then writeln ('стороны ',a,' и ',b);     // проверяем условие, если a*b=s, то выводим сообщение со сторонами прямоугольников
                End.                                                          // конец
            

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

|| Даны натуральные числа n, m. Получить все натуральные числа, меньшие n, сумма квадратов цифр, которых равна m.


                program zadacha4_7;                                       // название программы
                var
                    n, m, i, a, sum, cif: longint;                        // описание переменных
                Begin                                                     // начало
                    writeln('введите n и m');                             // вывод сообщения
                    readln(n, m);                                         // ввод n, m
                    for i:=1 to n do                                      // запускаем арифметический цикл с параметром FOR для i от 1 до n делать
                        begin                                             // начало тела основного цикла
                            a:=i;                                         // присваиваем переменной a значение i
                            sum:=0;                                       // обнуляем переменную sum
                            while a>0 do                                  // запускаем вложенный цикл с предусловием, пока a>0 делать
                                begin                                     // начало тела вложенного цикла
                                    cif:=a mod 10;                        // присваиваем переменной cif значение остатка от деления на 10
                                    sum:=sum+sqr(cif);                    // находим сумму квадратов цифр
                                    a:=a div 10;                          // присваиваем переменной a значение целой части при делении на 10
                                end;                                      // конец тела вложенного цикла
                            if sum=m then write(i,' ');                   // проверяем условие, если сумма равна m, тогда выводим это число
                        end;                                              // конец тела основного цикла
                End.                                                      // конец
            

|| Найти все решения заданного числового ребуса. Каждой букве соответствует некоторая цифра. Причём одинаковым буквам соответствуют одинаковые цифры, разным буквам - разные цифры.

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


                program zadacha4_8a;                                                        // название программы
                var
                    k, t, o, kto, kot, tok: longint;                                        // описание переменных
                Begin                                                                       // начало
                    for k:=0 to 9 do                                                        // запускаем арифметический цикл с параметром FOR для k от 0 до 9 делать
                        for t:=0 to 9 do                                                    // запускаем вложенный арифметический цикл с параметром FOR для t от 0 до 9 делать
                            for o:=0 to 9 do                                                // запускаем вложенный арифметический цикл с параметром FOR для o от 0 до 9 делать
                                begin                                                       // начало тела цикла
                                    kto:=k*100+t*10+o;                                      // присваиваем переменной kto значение k*100+t*10+o
                                    kot:=k*100+o*10+t;                                      // присваиваем переменной kot значение k*100+o*10+t
                                    tok:=t*100+o*10+k;                                      // присваиваем переменной tok значение t*100+o*10+k
                                    if (k<>t) and (k<>o) and (t<>o) and (kto+kot=tok)       // проверяем условие, если k<>t и k<>o и t<>o и kto+kot=tok,
                                        then writeln(kto,'+',kot,'=',tok);                  // тогда выводим результат
                                end;                                                        // конец тела цикла
                End.                                                                        // конец
            

В данном алгоритме тело цикла выполнялось 10∙10∙10=1000 раз. (будем говорить сложность алгоритма = 1000)

Если же для решения более сложных ребусов потребуется написать 8-10 вложенных циклов, то такой полный перебор будет работать достаточно долго.

Можно немного упростить данный алгоритм, если увидеть, что 1≤k≤4, t≥2.


                for k:=1 to 4 do
                    for t:=2 to 9 do
                        for o:=0 to 9 do
            

Теперь сложность алгоритма 4∙8∙10=320. Простое косметическое исправление дало увеличение скорости в 3 раза.

Но и данный алгоритм не является оптимальным. Посмотрите, при k=2 и t=2 программа переберёт все 10 вариантов o. В таких случаях, когда k=t цикл по o вообще необходимо не выполнять.

Назовём такой метод - контролируемый перебор.


                program zadacha4_8b;                                                        // название программы
                var
                    k, t, o, kto, kot, tok: longint;                                        // описание переменных
                Begin                                                                       // начало
                    for k:=1 to 4 do                                                        // запускаем арифметический цикл с параметром FOR для k от 1 до 4 делать
                        for t:=2 to 9 do                                                    // запускаем вложенный арифметический цикл с параметром FOR для t от 2 до 9 делать
                            if k<>t then                                                    // проверяем условие, если k<>t, тогда
                                for o:=0 to 9 do                                            // запускаем вложенный арифметический цикл с параметром FOR для o от 0 до 9 делать
                            if (k<>o) and (t<>o) then                                       // проверяем условие, если k<>o и t<>o, тогда
                                begin
                                    kto:=k*100+t*10+o;                                      // присваиваем переменной kto значение k*100+t*10+o
                                    kot:=k*100+o*10+t;                                      // присваиваем переменной kot значение k*100+o*10+t
                                    tok:=t*100+o*10+k;                                      // присваиваем переменной tok значение t*100+o*10+k
                                    if kto+kot=tok then writeln(kto,'+',kot,'=',tok);       // проверяем условие, если kto+kot=tok, тогда выводим результат
                                end;
                End.                                                                        // конец
            

Вопросы для повторения:

  1. Для чего предназначен оператор цикла?
  2. Какие циклы существуют в языке Pascal?
  3. Какой формат записи имеет оператор FOR?
  4. Как работает оператор FOR?
  5. В каких случаях применяется оператор FOR?
  6. Сколько раз будет выполнен цикл, и чему будет равна переменная S после выполнения:
    
                            s:=0;
                            n=6;
                            for i:=3 to n do
                                s:=s+i;
                        
  7. Как в теле цикла выполнить несколько операторов?
  8. Какой формат записи имеют циклы WHILE и REPEAT?
  9. В каких случаях удобно применять эти циклы?
  10. Чем отличается цикл WHILE от цикла REPEAT?
  11. Будет ли остановлено выполнение данного цикла? Почему?
    
                            s:=0;
                            i:=1;
                            while i<=4 do
                                s:=s+i;
                        
  12. Может ли во вложенных циклах использоваться одна и та же переменная, например, i?
  13. Можно ли вкладывать друг в друга различные циклы: FOR в WHILE или REPEAT в FOR?

Задания для самостоятельной работы:

  1. Старинная задача. Сколько можно купить быков, коров и телят, если бык стоит 10 рублей, корова – 5 рублей, телёнок – полтинник (0,5 рубля), при условии, что на 100 рублей надо купить 100 голов скота.
  2. Задано натуральное n. Для всех чисел от 1 до n найти сумму чётных делителей.
  3. Найти все двузначные числа, которые содержат цифру N.
  4. Написать программу поиска двузначных чисел, удовлетворяющих следующему условию: если к сумме цифр числа прибавить квадрат этой суммы, то получится само число.
  5. Написать программу поиска трёхзначных чисел, квадрат которых оканчивается тремя цифрами, составляющими исходное число.
  6. Написать программу поиска четырёхзначного числа, которое при делении на C даёт в остатке B, а при делении на B даёт в остатке D.
  7. Найти сумму целых положительных чисел из промежутка от А до В, кратных k (значения переменных А и В вводятся с клавиатуры).
  8. Найти сумму целых положительных чисел, больших A, меньших B, кратных 3 и заканчивающихся на 2, 4 или 8.
  9. В трёхзначном числе зачеркнули старшую цифру, когда полученное двузначное число умножили на 7, то получили данное число. Найти это число.
  10. Сумма цифр трёхзначного числа кратна 7, само число также делится на 7. Найти все такие числа.
  11. Среди четырёхзначных чисел выбрать те, у которых все четыре цифры различны.
  12. В 1626 году индейцы продали остров Манхеттен за 20$. Если бы эти деньги были помещены в банк на текущий счёт и ежегодный прирост составил k%, то какова была бы сумма в текущем году?
  13. Найти минимальное число, большее N, которое нацело делится на K (K, N - натуральные числа).
  14. Выяснить, сколько раз в натуральном числе встречается его максимальная цифра (Например, ввод 4423, вывод 2 раза; ввод 9077, вывод 1 раз).
  15. Стороны прямоугольника заданы натуральными числами M и N. Составить программу, которая будет находить, на сколько квадратов, стороны которых выражены натуральными числами, можно разрезать данный прямоугольник, если от него каждый раз отрезается квадрат максимально возможной площади.