Задача 6: Равновеликие прямоугольники.
Прямоугольники, площади которых равны, называются равновеликими.
Написать программу, находящую все возможные целочисленные стороны
равновеликих прямоугольников заданной площади. Одинаковые
прямоугольники, получающиеся заменой сторон, печатать не надо.
Входные данные:
Площадь четырехугольника (1<=n<=50000).
Выходные данные:
Стороны четырехугольника (A*B)
Пример входных данных:
12
Пример выходных данных:
1*12
2*6
3*4
Решение:
Попробуем упростить задачу. Разберемся, что такое площадь
прямоугольника. Площадь прямоугольника - произведение длин двух
прилежащих сторон. Т.е. задачу можно представить как нахождение всех
пар множителей, дающих заданный результат.
Рассмотрим алгоритм эффективного поиска множителей данного числа.
(Кстати, эта задача была на одной из олимпиад несколько лет назад)
Мы будем искать одновременно два сопряженных множителя, т.е.
множителя, которые при перемножении дают искомое число.
Код программы:
MaxF := trunc(sqrt(N));
{Первый множитель данного числа не может быть больше корня из
этого числа, в то время как сопряженный с ним множитель всегда
не меньше этого корня}
For F := 1 to MaxF do
If N mod F = 0 then Writeln (F, N div F);
Вот и все! Для
примера приведем авторское решение:
{Равновеликие
прямоугольники. Решение А.Никитина, Самара }
program equrectangle;
var p:word; {переменная для площади}
procedure find_and_print_side(a,b:word);
begin
if (a<=b) then begin
if (a*b=p) then writeln(a,'*',b);
inc(a); find_and_print_side(a,p div a);
end;
end;
begin { основная программа }
assign(input,'square.in'); reset(input); readln(p); close(input);
assign(output,'square.out'); rewrite(output);
find_and_print_side(1,p);
close(output);
end.
Кажется, оно
неэффективное. Для этого проделаем небольшой эксперимент:
1) Заменим ограничение на N<=1000000000.
2) Исправим в авторском решении тип переменных с word на longint.
На тесте 98765432 мы не дождемся, пока программа найдет ответ, а
если ввести какое-нибудь большое простое число, то она будет
проводить n итераций, в то время как вторая программа независимо от
числа производит sqrt(n) операций. Ура :)
Далее
ð
