Назовём такой метод - контролируемый перебор.
program zadacha3_8c;
var k, t, o, kto, kot, tok:longint;
Begin
for k:=1 to 4 do
for t:=2 to 9 do
if kt then
for o:=0 to 9 do
if (ko) and (to) then
begin
kto:=k*100+t*10+o;
kot:=k*100+o*10+t;
tok:=t*100+o*10+k;
if kto+kot=tok then writeln(kto,'+',kot,'=',tok);
end;
End.
Такой алгоритм даже при 8-10 вложенных циклах работает очень быстро.
Вопросы для повторения:
Может ли во вложенных циклах использоваться одна и та же переменная, например i?
Можно ли вкладывать друг в друга различные циклы: FOR в WHILE или REPEAT в FOR?
Задания для самостоятельной работы:
Старинная задача. Сколько можно купить быков, коров и телят, если бык стоит 10 рублей, корова – 5 рублей, телёнок – полтинник (0,5 рубля), при условии, что на 100 рублей надо купить 100 голов скота.
Задано натуральное n. Для всех чисел от 1 до n найти:
количество делителей; b) сумму чётных делителей.
Найти все решения следующих числовых ребусов:
БАБКА+ДЕДКА+РЕПКА=СКАЗКА (4 решения)
КОРОВА+ТРАВА+ДОЯРКА=МОЛОКО (2 решения)
АЛЁНКА+ИВАН+КОЗЛИК=СКАЗКА (1 решение)
ВЕТКА+ВЕТКА+СТВОЛ=ДЕРЕВО (3 решения)
ВОРОТА+ТРАВА=ФУТБОЛ (3 решения)
Изучаем “Циклы”
М4_Блок № 3
Тема урока:
Вложенные циклы.
Цель занятия:
Закрепить знания по использованию различных типов циклов;
Получить навыки решения алгоритмов с вложенными циклами.
Для решения задачи достаточно часто требуется использовать несколько вложенных друг в друга циклических конструкций. Такие конструкции называют вложенными циклами.
Рассмотрим несколько примеров:
Дано натуральное число S. Требуется написать программу для нахождения всех прямоугольников, площадь которых равна S и стороны выражены натуральными числами.
program zadacha3_6;
var s, a, b:longint;
Begin
writeln('Введите s'); readln(s);
for a:=1 to s do
for b:=1 to s do
if a*b=s then writeln ('стороны ',a,' и ',b);
End.
Данную задачу можно было решить, используя только один цикл. Подумайте, как это сделать.
Даны натуральные числа n, m. Получить все натуральные числа, меньшие n, сумма квадратов цифр которых равна m.
program zadacha3_7;
var n, m, i, a, sum, cif:longint;
Begin
writeln('введите n и m');readln(n, m);
for i:=1 to n do
begin
a:=i;sum:=0;
while a0 do
begin
cif:=a mod 10;
sum:=sum+sqr(cif);
a:=a div 10;
end;
if sum=m then write(i,' ');
end;
End.
Найти все решения заданного числового ребуса. Каждой букве соответствует некоторая цифра. Причём одинаковым буквам соответствуют одинаковые цифры, разным буквам - разные цифры.
Поскольку здесь всего три буквы, то для решения достаточно написать три вложенных цикла, и перебрать все варианты сложения трёхзначных чисел.
program zadacha3_8a;
var k, t, o, kto, kot, tok:longint;
Begin
for k:=0 to 9 do
for t:=0 to 9 do
for o:=0 to 9 do
begin
kto:=k*100+t*10+o;
kot:=k*100+o*10+t;
tok:=t*100+o*10+k;
if (kt) and (ko) and (to) and (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 вообще необходимо не выполнять.