Помогите с задачей по Тройкам Пифагора

[quaker_strelok]

Задание:

Если p - периметр прямоугольного треугольника со сторонами {a, b, c}, то есть ровно три целочисленных решения для
p = 120:{20, 48, 52}, {24, 45, 51}, {30, 40, 50}
Для какого значения p<1000 число решений максимально?

Буду безмерно благодарен тем, кто сможет помочь, готов даже премировать :)

Если что, ася 443-478

[Admiral]

quaker_strelok в чём сложность в математической части или/и в части реализации?
В задании прямоугольный треугольник, это ж хрестоматийный случай по теореме Пифагора: Квадрат одной из сторон равен сумме квадратов других сторон.
http://upload.wikimedia.org/math/d/2/7/d27418ae24c96dff9dce9f7d48c49355.png
http://ru.wikipedia.org/wiki/Теорема_Пифагора
Надеюсь теперь с математикой ясность. Теперь насчёт реализации. Если сильно напрягаться не хочется, пускай проц напрягается, можно задействовать банальный перебор, с помощью циклов.

#include <stdio.h>
int main(int argc, char* argv[])
{
int p, pMax=0;
for (p=1;p<1000;p++)
{
//p=120;
printf("\nCurrent p=%i ",p);
for (int a=1; a<p; a++)
for (int b=1; b<p; b++)
for (int c=1; c<p; c++)
//if (p==(a + b + c) && a < (b + c) && b < (c + a) && c < (a + b))
if (p==(a + b + c) && (a*a == (b*b + c*c) || b*b == (c*c + a*a) || c*c == (a*a + b*b)))
{
printf("{a=%i b=%i c=%i} ",a,b,c);
pMax=p;
}
}
printf("p max = %i",pMax);
return 0;
}

Данный код считает долго. Код не делает выборку совпадений значений сторон, но в разной последовательности. В тексте программы закомментировано условия для всех прямоугольников.
Для p<1000 ответ будет таков
Current p=996 {a=249 b=332 c=415} {a=249 b=415 c=332} {a=332 b=249 c=415} {a=332
b=415 c=249} {a=415 b=249 c=332} {a=415 b=332 c=249}
...
p max = 996
Если подходит с делом, то нужно составлять систему уравнений, среди прочих условий которой будут присутствовать теорема Пифагора и заданное условие задачи.

[quaker_strelok]

Спасибо огромное, проблема у меня как раз в реализации, т.к. только начал изучать C++, но прога и впрямь долгая.. боюсь на компах в инсте она пол дня будет считаться...

1) Вы не уловили самого вопроса.. надо не максимальный периметр, при котором есть решения, а при каком периметре число решений максимально

2) if (p==(a + b + c) && a < (b + c) && b < (c + a) && c < (a + b))
в чем смысл этой строчки?

3) везде в циклах:

for (int a=1; a<p; a++)
for (int b=1; b<p; b++)
for (int c=1; c<p; c++)

для быстроты подсчета можно заменить p на p/2, т.к. сторона треугольника никогда не может быть больше полупериметра.. я прав?

[Admiral]

Сразу скажу, что код выполнен на С, из того что можно отнести лишь к С++ только удобный однострочный комментарий \\ вместо многострочного Сишного \* */.
По моим наблюдениям скорость проца не сильно влияет на настолько не оптимизированную программу.
В данном случаи строчка Current p развлекает скучающего оператора ПК, но если с графикой в С знакомство есть то можно строить треугольники по текущим данным. :)

1)Да есть немного. Надеюсь результаты решения (какие возможные значения a b c на данный периметер) сохранять не нужно?

2) А это я сразу не уловил, что речь идёт про частный случай - прямоугольный треугольник, а не про треугольник в общем. Это условие не вырождение треугольника (другими словами, при таких условиях можно нарисовать треугольник). Я указал ниже в комментарии к коду, что данная строчка закомментирована. Это на тот случай, если кому-то понадобится про треугольник в общем случаи.

3)Да это так, любая из сторон треугольника всегда меньше полупериметра. Вот и первые шаги в оптимизации.
Какая может быть нижняя граница для циклов? При заданном периметре, меньше чего не может быть наименьшая сторона прямоугольного треугольника? Это те вопросы, на которые не обходимо ответить, что б оптимизировать код.

Касательно уточнённого задания, то каркас отлова необходимых значений данн, осталось добавить двух мерный массив для отлова: 1) значений периметров, 2) количество решений с ними, 3)сортировка и вывод наибольшего по количеству решений периметра.
Без третьего пункта, примерно что-то на подобии такого

printf("{a=%i b=%i c=%i} ", a, b, c);
if (i==0)
{
pMaxRes[i][0]=p;
pMaxRes[i][1]=1;
i++;
}
else
{

if (p!=pMaxRes[i-1][0])
{
pMaxRes[i][0]=p;
pMaxRes[i][1]=1;
i++;
}
else
pMaxRes[i-1][1]++;
}

[quaker_strelok]

Спасибо еще раз :)

куда вставить код, который вы привели?:closed-to выложите полный код, если можно

[Admiral]

Внимание! Код не делает выборку совпадений значений сторон, но в разной последовательности, например для p=384 варианты {a=96 b=128 c=160} и {a=128 b=96 c=160} считаются абсолютно разными. Поскольку это происходит для всех p без исключения, то решение будет найденное корректно.

/*Если p - периметр прямоугольного треугольника со сторонами {a, b, c}, то есть ровно три целочисленных решения для
p = 120:{20, 48, 52}, {24, 45, 51}, {30, 40, 50}
Для какого значения p<1000 число решений максимально?*/
#include <stdio.h>

int main(int argc, char* argv[])
{
const int MyLimit = 1000;
int p, a, b, c, i=0, pMaxRes[MyLimit][2];

for (p=3; p<MyLimit; p++)
{
printf("\nCurrent p=%i ",p);
for (a=1; a<p/2; a++)
for (b=1; b<p/2; b++)
for (c=1; c<p/2; c++)
if (p==(a + b + c) && c*c == (a*a + b*b))
{
printf("{a=%i b=%i c=%i} ", a, b, c);
if (i==0)
{
pMaxRes[i][0]=p;
pMaxRes[i][1]=1;
i++;
}
else
{

if (p!=pMaxRes[i-1][0])
{
pMaxRes[i][0]=p;
pMaxRes[i][1]=1;
i++;
}
else
pMaxRes[i-1][1]++;
}
}
}

for (a=0; a<i; a++)
printf("\nValid perimeter = %i match %i", pMaxRes[a][0], pMaxRes[a][1]);
return 0;
}


Valid perimeter = 12 match 2
Valid perimeter = 24 match 2
Valid perimeter = 30 match 2
Valid perimeter = 36 match 2
Valid perimeter = 40 match 2
Valid perimeter = 48 match 2
Valid perimeter = 56 match 2
Valid perimeter = 60 match 4
Valid perimeter = 70 match 2
Valid perimeter = 72 match 2
Valid perimeter = 80 match 2
Valid perimeter = 84 match 4
Valid perimeter = 90 match 4
Valid perimeter = 96 match 2
Valid perimeter = 108 match 2
Valid perimeter = 112 match 2
Valid perimeter = 120 match 6
Valid perimeter = 126 match 2
Valid perimeter = 132 match 4
Valid perimeter = 140 match 2
Valid perimeter = 144 match 4
Valid perimeter = 150 match 2
Valid perimeter = 154 match 2
Valid perimeter = 156 match 2
Valid perimeter = 160 match 2
Valid perimeter = 168 match 6
Valid perimeter = 176 match 2
Valid perimeter = 180 match 6
Valid perimeter = 182 match 2
Valid perimeter = 192 match 2
Valid perimeter = 198 match 2
Valid perimeter = 200 match 2
Valid perimeter = 204 match 2
Valid perimeter = 208 match 2
Valid perimeter = 210 match 4
Valid perimeter = 216 match 2
Valid perimeter = 220 match 2
Valid perimeter = 224 match 2
Valid perimeter = 228 match 2
Valid perimeter = 234 match 2
Valid perimeter = 240 match 8
Valid perimeter = 252 match 6
Valid perimeter = 260 match 2
Valid perimeter = 264 match 4
Valid perimeter = 270 match 4
Valid perimeter = 276 match 2
Valid perimeter = 280 match 6
Valid perimeter = 286 match 2
Valid perimeter = 288 match 4
Valid perimeter = 300 match 4
Valid perimeter = 306 match 2
Valid perimeter = 308 match 2
Valid perimeter = 312 match 4
Valid perimeter = 320 match 2
Valid perimeter = 324 match 2
Valid perimeter = 330 match 4
Valid perimeter = 336 match 6
Valid perimeter = 340 match 2
Valid perimeter = 348 match 2
Valid perimeter = 350 match 2
Valid perimeter = 352 match 2
Valid perimeter = 360 match 8
Valid perimeter = 364 match 2
Valid perimeter = 372 match 2
Valid perimeter = 374 match 2
Valid perimeter = 378 match 2
Valid perimeter = 380 match 2
Valid perimeter = 384 match 2
Valid perimeter = 390 match 4
Valid perimeter = 392 match 2
Valid perimeter = 396 match 6
Valid perimeter = 400 match 2
Valid perimeter = 408 match 4
Valid perimeter = 416 match 2
Valid perimeter = 418 match 2
Valid perimeter = 420 match 10
Valid perimeter = 432 match 4
Valid perimeter = 440 match 4
Valid perimeter = 442 match 2
Valid perimeter = 444 match 2
Valid perimeter = 448 match 2
Valid perimeter = 450 match 4
Valid perimeter = 456 match 4
Valid perimeter = 462 match 4
Valid perimeter = 468 match 4
Valid perimeter = 476 match 2
Valid perimeter = 480 match 8
Valid perimeter = 490 match 2
Valid perimeter = 492 match 2
Valid perimeter = 494 match 2
Valid perimeter = 504 match 8
Valid perimeter = 510 match 4
Valid perimeter = 516 match 2
Valid perimeter = 520 match 4
Valid perimeter = 528 match 6
Valid perimeter = 532 match 2
Valid perimeter = 540 match 6
Valid perimeter = 544 match 2
Valid perimeter = 546 match 4
Valid perimeter = 552 match 4
Valid perimeter = 560 match 6
Valid perimeter = 564 match 2
Valid perimeter = 570 match 4
Valid perimeter = 572 match 2
Valid perimeter = 576 match 4
Valid perimeter = 588 match 4
Valid perimeter = 594 match 2
Valid perimeter = 598 match 2
Valid perimeter = 600 match 6
Valid perimeter = 608 match 2
Valid perimeter = 612 match 4
Valid perimeter = 616 match 4
Valid perimeter = 624 match 6
Valid perimeter = 630 match 8
Valid perimeter = 636 match 2
Valid perimeter = 640 match 2
Valid perimeter = 644 match 2
Valid perimeter = 646 match 2
Valid perimeter = 648 match 2
Valid perimeter = 650 match 2
Valid perimeter = 660 match 10
Valid perimeter = 672 match 8
Valid perimeter = 680 match 4
Valid perimeter = 684 match 4
Valid perimeter = 690 match 4
Valid perimeter = 696 match 2
Valid perimeter = 700 match 4
Valid perimeter = 702 match 2
Valid perimeter = 704 match 2
Valid perimeter = 708 match 2
Valid perimeter = 714 match 2
Valid perimeter = 720 match 12
Valid perimeter = 728 match 4
Valid perimeter = 732 match 2
Valid perimeter = 736 match 2
Valid perimeter = 744 match 2
Valid perimeter = 748 match 2
Valid perimeter = 750 match 2
Valid perimeter = 756 match 8
Valid perimeter = 760 match 4
Valid perimeter = 768 match 2
Valid perimeter = 770 match 4
Valid perimeter = 780 match 8
Valid perimeter = 782 match 2
Valid perimeter = 784 match 2
Valid perimeter = 792 match 6
Valid perimeter = 798 match 2
Valid perimeter = 800 match 4
Valid perimeter = 804 match 2
Valid perimeter = 810 match 4
Valid perimeter = 816 match 4
Valid perimeter = 828 match 4
Valid perimeter = 832 match 2
Valid perimeter = 836 match 2
Valid perimeter = 840 match 16
Valid perimeter = 850 match 2
Valid perimeter = 852 match 2
Valid perimeter = 858 match 2
Valid perimeter = 864 match 6
Valid perimeter = 870 match 4
Valid perimeter = 874 match 2
Valid perimeter = 876 match 2
Valid perimeter = 880 match 6
Valid perimeter = 882 match 2
Valid perimeter = 884 match 2
Valid perimeter = 888 match 2
Valid perimeter = 896 match 2
Valid perimeter = 900 match 8
Valid perimeter = 910 match 4
Valid perimeter = 912 match 4
Valid perimeter = 918 match 4
Valid perimeter = 920 match 4
Valid perimeter = 924 match 10
Valid perimeter = 928 match 2
Valid perimeter = 930 match 2
Valid perimeter = 936 match 6
Valid perimeter = 948 match 2
Valid perimeter = 950 match 2
Valid perimeter = 952 match 4
Valid perimeter = 960 match 8
Valid perimeter = 966 match 2
Valid perimeter = 972 match 2
Valid perimeter = 980 match 2
Valid perimeter = 984 match 2
Valid perimeter = 986 match 2
Valid perimeter = 988 match 2
Valid perimeter = 990 match 8
Valid perimeter = 992 match 2
Valid perimeter = 992 match 2
Valid perimeter = 996 match 2
для анализа оператором ПК и принятии решения про ответ.

Как видно из таблицы Valid perimeter = 840 match 16 - ответ, то есть 840 максимальный целочисленный периметр, меньший за 1000, прямоугольного треугольника, при котором число решений максимально и составляет 16, с учётом того что треугольник можно разворачивать.

Если нужен результат чётко, то нужно поработать с двухмерным массивом pMaxRes[][]: отсортировать/найти наибольший элемент во втором ряде и вывести соответствующиё значение с первого.

[quaker_strelok]

у меня последний код не выполняется...

1) по моему где-то лишняя скобочка....
2) пишет что вот здесь printf("p max = %i",pMax);

error C2065: 'pMax' : undeclared identifie

[Drongo]

error C2065: 'pMax' : undeclared identifie »Так в последнем коде такой переменной нет вовсе.1) по моему где-то лишняя скобочка....
2) пишет что вот здесь printf("p max = %i",pMax); » Вы что-то путаете? У меня всё компилируется без нареканий... Помоему вы смешали первый код со вторым.

Выделите текст внутри кода, что написал Admiral, - скопируйте - вставьте в файл .cpp - сохраните, откройте и откомпилируйте.

[quaker_strelok]

Drongo, опс, действительно ошибка получилась у меня.. прошу прощения.

Если нужен результат чётко, то нужно поработать с двухмерным массивом pMaxRes[][]: отсортировать/найти наибольший элемент во втором ряде и вывести соответствующиё значение с первого. »

Если не сложно - можете вот это тоже написать? :)

[Admiral]

quaker_strelok - после уточнение задания на смену переменной pMax пришёл массив pMaxRes[][], впрочем можно было завести несколько переменных, но с массивом нагляднее.

Что б не повторять весь код заново приведу окончание программы

b=pMaxRes[0][1];
c=0;
for (a=1; a<i; a++)
if (b <= pMaxRes[a][1])
{
b=pMaxRes[a][1];
c=a;
}
printf("\nValid perimeter = %i match %i", pMaxRes[c][0], pMaxRes[c][1]);
return 0;

[quaker_strelok]

Всё, спасибо всем, вроде всё отлично работает :)