С Новым годом! Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 5.00/21: Рейтинг темы: голосов - 21, средняя оценка - 5.00
0 / 0 / 0
Регистрация: 30.03.2017
Сообщений: 36
1

Задача о Пифагоровых тройках

17.07.2017, 15:37. Показов 4111. Ответов 22
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Добрый день. Думаю, многие решали эту задачу просто методом перебора для небольших значений. В данном случае, необходимо при заданном c (гипотенуза) найти все тройки взаимно простых чисел a, b, c, таких, что a*a + b*b = c*c.
При 0 < с < 10^6. Как ни крутил, не выходит O(n), быть может, есть какая-то математическая хитрость. Заранее спасибо !
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
17.07.2017, 15:37
Ответы с готовыми решениями:

Найти общее решение в примитивных тройках уравнения: x^2-y^2=z^n
Господа, найдите общее решение в примитивных тройках уравнения: {x}^{2}-{y}^{2}={z}^{n} x, y...

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

Генерация Пифагоровых троек
Попалась в разделе &quot;C для начинающих&quot;. Пифагорова тройка целых - это тройка (x,y,z), такая, что...

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

22
Заблокирован
17.07.2017, 15:50 2
"взаимно простых чисел a, b" это что за дополнительное условие?
0
0 / 0 / 0
Регистрация: 30.03.2017
Сообщений: 36
17.07.2017, 15:53  [ТС] 3
MansMI, a,b и c. Все три числа взаимно простые.
0
68 / 51 / 27
Регистрация: 27.04.2015
Сообщений: 203
17.07.2017, 16:14 4
Цитата Сообщение от MansMI Посмотреть сообщение
"взаимно простых чисел a, b" это что за дополнительное условие?
ТСу нужны только примитивные тройки.
0
Заблокирован
17.07.2017, 16:22 5
может так, не проверял
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int abc(int a,int b,int c)
{
    for(int i=2; i<=a; i++)
        if((a%i==0 + b%i==0 + c%i==0)>1) return 0;
    return 1;
}
void main()
{
    int c;
    cout<<"c:";
    cin>>c;
    int c2=c*c;
    int d=(int)sqrt((double)c2/2);
    for(int a=0; a<=d; a++)
    for(int b=a; b<=c; b++)
    if(a*a+b*b==c2 && abc(a,b,c))
        cout<<a<<" "<<b<<" "<<c<<endl;
0
0 / 0 / 0
Регистрация: 30.03.2017
Сообщений: 36
17.07.2017, 16:30  [ТС] 6
MansMI, прошу прощения, забыл уточнить, что лимит по времени - 1 сек.
В вашем примере достаточно взять тот же крайний случай c = 10^6 , тогда d = 707000 ( примерно ) , первый for будет выполняться d раз, а с учётом второго, там получится слишком долгий перебор.
0
68 / 51 / 27
Регистрация: 27.04.2015
Сообщений: 203
17.07.2017, 16:36 7
Да тут просто перебор, он находит все тройки. Чтобы оптимизировать скорость работы, надо воспользоваться как-то красиво формулой Евклида и генерировать для нее некоторые разные по четности взаимно простые числа, а потом уже используя их и находить сами тройки. Но это не точно
0
Заблокирован
17.07.2017, 16:38 8
motocross971, ну и сколько 1М длится?
0
0 / 0 / 0
Регистрация: 30.03.2017
Сообщений: 36
17.07.2017, 16:51  [ТС] 9
MansMI, ну я так предполагаю, что, если 0 <= a <= d, a <= b <= c, тогда, пусть с = 10^6. Для a = 0, b сделает с - a = 1 000 000 проходов, потом, при а = 1, b сделает c - a = 999 999 проходов и тд. Пускай, грубо говоря d = 700000, тогда минимальное значение c - a = 300 000. Выполняться будет за n*(n-1) /2 , где n = 700000. Поправьте, если неправ.
0
Заблокирован
17.07.2017, 16:55 10
я тут скобок пожалел, нужно if((a%i==0)+(b%i==0)+(c%i==0)>1) return 0;
вполне возможно, но как n конвертируется в секунды?
0
0 / 0 / 0
Регистрация: 30.03.2017
Сообщений: 36
17.07.2017, 17:01  [ТС] 11
MansMI , Если n = 7 * 10^5, то O(n*n) = 49 * 10^10 = 490 * 10^9. Не думаю, что обычный современный компьютер выполнит такое количество операций за 1 сек.
0
0 / 0 / 0
Регистрация: 30.03.2017
Сообщений: 36
17.07.2017, 17:09  [ТС] 12
Запустил на Visual Studio 2013 на процессоре core i5 3.3 GHz. Уже для с = 100 000 выходит за рамки, для с = 1 000 000 побоялся запускать.
Изображения
 
0
167 / 107 / 22
Регистрация: 02.01.2012
Сообщений: 596
17.07.2017, 18:12 13
Ну Вы странный перебор устроили.. Примитивная тройка всегда представима в виде
https://www.cyberforum.ru/cgi-bin/latex.cgi?\left\{a = {m}^{2} - {n}^{2}\\ b = 2mn\\c = {m}^{2} + {n}^{2}\begin{matrix}\end{matrix}\right.
Где m и n разной чётности и взаимно просты.
Так что перебор нужно только до c, а не до с2.
Если с до 10e6, можно предварительно построить массив из тысячи квадратов
0
68 / 51 / 27
Регистрация: 27.04.2015
Сообщений: 203
17.07.2017, 18:21 14
Попробовал написать, как я предлагал выше. Тестируйте.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
 
bool haveGCD(int n, int m)//имеют общий делитель
{
    for (auto i = n; i > 1; i--) {
        if (!n%i || !m%i) return 1;
    }
    return 0;
}
 
int main()
{
    while (true) {
        int x = 0, y = 0, z, n, m;
        std::cin >> z;
        for (n = 1; n < (double)sqrt(z); n++) {
            for (m = n + 1; m < sqrt(z); m += 2) {
                if (n*n + m*m == z) {
                    if (!haveGCD(n, m)) {
                        x = m*m - n*n;
                        y = 2 * n*m;
                        std::cout << x << " " << y << " " << z << std::endl;
                    }
                }
            }
        }
        system("pause");
        system("cls");
    }
    return 0;
}
Я не буду врать, потому что мне лень считать или проверять, насколько быстро работает программа. Но если разобраться с алгоритмом подбора n и m, да еще и возможно как-то упростит проверку на взаимную простоту этих чисел, то это, наверное, один из оптимальных вариантов решения.

Добавлено через 9 минут
UPD замерил наскоряк, у меня даже при {10}^{7} получается меньше секунды
1
Заблокирован
17.07.2017, 18:24 15
добрался до VS , а какие нибудь контрольные гипотенузы есть? а то ничего кроме 5 на ум не приходит, 999997 вроде считает
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int abc(int a,int b,int c)
{
    if(b%a==0 || c%a==0) return 0;
    int n=(int)sqrt((double)a);
    for(int i=2; i<=n; i++)
        if(!(a%i)+!(b%i)+!(c%i)>1) return 0;
    return 1;
}
void main(int argc,char **argv)
{
    int c;
    cout<<"c:";
    cin>>c;
    _int64 c2=(_int64)c*c;
    int d=(int)sqrt((double)c2/2);
    for(int a=1; a<=d; a++)
    {
        _int64 a2=(_int64)a*a;
        int b=(int)sqrt((double)c2-a2);
        _int64 n=a2+(_int64)b*b;
        if(n==c2 && abc(a,b,c)) 
                cout<<a<<" "<<b<<" "<<c<<endl;
    }
    system("pause");
}
0
68 / 51 / 27
Регистрация: 27.04.2015
Сообщений: 203
17.07.2017, 18:26 16
MansMI, на [url=https://ru.wikipedia.org/wiki/%D0%9F%D0%B8%D1%84%D0%B0%D0%B3%D0%BE%D1%80%D0%BE%D0%B2%D0%B0_%D1%82%D1%80%D0%BE% D0%B9%D0%BA%D0%B0]вики[url] есть до 300. Мне хватило, чтобы отладить программу.
0
167 / 107 / 22
Регистрация: 02.01.2012
Сообщений: 596
17.07.2017, 18:27 17
YarRainbow, ну ты молодец, конечно, что знаешь формулу товарища Евклида для пифагоровых троек. А вот что не знаешь алгоритм того же товарища Евклида для НОД - это минус
0
0 / 0 / 0
Регистрация: 30.03.2017
Сообщений: 36
17.07.2017, 20:38  [ТС] 18
Огромное спасибо и YarRainbow и Case-Man и
MansMI
за помощь !
А если имеем заданный катет n < 10^8 и необходимо вывести все возможные прямоугольные треугольники ( где a, b, c не обязательно взаимно простые ), этот алгоритм также применим ?
Например, если задан катет 12, то возможны прямоугольные треугольники:
5 12 13 ; 9 12 15; 12 16 20; 12 35 37.
0
Заблокирован
17.07.2017, 20:44 19
так не годится, гипотенуза ограничивает диапазон катетов, а от катета в поисках другого можно вдоль числовой прямой до второго пришествия шагать
0
0 / 0 / 0
Регистрация: 30.03.2017
Сообщений: 36
17.07.2017, 21:11  [ТС] 20
MansMI мне эта задача на олимпиаде попалась, у неё 100% есть решение, но вот какое, это уже другой вопрос. Поэтому и обратился на форум за помощью. Можно сказать наверняка, что катет не может быть больше гипотенузы, но разве этого достаточно для того перебора, будет ли решение оптимально ?
0
17.07.2017, 21:11
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
17.07.2017, 21:11
Помогаю со студенческими работами здесь

Поиск пифагоровых троек в массиве
Привет всем, только начал изучать Си, прошу помоч с решением задачи:&quot;Ввести массив из 14 чисел,...

Найти 20 первых пифагоровых чисел
Найти 20 первых пифагоровых чисел, то есть целых k, l, m таких, что k2 + l2 = m2

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

Найти 20 первых пифагоровых чисел
Найти 20 первых пифагоровых чисел, то есть целых k, l, m таких, что k2 + l2 = m2


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru