Задачи на вложенные циклы

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

1. for — цикл с параметром.
2. while — цикл с предусловием.
3. repeat/until — цикл с постусловием.

Основная идея использования вложенных циклов

Основная идея использования вложенных циклов состоит в том, что даже когда некий процесс, требует цикла — повтора действий (т.н. “внешний цикл”), то даже внутри отдельного действия можно запустить свой цикл (т.н. “внутренний” или “вложенный цикл”) для решения какой-то “местной” задачи.

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

Графическое представление вложенных циклов

Работу циклов также можно сравнить с вращением связанных шестерёнок разного размера:

— внешний цикл это как бы большая шестерёнка, за один свой оборот (виток цикла), внешний цикл заставляет вращаться вложенный цикл (меньшую шестерёнку) несколько раз.

Такая иллюстрация точна в случае, если число повторов вложенного цикла не зависит от того какой именно (1-ый, n-ый или иной) виток делает внешний цикл, а так бывает не всегда. Почему выясним, рассматривая примеры ниже.

Примеры кода решений задач с вложенными циклами

Пример №1.1: Repeat/until + For: работа с пользователем до его указания на завершение программы

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

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

В качестве конкретного пример рассмотрим решение задачи:

Пользователь вводит целые положительные числа, большие $5$. Пока он не введёт число $22$ в ответ на каждое введённое число выводите все целые числа от $1$ до этого числа, если же пользователь ввёл ноль, то объявите о завершении работы программы.

Решение:

var a,i:integer;
begin
repeat // внешний цикл
writeln(‘vvedite chislo >5:’);
readln(a);

for i:=1 to a do // (вложенный цикл) выводим все числа до a
write(i, ‘ ‘);

writeln(); // перенос строки

until (a = 22); // конец тела внешнего цикла

writeln(‘zaversheno!’);
readln();
end.

Прокомментируем это решение:

1. В качестве внешнего цикла мы выбрали repeat/until, чтобы проверять условие уже после ввода значения пользователем.
2. В качестве внутреннего цикла мы выбрали for — ведь каждый раз будет известно число, до которого надо выводить меньшие числа. Можно было бы использовать и любой другой цикл, но for в таких случаях использовать грамотнее и красивее.
3. минусом выбора repeat/until внешним циклом является то, что эта программа, в случае если пользователь введёт число $22$, все равно выведет ряд чисел, а только потом завершится.

Последний пункт вызывает желание (да-да, программирование должно вас увлекать 😉 переписать код так, чтобы в случае, если пользователь ввёл $22$ ряд чисел не выводился.

Пример №1.2 (продолжение): While + For: работа с пользователем до его указания на завершение программы

Это пример является продолжением предыдущего и одновременной иллюстрацией ситуации, где цикл For вложен в While:

var a,i:integer;
begin

writeln(‘vvedite chislo >5:’);
readln(a);

while (a <> 22) do
begin // начало тела внешнего цикла

for i:=1 to a do // (вложенный цикл) выводим все числа до a
write(i, ‘ ‘);

writeln(); // перенос строки

writeln(‘vvedite chislo >5:’); // очередной раз запрашиваем число в цикле
readln(a);

end; // конец тела внешнего цикла

writeln(‘zaversheno!’);
readln();
end.

Как работает эта программа:

1. Сначала, ещё до цикла мы просим пользователя ввести число первый раз, если это число = 22, то цикл вообще не начнётся и программа будет завершена без вывода ряда.
2. Если пользователь вводит число не равное 22, то цикл начнётся, так как число уже известно, то в витке цикла мы сначала выведем значения до введённого числа, а только потом в конце витка запросим очередное число.

Пример №2 — вывод таблицы умножения

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

1. есть какой-то главный (внешний) цикл, тело которого должно решить задачу вывода на экран очередной строки (ну и расчета значений, которые нужно выводить)
2. но задача в вывода очередной строки в теле внешнего цикла, решается размещением в этом теле ещё одного вложенного цикла, который, например, формирует эту очередную строку из неких фрагментов, например символов или групп символов.

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

Рассмотрим решение задачи:

Вывести на экран таблицу умножения чисел от 1 до 9.

Решение (for в for):

var i, j: integer;
begin
for i := 1 to 9 do // цикл по строкам таблицы, счетчик как левый множитель
begin
for j := 1 to 9 do // выводим равенства очередной строки, счётчик как правый множитель
write(i, ‘*’, j, ‘=’, i*j, ‘ ‘);
writeln(); // переносим строку
end;

readln();
end.

Конечно, в качестве внешнего цикла можно было бы использовать любую другую из оставшихся двух конструкцию, например, давайте перепишем это решение используя вложение for в while:

var i, j: integer;
begin
i := 1; // начальное значение для счетчика внешнего цикла
while (i <= 9) do // цикл по строкам таблицы, счетчик как левый множитель
begin

for j := 1 to 9 do // выводим равенства очередной строки, счётчик как правый множитель
write(i, ‘*’, j, ‘=’, i*j, ‘ ‘);
writeln(); // переносим строку

i:=i+1; // увеличиваем значение счетчика внешнего цикла
end;

readln();
end.

Или даже while в repeat-until:

var i, j: integer;
begin
i := 1; // начальное значение для счетчика внешнего цикла

repeat // начало тела внешнего цикла

j := 1; // сбрасываем значение счетчика внутреннего цикла в единицу (чтобы он повторился как и предыдущий раз), или если речь идёт о первом витке, то это действие можно назвать заданием начального значения счетчика
while (j<=9) do // выводим равенства очередной строки, счётчик как правый множитель
begin
write(i, ‘*’, j, ‘=’, i*j, ‘ ‘);
j:=j+1; // увеличиваем значение счетчика внутреннего цикла
end;

writeln(); // переносим строку
i:=i+1; // увеличиваем значение счетчика внешнего цикла

until (i > 9); // проверка условия выхода из внешнего цикла и конец его тела

readln();
end.

Задачи для самостоятельного решения

1. Выведите на экран таблицу умножения используя только циклы вида repeat/until.
2. Выведите на экран таблицу умножения используя только циклы вида while.
3. Выведите на экран таблицу умножения используя один цикл while и один repeat-until .
4. Пользователь вводит числа до тех пор пока не введёт число меньшее $1$. В ответ на каждое введённое им число выводите на экран все нечетные числа от 1 до это числа, при этом делящиеся на 5. Если же пользователь ввел число меньшее $1$, то завершите программу.
5. Пользователь вводит первое целое число-ограничитель $m$. А затем начинает вводить целые числа по одному, пока не введёт число большее числа-ограничителя.
   Если очередное целое число больше $1$, то в ответ на каждое такое число программа должна выводить все целые числа от единицы до этого числа.

   Примечание: это задача на вложенные циклы, в качестве внешнего надо использовать while, а в качестве внутреннего можно использовать или for или while.

6. Пользователь вводит целое положительное число, если оно не соответствует критериям (то есть не является положительным), выведете сообщение об ошибке, в противном случае выведете на экран все числа от 1 до введённого пользователем.
7. Модифицируйте предыдущую задачу так, чтобы в случае, если число удовлетворяет требованиям (целое, положительное), то на экран выводились четные числа.
8. Выведете на экран числа от 1 до 5 два раза с помощью вложенных циклов. Так чтобы в консоли было:
   1 2 3 4 5
   1 2 3 4 5
9. M раз выведете на экран числа от 1 до N с помощью вложенных циклов. Так чтобы в консоли было:
   $
   left.
   begin{array}{ccc}
   1 & … & N \
   1 & … & N \
   end{array}
   right} text{M раз}
   $
10. Модифицируйте предыдущую задачу так, чтобы в каждой чётной (той, у которой номер чётный) строке выводилось N символов, а в каждой нечетной N/2 символов (сделайте проверку того, что $N/2$ больше нуля)
11. Пользователь вводит числа до тех пор пока им не будет передан ноль. В ответ на каждое число программа должна сообщать чётное оно или нет.
12. Пользователь вводит четное целое число (если нечетное сообщите об ошибке). Делите это число в цикле на $2$ до тех пор пока оно делится, выводя каждый промежуточный результат, например для $12$ в консоли получим:
    6
    3

    А для 8:

    4
    2
    1

13. Пользователь вводит два целых числа $M$ и $N$, если $M$ четное, делайте то же, что и в предыдущей задаче, а если нечётное, то умножайте $M$ в цикле на $3$ до тех пор пока результат не станет больше $N$ (и выводите каждый из промежуточных результатов умножения на экран), например для:
    M := 3;
    N := 15;

    Получим:

    9
    27

14. С помощью вложенных циклов выведите на экран таблицу умножения числе от 1 до 9, начнётся она как-то так:
    1×1 = 1
    1×2 = 2
    ……
15. С помощью вложенных циклов выведите на экран таблицу деления чисел от 1 до 9.
16. Пользователь вводит целое положительное число $N$, если оно не соответствует критериям (то есть не является положительным), выведете сообщение об ошибке, в противном случае выведите на экран все числа последовательности, не большие $N$, сформированной следующим образом:
    8 10 3 12 14 3 16 18 3 20 22 3 и т.д.

    — то есть всё начинается с восьмерки, затем число увеличивается на 2, затем выводит тройка и ещё пара увеличенных на 2 чисел и т.д.

17. Модифицируйте решение предыдущей задачи. так чтобы пользователь вводил второе число $M$, которое отвечало бы за длину возрастающего фрагмента, например для $M=4$:
    $ underbrace{8 ;10 ;12 ;14}_{text{четыре числа}} ;3 underbrace{;16 ;18 ;20 ;22}_{text{четыре числа}} ;3 ; …. ;3 ;…. ;text{и т.д.} $

    Заметьте. что в предыдущей задаче $M$ было зафиксировано $=2$:
    $ underbrace{8 ;10}_{text{два числа}} ;3 underbrace{;14 ;16}_{text{два числа}} ;3 ; …. ;3 ;…. ;text{и т.д.} $

18. Модифицируйте решение предыдущей задачи, так, чтобы длина возрастающего фрагмента каждый раз увеличивалась на единицу (начиная с двух):
    $underbrace{; 8 ;10}_{text{два числа}} ;3; underbrace{10 ;12 ;14 }_{text{три числа}} ;3; underbrace{;16 ;18 ;20 ;22}_{text{четыре числа}} ;3 ; …. ;3 ;…. ;text{и т.д.} $

    ПРИМЕЧАНИЕ: эту задачу можно решить, как вложенными циклами, так и вообще одним циклом (что более изящно), при этом решение одним циклом можно сделать, как используя делимость нацело (для определения момента вывода тройки), так и не используя.
    Решите всеми тремя способами.

19. Пользователь передает целое положительное число $N$, выведете на экран последовательность от $1$ до $N$ “ёлочкой”, например для $N = 17$:
    1
    2 3
    4 5 6
    7 8 9 10
    11 12 13 14
    15 16 17

    ПРИМЕЧАНИЕ: эту задачу можно решить, как вложенными циклами, так и вообще одним циклом (что более изящно).
    Решите указанными двумя способами.

20. Модифицируйте предыдущий вывод “ёлочкой” так, чтобы в каждой нечетной строке выводились только четные числа, а в каждой четной только нечетные, например для $N = 17$:
    3
    4 6
    7 9
    12 14
    15 17
21. Пользователь передает целые положительные число $N$ и $M$, выведете на экран последовательность от $1$ до $N$, так чтобы ширина “ёлочки” увеличивалась до $M$ чисел, то уменьшалась до $1$. Например, для $M = 3$ и $N = 25$ получим:
    $
    1; \
    2; 3; \
    4; 5; 6;;;;;;;;; text{–максимум три числа} \
    7; 5; \
    9; \
    10; 17; \
    18; 19; 20;;;;;;; text{–снова три числа} \
    21; 22; \
    23; \
    24; 25;…..
    $
22. Пользователь передает целые положительные число $N$, выведете на экран последовательность от $1$ до $N$, так чтобы ширина “ёлочки” росла волнами. Например, для $N = 49$ получим:
    $
    1; \
    2; 3; ;;;;;;;; text{–сначала до двух} \
    4; \
    5; 6; \
    7; 8; 9; ;;;;;;;; text{–потом до трёх} \
    10; 11; \
    12; ;;;;;;;; text{–возвращаемся к одному} \
    13; 14; \
    15; 16; 17; \
    18; 19; 20; 21; ;;;;;;;; text{–тут уже четыре} \
    22; 23; 24; \
    25; 26; ;;;;;;;; text{–снова убывает } \
    27; \
    28; 29; \
    30; 31; 32; \
    33; 34; 35; 36; \
    37; 38; 39; 40; 41; \
    42; 43; 44; 45; \
    46; 47; 48; \
    49;
    $