0 / 0 / 0
Регистрация: 30.03.2017
Сообщений: 36
|
|
1 | |
Задача о Пифагоровых тройках17.07.2017, 15:37. Показов 4111. Ответов 22
Метки нет (Все метки)
Добрый день. Думаю, многие решали эту задачу просто методом перебора для небольших значений. В данном случае, необходимо при заданном c (гипотенуза) найти все тройки взаимно простых чисел a, b, c, таких, что a*a + b*b = c*c.
При 0 < с < 10^6. Как ни крутил, не выходит O(n), быть может, есть какая-то математическая хитрость. Заранее спасибо !
0
|
17.07.2017, 15:37 | |
Ответы с готовыми решениями:
22
Найти общее решение в примитивных тройках уравнения: x^2-y^2=z^n Поиск пифагоровых троек Генерация Пифагоровых троек Расчет Пифагоровых троек |
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 |
0
|
Заблокирован
|
||||||
17.07.2017, 16:22 | 5 | |||||
может так, не проверял
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
|
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
|
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 |
Ну Вы странный перебор устроили.. Примитивная тройка всегда представима в виде
Где m и n разной чётности и взаимно просты. Так что перебор нужно только до c, а не до с2. Если с до 10e6, можно предварительно построить массив из тысячи квадратов
0
|
68 / 51 / 27
Регистрация: 27.04.2015
Сообщений: 203
|
||||||
17.07.2017, 18:21 | 14 | |||||
Попробовал написать, как я предлагал выше. Тестируйте.
Добавлено через 9 минут UPD замерил наскоряк, у меня даже при {10}^{7} получается меньше секунды
1
|
Заблокирован
|
||||||
17.07.2017, 18:24 | 15 | |||||
добрался до VS , а какие нибудь контрольные гипотенузы есть? а то ничего кроме 5 на ум не приходит, 999997 вроде считает
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
|
0 / 0 / 0
Регистрация: 30.03.2017
Сообщений: 36
|
|
17.07.2017, 21:11 [ТС] | 20 |
MansMI мне эта задача на олимпиаде попалась, у неё 100% есть решение, но вот какое, это уже другой вопрос. Поэтому и обратился на форум за помощью. Можно сказать наверняка, что катет не может быть больше гипотенузы, но разве этого достаточно для того перебора, будет ли решение оптимально ?
0
|
17.07.2017, 21:11 | |
17.07.2017, 21:11 | |
Помогаю со студенческими работами здесь
20
Поиск пифагоровых троек в массиве Найти 20 первых пифагоровых чисел доказательства свойств Пифагоровых троек Найти 20 первых пифагоровых чисел Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |