Для решения задачи достаточно часто требуется использовать две и более циклические конструкции, одна из которых помещается в тело цикла другой. Такие конструкции называют вложенными циклами. Внутренний и внешний циклы могут быть любыми из трех рассмотренных ранее видов. Правила организации внешнего и внутреннего циклов такие же, как и соответствующих простых операторов. Однако при использовании вложенных циклов необходимо соблюдать следующее условие: внутренний цикл должен полностью укладываться в циклическую часть внешнего цикла.
Пример 1. Даны натуральные числа n и k. Составить программу вычисления выражения 1k+2k+...+nk.
Ввод:
1 строка - число N
2 строка - число k
Вывод:
Сумма - S
Для вычисления указанной суммы целесообразно использовать
1) Внешний цикл For с управляющей переменной i, изменяющейся от 1 до n.
2) Внутренний цикл For с управляющей переменной j, изменяющейся от 1 до k, в котором будем вычислять p=i в степени k и сумму всех элементов.
Program z1 ;
Var n, k, i, j: Integer;
p,s:int64;
Begin
ReadLn (n,k) ;
s:=0 ;
For i:=1 To n Do
Begin
p:=1;
For j:=1 To k Do
p:=p*i;
s:=s+p;
End;
WriteLn(s);
End.
1. Отладка программы:
1) Выполните команду Debug/Watch. Появится окно Watches.
2) Используя клавиши Ctrl+F7 (инициируется открытие окна Add Watch), введите переменные программы (i ,P,s).
3) Выполните программу в пошаговом режиме (последовательное нажатие на F8), отслеживая изменение значений переменных в окне Watches. При выполнении ReadLn (n,k) введите, например, значения 4 и 2 для того, чтобы количество повторений цикла было небольшим.
2. Измените программу так, чтобы вычислялась сумма 11+22+ + ...+nn .
Указание. Требуется изменить параметры у внутреннего оператора For (For j:=1 То i Do p:=p*i;) и убрать переменную k.
Задание 1. Сложим все цифры какого-либо числа. Получим новое число, равное сумме всех цифр исходного числа. Продолжим этот процесс до тех пор, пока не получим однозначное число (цифру), называемое цифровым корнем данного числа. Например, цифровой корень числа 34697 равен 2 (3+4 + 6+9+7=29; 2+9=11; 1+1=2). Составить программу нахождения цифрового корня натурального числа.
Задание 2. "Рисование" символами. Выведите на экран числа в следующем виде:
1
2 2
3 3 3
4 4 4 4
5 5 5 5 5
и т.д.
Имеется целый класс задач, решение которых сводится к перебору различных вариантов, среди которых выбирается такой, который удовлетворяет условию задачи.
Пример 2. Поиск делителей целого числа N.
Целое число K является делителем N, если остаток от деления N на K равен 0. Чтобы найти все делители достаточно перебрать все числа от 1 до N и проверить, являются ли они делителями.
program z11;
var n,i:integer;
BEGIN
readln(n);
for i:=1 to n do
if n mod i = 0 then
write(i, ' ');
END.
На этом примере ясна общая структура решения задач на перебор вариантов. Для организации перебора используется цикл, каждый шаг выполнения которого соответствует рассмотрению одного из вариантов. Внутри цикла стоит проверка, подходит ли данный вариант под условие задачи.
Решая задачи методом перебора, всегда следует подумать, а нельзя ли каким-то образом сократить количество перебираемых вариантов. В данном случае заметим, что любое число делится само на себя и на 1. Поэтому эти варианты можно исключить из перебора. Более того, наибольшим делителем, отличным от самого числа N может быть только N/2, а все числа, большие N/2 заведомо делителями не являются. Учет этих особенностей приводит к более эффективной программе:
program z11;
var n,i:integer;
BEGIN
readln(n);
write(1, ' ', n,' ');
for i:=2 to n div 2 do
if n mod i = 0 then
write(i, ' ');
END.
Продолжая размышления о сокращении перебора, заметим, что если i является делителем, то частное от деления на i — тоже делитель. Таким образом, выводя делители парами, можно ограничится перебором до корня из n:
program z11;
var n,i,m:integer;
BEGIN
readln(n);
m:=trunc(sqrt(n));
write(1, ' ', n,' ');
for i:=2 to m do
if n mod i = 0 then
write(i, ' ',n div i,' ');
END.
Задание 3. Старинная задача. Сколько можно купить быков, коров и телят, если плата за быка 10 рублей, за корову — 5 рублей, за теленка — полтинник (0.5 рубля), если на 100 рублей надо купить 100 голов скота.
Обозначим через b — количество быков; k — количество коров; t — количество телят. После этого можно записать два уравнения: 10b+5k+0.5t=100 и b+k+t=100. Преобразуем их: 20b+10k+t=200 и b+k+t=100.
На 100 рублей можно купить:
не более 10 быков, т. е. 0<b<10,
не более 20 коров, т. е. 0<k<20,
не более 200 телят, т. е. 0<t<200.
1. Сколько раз будет проверяться условие? (11*21*201=46431 раз)
2. Можно ли сократить количество проверок? (Если известно количество коров и быков, тогда количество телят можно найти с.о. 100-(b+k)).
Program z2;
Var b, k, t: Integer;
Begin
For b:=0 To 10 Do
For k:=0 To 20 Do
begin
t:=100-(b+k);
If (20*b+10*k+t=200) and (b+k+t=100)
Then WriteLn (' b= ' ,b,' k= ',k,' t= ' ,t);
end;
End.
3. Сколько раз будет выполняться проверка условия в этом случае? (11*21=231 раз)
Пример 5. Написать программу, которая находит все четырехзначные числа abсd (а, b, с, d — цифры числа, причем между ними нет совпадений, т. е. числа, например, типа 1221 нас не устраивают, т. е. любые две цифры числа различны), для которых выполняется условие: ab-cd=a+b+c+d. Другими словами, разность чисел, составленных из старших цифр числа и из младших, равна сумме цифр числа.
Например, рассмотрим число 5236: 52-36=5+2+3+6; 16=16.
Один из способов решения— перебор всех четырехзначных чисел и проверка выполнения условия. Попробуем сократить перебор, для этого преобразуем условие.
10*a+b-(10*c+d)=a+b+c+d
10*a+b-10*c-d=a+b+c+d;
9a-11c-2d=0
9a-9c-2c-2d=0
9(a-c)=2(c+d)
(a-c)/(c+d)=2/9, тогда a-c=2 и c+d=9, следовательно, а=с+2, d=9-c и 0≤с≤7.
program z3;
Var a,b,c, d:Integer;
Begin
For c:=0 To 7 Do
Begin
a:=c+2;
d:=9-c;
For b:=0 To 9 Do
If (b<>c) And (b<>a) And (b<>d) Then writeln(a,b,c,d) ;
End;
End.