Сайт Льва Волкова
  
· Человек употребляет нецензурные выражения в среднем 230105 раз в течение жизни.
 
      На главную  
 Личное
  Статьи
  Задачи 
 Ссылки
 АТ-531
www.levvol.ru    
 

Прямоугольный треугольник с максимальным периметром

Чему равен максимальный периметр прямоугольного треугольника со сторонами, являющимися натуральными числами, меньший 1 миллиона? Задача была опубликована на сайте diofant.ru.

Прямоугольный треугольник с натуральными длинами всех трех его сторон называется пифагоровым, так как считается, что Пифагор (570 — 500 до н.э.) впервые доказал, что квадрат длины гипотенузы любого прямоугольного треугольника равен сумме квадратов длин его катетов. Тройка натуральных чисел (x,y,z), для которой
x2+y2=z2 (1)

называется пифагоровой.[1]

Во всех древних развитых цивилизациях (Вавилон, Египет, Индия, Китай, Греция) из поколения в поколение передавалась магическая сила прямоугольного треугольника с длинами сторон 3, 4,5.

Ветхом Завете сказано, что при построении скинии — основной иудейской святыни — использовались ковры, основной прямоугольник которых имел размер 3 х 4 локтя (Исход, 37,10), а при возведении храма Соломона были изготовлены подставки для жертвенных чаш с боковыми гранями размером 3 х 4 локтя (I кн. Царств, 7,27).

Тройка (3,4,5) натуральных чисел упоминалась в дошедшем до нас диалоге китайского императора Чжоу-Гуна (1100 г. до н.э.) с ученым Шан Гао.

Пифагор называл эту тройку «невестой», а Платон считал, что тройка (3,4,5)— это супружество: горизонтальный катет, длиной четыре, — это женское начало, вертикальный катет, длиной три, — это мужское начало, а гипотенуза, длиной пять, — их потомство.

В 14 году до нашей эры римский писатель, архитектор и инженер Витрувий восславил построение прямого угла с помощью тройки (3,4,5) как величайшее достижение матматики той эпохи.[2]

Очевидно тождество
(x,y,z)=(y,x,z) (2)

Если (x,y,z) пифагоров тройка, то тройка (λx,λy,λz), где λ — натуральное число также является пифагоровой.

Любой пифагоров треугольник обладает следующими свойствами:

  • один из его катетов кратен 4;
  • один из его катетов кратен 3;
  • одна из его сторон кратна 5.

Следствие: в любом пифагоровом треугольнике (x,y,z)произведение трех сторон кратно 60.

Если (x,y,z) не имеют общего множителя, отличного от единицы, то пифагорова тройка называется простейшей или несократимой.

Если же НОД(x,y)=2, то такая тройка назывется квазипростейшей.

Диофант (III в н.э.) широко использовал в своих книгах «Арифметика» формулу:
(2mn,m2-n2,m2+n2)
НОД(m,n)=1; m>n
(3)

Для множества всех простейших и квазипростейших пифагоровых троек, где m и n — взаимопростые натуральные числа, m>n. [1]

Перейдем к решению задачи нахождения сторон пифагорова треугольника с максимальным перметром, при условии, что его периметр не превышает 1000000.

В пифагоровом треугольнике периметр будет равен
p=2mn+2m2 (4)

т.е. всегда является четным числом.

В нашем случае mn+m2<500000.

Будем перебирать значения m,n от 1 до 707 (7072≈500000).


Program MaxPerimetr;
Uses CRT;
Var m,n,p,mn,mm,mp,m2,a,b,c:longint;
Begin
ClrScr;
mp:=0;
for m:=1 to 707 do begin
m2:=m*m; {Квадрат m вычисляем вне цикла}
n:=1;
while n<m do begin
a:=2*m*n;
b:=m2-n*n;
c:=m2+n*n; p:=a+b+c;
if (p>mp) and (p<1000000) then begin
mp:=p;
mm:=m;
mn:=n;
end;
n:=n+1;
end;
end;
writeln('Катет a=',2*mn*mm:7);
writeln('Катет b=',mm*mm-mn*mn:7);
writeln('Гипотенуза с=',mm*mm+mn*mn:7);
writeln('Периметр p=',mp:7);
readln
End.


Сохранить эту программу

В результате работы программы мы получили следующие значения
Катет         а= 497994
Катет         b= 3992
Гипотенуза c= 498010
Периметр    p= 999996

Сделаем выводы относительно сокращения и оптимизации перебора на примере рассмотренной задачи:

  • Надо правильно выбрать границы значений перебираемых величин. Мы взяли диапазон изменения параметров m и n от 1 до 707.

  • Надо исключить неверные, лишние ветви перебора. Мы рассматриваем варианты, когда m>n.

  • Следует избегать многократного применения одних и тех же операций в циклах, если данные могут быть подготовленны заранее. Мы вычисляем значение m2 один раз вне цикла изменения n.

  • Надо выбрать хорошее начальное приближение. В данной задаче этот принцип не важен.[3]



Источники:

  1. Малаховский В.С. Числа знакомые и незнакомые: Учебное пособие/ В.С.Малаховский. -Калининград. ФГУИПП «Янтарный сказ» 2004. - 184 c.
  2. Боро В., Цагир Д., Рольфс Ю., Краф Х., Янцен Е. Живые числа. -М.: Мир, 1985. -128 с.
  3. Есипов А.С., Паньгина Н.Н., Громада М.И. Информатика. Сборник задач и решений для общеобразовательных учебных заведений. -СПб.: Наука и Техника, 2001. - 368 с.

Назад