Вложенные циклы
Рассмотрим задачи, где в среди операторов тела цикла присутствует другой оператор цикла.Пример1. Для заданного натурального числа n найти такие тройки натуральных чисел a, b, c, что a + b + c = n.
|
var a, b, c, n : integer; kol : integer; begin write ('введи число'); read (n); for a := 0 to n do for b := 0 to n do for c := 0 to n do if a + b + c = n then begin writeln (a, ' ', b, ' ', c); kol := kol + 1; end; writeln ('количество способов ', kol); end. |
{ n — введенное число } { пробуем в качестве a все числа от 0 до n } { пробуем в качестве b все числа от 0 до n } { пробуем в качестве c все числа от 0 до n } { если a + b + c = n, то }
{ печатаем тройку чисел } { подсчитываем количество способов } |
Программа работает, однако время работы ее пропорционально n3.
Очевидно, что числа a, b, c зависимы. А именно, при некотором фиксированном значении a, значение b может изменяться до n – a. Переменная c с учетом зафиксированных a и b изменяется до n - a - b.
Тогда циклы могут быть записаны в виде:
for a := 1 to n do
for b := 1 to n - a do
for c := 1 to n - a - b do
if a + b + c = n then
begin
writeln (a, ' ', b, ' ', c);
kol := kol + 1;
end;
writeln ('количество способов ', kol);
Это чуть-чуть лучше, поскольку количество циклов стало равным n * (n-1) * (n-2).
Еще раз взглянем на возможные граничные значения переменных a, b и c.
Переменная а должна изменяться до n-2, что следует из того, что числа натуральные.
Переменная b должна изменяться до n - a - 1.
Тогда на долю с остается n - a - b.
var a, b, c, n : integer;
kol : integer;
begin
write ('введи число');
read (n);
for a := 1 to n - 2 do
for b := 1 to n - a - 1 do
begin
c := n - a - b;
if c = 0 then
begin
writeln (a, ' ', b, ' ', c);
kol := kol + 1;
end;
end;
writeln ('количество способов ', kol);
end.