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

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

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

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

Задача 12. Даны натуральные числа a и b (a < b). Получите все простые числа p, удовлетворяющие неравенству a  p  b.

Решение. В этой задаче необходимо два цикла: внешний будет перебирать все целые числа из указанного диапазона, а внутренний проверять, является ли число простым. Число - простое, если делится только на единицу и само себя. Наиболее интересная часть в этой задаче - организация внутреннего цикла. В этом цикле для данного числа p будут перебираться все возможные делители числа p (от 2 до p) до получения нулевого остатка. Если делитель совпал с числом p, то число - простое, в противном случае - нет.

var a, b, p, i: integer; {a, b - границы диапазона

p - проверяемое число}

begin

write (‘задайте границы диапазона’);

readln (a, b);

for p := a to b do {перебор целых чисел из указанного диапазона}

begin i := 1;

repeat

i := i +1; {перебор делителей}

until p mod i = 0;

if i = p then writeln (p, ‘ ’); {проверяется, является ли число простым}

end;

end.

Упражнение. Даны вещественные числа a и b (a < b). Получите все целые числа р, удовлетворяющие неравенству a  p  b, сумма цифр которых является четным числом.

Переборный метод решения задач

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

Задача 13. Эта задача была сформулирована поэтом Антанасом Баранаускасом, который интересовался теорией чисел. Это любимая задача его детства, над которой он бился две недели: сколько можно купить быков, коров и телят, платя за быка 10 руб., за корову - 5 руб., а за теленка - полтинник, если на 100 рублей надо купить 100 голов скота?

Решение. Условие этой задачи можно представить в виде системы:

или после преобразования ,

где b - количество быков, k - количество коров, t - количество телят. Необходимо организовать три цикла для перебора всех возможных значений количества быков, коров и телят. Причем, можно заметить, что на 100 рублей можно купить не более 10 быков, 20 коров и 200 телят.

var a, b, c: integer;

begin

for b := 0 to 10 do

for k := 0 to 20 do

for t := 0 to 200 do

if (20*b + 10*k + t = 200) and (b + k + t = 100)

then writeln (‘на 100 рублей можно купить’,b,‘быков’,k,‘коров’,t, ‘телят’);

end.

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

Задача 14. Найдите все трехзначные числа, сумма цифр которых кратна 3.

Решение. Задача решается путем перебора всех трехзначных чисел. Причем перебор чисел можно организовать по-разному: 1) перебирать трехзначные числа, выделять цифры из числа и находить сумму цифр ; 2) организовать три цикла для перебора цифр сотен, десятков и единиц и находить сумму этих цифр.

Вариант 1.

var i : integer;

begin

for i := 100 to 999 do {перебор всех трехзначных чисел}

if (i div 100 + i div 10 mod 10 + i mod 10) mod 3 = 0

then write (i, ‘ ’);

end.

Вариант 2.

var i, j, k : integer;

begin

for i := 1 to 9 do {перебор цифр сотен}

for j := 0 to 9 do {перебор цифр десятков}

for k := 0 to 9 do {перебор единиц}

if (i + j + k) mod 3 = 0 then write (i*100 + j*10 + k, ‘ ‘);

end.

Упражнения.

Напишите программу для решения следующих задач.

1. Сегодня утром я видел в парке людей, собак и кошек. Собак было больше, чем людей. У собак и людей вместе было 100 голов и ног. А собак и людей вместе было втрое больше, чем кошек. Сколько я видел кошек? (Ответ - 8 кошек).

2. Джон Смит сообщил своей семье, что отныне каждый месяц им следует экономить вдвое больше, чем в предыдущем месяце. Они сэкономят 1 доллар в первый месяц, 2 доллара во второй месяц, 4 доллара в третий месяц и т.д. Сколько они сэкономят за год? Через сколько месяцев сумма сэкономленных долларов превысит 10000 долларов?

3. Преподаватели Калифорнийского университета удивлялись на своего нового коллегу. Когда ему сказали, что его месячный оклад составит сумму **** и через 6 месяцев будет повышен до 3 тысяч долларов, он ответил: “Какое чудесное число! Если разделить его на 10, то остаток будет равен 9, если разделить на 9, то остаток будет 8 и т.д. В конце концов остаток будет 1, когда мы разделим эту сумму на 2. Каков был первоначальный оклад нового преподавателя? (Ответ - 2519 долларов).

4. Найдите все натуральные пятизначные числа вида 67m1n (m и n-цифры), которые делятся на 36. Для представления натуральных чисел разрешается использовать короткие целые, меньшие или равные 32767. (Ответ - 67212 и 67716).

5. Для каждого четырехзначного числа составляется дробь: отношение суммы цифр числа к самому числу. Укажите четырехзначное число, для которого эта дробь наибольшая.