Поиск нуля функции на отрезке
Требуется найти корень уравнения f( x ) = 0
на отрезке [a; b]
с заданной точностью eps
f(x) непрерывна на этом отрезке
имеет на нем ровно 1 корень, т.е. f(a ) * f( b ) < 0
Эта задача решается методом половинного деления.
assert(b > a);
var fa := f(a);
var fb := f(b);
assert(fa * fb < 0);
while b - a > eps do
begib
var x := (b + a) / 2;
var fx := f(x);
if fx * fa > 0 then
begin
a := x;
fa := fx;
end
else
b := x;
end;
Вложенные циклы
Метод последовательной детализации
Задача. Вывести все простые числа <= n
writeln(2);
x := 3;
while x <= n do
begin
Если число x — простое, то
writeln(x);
x += 2;
end;
Метод окаймления
Задача. Вывести Ak, A = 2..10
Метод окаймления заключается в том, что что мы окаймляем данный алгоритм внешним циклом, "размораживая" некоторый параметр.
Итак, пусть A — фиксировано( "заморожено" ).
var p := 1.0;
for var i:=1 to k do
p *= A;
write(p);
Теперь размораживаем A:
for A:=2 to 10 do
begin
...
end;
Переборные задачи
Класс задач, в которых требуется перебрать множество вариантов и выбрать несколько оптимальных по каким-то критериям.
Задача. Дано равенство: a2 + b2 = c2, a,b,c — целые Вывести все такие тройки (a, b, c), что: a<=1000, b<=1000, c<=1000;
Решение.
for var a:=1 to 1000 do
for var b:=1 to 1000 do
for 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;
Вывод. При наличии нескольких вложенных циклов, в первую очередь, нужно оптимизировать самый внутренний.