Компьютерный форум OSzone.net  

Компьютерный форум OSzone.net (http://forum.oszone.net/index.php)
-   Программирование и базы данных (http://forum.oszone.net/forumdisplay.php?f=21)
-   -   Помогите с задачей по Тройкам Пифагора (http://forum.oszone.net/showthread.php?t=124100)

quaker_strelok 25-11-2008 21:19 963504
Помогите с задачей по Тройкам Пифагора
 
Задание:

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

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

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

Admiral 26-11-2008 01:35 963696
quaker_strelok в чём сложность в математической части или/и в части реализации?
В задании прямоугольный треугольник, это ж хрестоматийный случай по теореме Пифагора: Квадрат одной из сторон равен сумме квадратов других сторон.

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 26-11-2008 17:28 964306
Спасибо огромное, проблема у меня как раз в реализации, т.к. только начал изучать 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 27-11-2008 01:26 964772
Сразу скажу, что код выполнен на С, из того что можно отнести лишь к С++ только удобный однострочный комментарий \\ вместо многострочного Сишного \* */.
По моим наблюдениям скорость проца не сильно влияет на настолько не оптимизированную программу.
В данном случаи строчка 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 27-11-2008 01:33 964779
Спасибо еще раз :)

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

Admiral 27-11-2008 02:06 964797
Внимание! Код не делает выборку совпадений значений сторон, но в разной последовательности, например для 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 27-11-2008 19:03 965461
у меня последний код не выполняется...

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

error C2065: 'pMax' : undeclared identifie

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

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

quaker_strelok 28-11-2008 00:10 965738
Drongo, опс, действительно ошибка получилась у меня.. прошу прощения.

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

Admiral 28-11-2008 21:52 966721
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 01-12-2008 16:44 969108
Всё, спасибо всем, вроде всё отлично работает :)


Время: 00:01.

Время: 00:01.
© OSzone.net 2001-