Генерация уникальных, упорядоченных пифагорейских триплетов

Question

Это программа, которую я написал для вычисления пифагорейских триплетов. Когда я запускаю программу, она печатает каждый набор триплетов дважды из-за оператора if. Можно ли как-то сказать программе, чтобы новый набор триплетов печатался только один раз? Спасибо.

import math

def main():
    for x in range (1, 1000):
        for y in range (1, 1000):
            for z in range(1, 1000):
                if x*x == y*y + z*z:
                    print y, z, x
                    print '-'*50

if __name__ == '__main__':
    main()  

Answer 1

Да, есть.

Хорошо, теперь вы хотите знать, почему. Почему бы просто не ограничить это так, чтобы z> y? Попробуйте

for z in range (y+1, 1000)

Answer 2

Вы можете попробовать это

  triplets=[]
    for a in range(1,100):
        for b in range(1,100):
            for c in range(1,100):
                if  a**2 + b**2==c**2:
                    i=[a,b,c]
                    triplets.append(i)
                    for i in triplets:
                          i.sort()
                          if triplets.count(i)>1:
                              triplets.remove(i)
    print(triplets)

Answer 3

# To find all pythagorean triplets in a range
import math
n = int(input('Enter the upper range of limit'))
for i in range(n+1):
    for j in range(1, i):
        k = math.sqrt(i*i + j*j)
        if k % 1 == 0 and k in range(n+1):
            print(i,j,int(k))

Answer 4

Следует отметить, что для a, b и c вам не нужно проходить цикл до N.

Для a вам нужно только выполнить цикл от 1 до int(sqrt(n**2/2))+1, для b от a+1 до int(sqrt(n**2-a**2))+1 и для c от int(sqrt(a**2+b**2) до int(sqrt(a**2+b**2)+2.

Answer 5

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

Ullong - это unsigned long long, и я создал несколько функций для получения квадрата и корня моя корневая функция в основном сказала, что если квадратный корень из заданного числа (после его целого числа (целого)) в квадрате не равно числу, то получим -1, потому что он не является рутируемым. _square и _root работают так, как ожидалось, как описано выше, я знаю другой способ его оптимизации, но я еще этого не делал и не проверял.

generate(vector<Triple>& triplist, ullong limit) {
cout<<"Please wait as triples are being generated."<<endl;
register ullong a, b, c;
register Triple trip;
time_t timer = time(0);

for(a = 1; a <= limit; ++a) {
    for(b = a + 1; b <= limit; ++b) {
        c = _root(_square(a) + _square(b));

        if(c != -1 && c <= limit) {
            trip.a = a; trip.b = b; trip.c = c;

            triplist.push_back(trip);

        } else if(c > limit)
            break;
    }
}

timer = time(0) - timer;
cout<<"Generated "<<triplist.size()<<" in "<<timer<<" seconds."<<endl;
cin.get();
cin.get();

}

Дайте мне знать, что вы все думаете. Он генерирует все примитивные и не примитивные тройки в соответствии с учителем, для которого я сдал его. (она проверила до 100, если я правильно помню).

Результаты из v4, предоставленные предыдущим кодером здесь:

Ниже приведен не очень научный набор моментов времени (использующий Java под Eclipse на моем старом ноутбуке с запущенным другим оборудованием ...), где «use x, y, z» было реализовано путем создания экземпляра объекта Triple с три значения и положить его в ArrayList. (Для этих прогонов N было установлено равным 10000, что в каждом случае составляло 12 471 тройку.)

Версия 4: 46 сек. используя квадратный корень: 134 сек. массив и карта: 400 сек.

мой результат Сколько троек сгенерировать: 10000

Пожалуйста, подождите, пока генерируются тройки. Сгенерировано 12471 за 2 секунды.

То есть, прежде чем я даже начну оптимизацию через компилятор. (Я помню, как раньше получал 10000 до 0 секунд с кучей специальных опций и прочего). Мой код также генерирует все тройки с 100 000 в качестве предела того, насколько высок side1,2, hyp может пройти за 3,2 минуты (я думаю, ограничение в 1 000 000 занимает час).

Я немного изменил код и получил ограничение в 10000 до 1 секунды (без оптимизации). Вдобавок к этому, при тщательном осмыслении мой может быть разбит на куски и нарезан на заданные диапазоны (например, 100 000 делятся на 4 равных блока для 3 процессоров (1 дополнительный, чтобы надеяться потреблять время процессора на всякий случай) с диапазонами от 1 до 25 000 (начните с 1 и ограничьте его до 25 000), от 25 000 до 50 000, от 50 000 до 75 000 и до 75 000 до конца. Я могу сделать это и посмотреть, не ускорит ли это что-либо (у меня будут предварительно подготовленные потоки, и я не буду включать их в фактическую сумму времени для выполнения тройной функции. Мне нужен более точный таймер и способ конкатенации векторов. Я думаю, что если 1 3,4 ГГц процессор с 8 ГБ оперативной памяти в своем распоряжении может сделать 10000 как лим в 1 секунду, чем 3 процессора должен сделать это за 1/3 секунды (и я округляю до более высокой секунды, как есть).

Answer 6

Версия 5 для Джоэла Нили.

Поскольку X может быть максимумом «N-2», а Y может быть максимумом «N-1» для диапазона 1..N. Поскольку Z max равно N, а Y max равно N-1, X может быть максимумом Sqrt (N * N - (N-1) * (N-1)) = Sqrt (2 * N - 1) и может начинаться с 3 .

MaxX = ( 2 * N - 1 ) ** 0.5

for x in 3..MaxX {
  y = x+1
  z = y+1
  m = x*x + y*y
  k = z * z
  while z <= N {
     while k < m {
        z = z + 1
        k = k + (2*z) - 1
    }
    if k == m and z <= N then {
        // use x, y, z
    }
    y = y + 1
    m = m + (2 * y) - 1
  }
 }