Класс задач, в которых требуется перебрать множество вариантов и выбрать несколько оптимальных по каким-то критериям.
Задача. Дано равенство: a2 + b2 = c2, a,b,c — целые Вывести все такие тройки (a, b, c), что: a<=1000, b<=1000, c<=1000;
Решение.
for var a:=1 to 1000 dofor var b:=1 to 1000 dofor var c:=1 to 1000 do if a*a + b*b = c*c then writeln(a, b, c);
Однако, ясно, что
a2 + b2 = c2 <=> b2 + a2 = c2
Кроме того, c можно вычислять.
Оптимизация.
for var a:=1 to 1000 do for var b:=1 to a-1 do begin var c := round(sqrt(a*a + b*b)); if a*a + b*b = c*c then begin writeln(a, b, c); writeln(b, a, c); end; end;
Вывод. При наличии нескольких вложенных циклов, в первую очередь, нужно оптимизировать самый внутренний.
