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

Ответ 1

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

(Я буду придерживаться псевдокода, чтобы избежать языковых предубеждений, и чтобы оптимизировать псевдокод, я не буду оптимизировать несколько вычислений, например x * x и y * y.)

Версия 1:

for x in 1..N {
    for y in 1..N {
        for z in 1..N {
            if x * x + y * y == z * z then {
                // use x, y, z
            }
        }
    }
}

- худшее решение. Он генерирует дубликаты и обходит части пространства, которые не являются полезными (например, каждый раз, когда z < y). Его временная сложность является кубической на N.

Версия 2, первое улучшение происходит из-за необходимости удерживать x < y < z, как в:

for x in 1..N {
    for y in x+1..N {
        for z in y+1..N {
            if x * x + y * y == z * z then {
                // use x, y, z
            }
        }
    }
}

что сокращает время выполнения и устраняет дублированные решения. Однако он все еще кубичен на N; улучшение является лишь уменьшением коэффи- циента N -куба.

Бессмысленно продолжать изучение возрастающих значений z после того, как z * z < x * x + y * y больше не выполняется. Этот факт мотивирует Версия 3, первый шаг от итерации грубой силы над z:

for x in 1..N {
    for y in x+1..N {
        z = y + 1
        while z * z < x * x + y * y {
            z = z + 1
        }
        if z * z == x * x + y * y and z <= N then {
            // use x, y, z
        }
    }
}

Для N 1000, это примерно в 5 раз быстрее, чем версия 2, но она все еще кубическая на N.

Следующее понимание состоит в том, что x и y являются единственными независимыми переменными; z зависит от их значений, а последнее значение z, рассмотренное для предыдущего значения y, является хорошим стартовым значением поиска для следующего значения y. Это приводит к Версия 4:

for x in 1..N {
    y = x+1
    z = y+1
    while z <= N {
        while z * z < x * x + y * y {
            z = z + 1
        }
        if z * z == x * x + y * y and z <= N then {
            // use x, y, z
        }
        y = y + 1
    }
}

который позволяет y и z "прокручивать" значения выше x только один раз. Он не только более чем в 100 раз быстрее для N 1000, он квадратичен на N, поэтому ускорение увеличивается с ростом N.

Я часто сталкивался с таким улучшением, чтобы недоверчиво относиться к "подсчетным циклам" для любых, но наиболее тривиальных применений (например, для перемещения массива).

Обновление: Очевидно, я должен был указать несколько вещей о V4, которые легко упускать из виду.

• Оба петель while управляются значением z (одно прямо, другое косвенно через квадрат z). Внутренний while фактически ускоряет внешний while, а не ортогонален ему. Важно посмотреть, что делают циклы, а не просто подсчитывать количество циклов.

• Все вычисления в V4 строго арифметичны. Преобразование в/из плавающей точки, а также вычисления с плавающей запятой являются дорогостоящими по сравнению.

• V4 работает в постоянной памяти, требуя только трех целых переменных. Нет никаких массивов или хеш-таблиц для выделения и инициализации (и, возможно, для возникновения ошибки вне памяти).

• Исходный вопрос позволил варьировать все x, y и x в том же диапазоне. V1..V4 следовал за этим шаблоном.

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

Version 4:           46 sec.
using square root:  134 sec.
array and map:      400 sec.

Алгоритм "массив и карта" по существу:

squares = array of i*i for i in 1 .. N
roots = map of i*i -> i for i in 1 .. N
for x in 1 .. N
    for y in x+1 .. N
        z = roots[squares[x] + squares[y]]
        if z exists use x, y, z

Алгоритм "использование квадратного корня" по существу:

for x in 1 .. N
    for y in x+1 .. N
        z = (int) sqrt(x * x + y * y)
        if z * z == x * x + y * y then use x, y, z

Фактический код для V4:

public Collection<Triple> byBetterWhileLoop() {
    Collection<Triple> result = new ArrayList<Triple>(limit);
    for (int x = 1; x < limit; ++x) {
        int xx = x * x;
        int y = x + 1;
        int z = y + 1;
        while (z <= limit) {
            int zz = xx + y * y;
            while (z * z < zz) {++z;}
            if (z * z == zz && z <= limit) {
                result.add(new Triple(x, y, z));
            }
            ++y;
        }
    }
    return result;
}

Обратите внимание, что x * x вычисляется во внешнем цикле (хотя я не стал кэшировать z * z); аналогичные оптимизации выполняются в других вариантах.

Я буду рад предоставить исходный код Java по запросу для других измененных мною вариантов, если я ничего не реализовал.

Ответ 2

Значительно быстрее, чем любое из решений до сих пор. Находит триплеты через тройное дерево.

Wolfram говорит:

Hall (1970) и Roberts (1977) доказывают, что это примитивная пифагорейская тройка тогда и только тогда, когда

(a,b,c)=(3,4,5)M

где M - конечное произведение матриц U, A, D.

И там у нас есть формула для генерации каждой примитивной тройки.

В приведенной выше формуле гипотенуза постоянно растет, поэтому довольно легко проверить максимальную длину.

В Python:

import numpy as np

def gen_prim_pyth_trips(limit=None):
    u = np.mat(' 1  2  2; -2 -1 -2; 2 2 3')
    a = np.mat(' 1  2  2;  2  1  2; 2 2 3')
    d = np.mat('-1 -2 -2;  2  1  2; 2 2 3')
    uad = np.array([u, a, d])
    m = np.array([3, 4, 5])
    while m.size:
        m = m.reshape(-1, 3)
        if limit:
            m = m[m[:, 2] <= limit]
        yield from m
        m = np.dot(m, uad)

Если вам нужны все троицы, а не только примитивы:

def gen_all_pyth_trips(limit):
    for prim in gen_prim_pyth_trips(limit):
        i = prim
        for _ in range(limit//prim[2]):
            yield i
            i = i + prim

list(gen_prim_pyth_trips(10**4)) потребовалось 2,81 миллисекунды, чтобы вернуться с 1593 элементами, а list(gen_all_pyth_trips(10**4)) заняло 19,8 миллисекунды, чтобы вернуться с 12471 элементами

Для справки принятый ответ (на python) занял 38 секунд для 12471.

Просто для удовольствия, установив верхний предел на миллион list(gen_all_pyth_trips(10**6)), возвращается в 2.66 секунды с элементами 1980642 (почти 2 миллиона троек за 3 секунды). list(gen_all_pyth_trips(10**7)) переносит мой компьютер на колени, так как список становится настолько большим, что он потребляет каждый бит бит. Выполнение чего-то вроде sum(1 for _ in gen_all_pyth_trips(10**7)) обходит это ограничение и возвращается через 30 секунд с помощью 23471475 элементов.

Дополнительные сведения об используемом алгоритме см. в статьях Wolfram и Wikipedia.

Ответ 3

Вы должны определить x < y < г.

for x in range (1, 1000):
    for y in range (x + 1, 1000):
            for z in range(y + 1, 1000):

Еще одна хорошая оптимизация - использовать только x и y и вычислить zsqr = x * x + y * y. Если zsqr - квадратное число (или z = sqrt (zsqr) - целое число), это триплет, иначе нет. Таким образом, вам нужно всего две петли вместо трех (для вашего примера, примерно в 1000 раз быстрее).

Ответ 4

Ранее перечисленные алгоритмы генерации пифагорейских триплетов являются модификациями наивного подхода, основанного на базовом соотношении a^2 + b^2 = c^2, где (a, b, c) триплет положительных целых чисел. Оказывается, что пифагорейские триплеты удовлетворяют некоторым довольно замечательным отношениям, которые могут быть использованы для генерации всех пифагорейских триплетов.

Euclid обнаружил первые такие отношения. Он определил, что для каждой пифагорейской тройки (a, b, c), возможно, после переупорядочения a и b существуют относительно простые положительные целые числа m и n с m > n, по крайней мере одно из которых четно и положительное целое число k такое, что

a = k (2mn)
b = k (m^2 - n^2)
c = k (m^2 + n^2)

Затем для генерации пифагорейских триплетов генерируем относительно простые натуральные целые числа m и n различной четности и положительное целое число k и применяем приведенную выше формулу.

struct PythagoreanTriple {
    public int a { get; private set; }
    public int b { get; private set; }
    public int c { get; private set; }

    public PythagoreanTriple(int a, int b, int c) : this() {
        this.a = a < b ? a : b;
        this.b = b < a ? a : b;
        this.c = c;
    }

    public override string ToString() {
        return String.Format("a = {0}, b = {1}, c = {2}", a, b, c);
    }

    public static IEnumerable<PythagoreanTriple> GenerateTriples(int max) {
        var triples = new List<PythagoreanTriple>();
        for (int m = 1; m <= max / 2; m++) {
            for (int n = 1 + (m % 2); n < m; n += 2) {
                if (m.IsRelativelyPrimeTo(n)) {
                    for (int k = 1; k <= max / (m * m + n * n); k++) {
                        triples.Add(EuclidTriple(m, n, k));
                    }
                }
            }
        }

        return triples;
    }

    private static PythagoreanTriple EuclidTriple(int m, int n, int k) {
        int msquared = m * m;
        int nsquared = n * n;
        return new PythagoreanTriple(k * 2 * m * n, k * (msquared - nsquared), k * (msquared + nsquared));
    }
}

public static class IntegerExtensions {
    private static int GreatestCommonDivisor(int m, int n) {
        return (n == 0 ? m : GreatestCommonDivisor(n, m % n));
    }

    public static bool IsRelativelyPrimeTo(this int m, int n) {
        return GreatestCommonDivisor(m, n) == 1;
    }
}

class Program {
    static void Main(string[] args) {
        PythagoreanTriple.GenerateTriples(1000).ToList().ForEach(t => Console.WriteLine(t));            
    }
}

Статья Википедии о Формулы для создания пифагорейских троек содержит другие такие формулы.

Ответ 5

Алгоритмы могут быть настроены на скорость, использование памяти, простоту и другие вещи.

Вот алгоритм pythagore_triplets, настроенный для скорости, за счет использования памяти и простоты. Если все, что вам нужно, это скорость, это может быть путь.

Вычисление list(pythagore_triplets(10000)) занимает 40 секунд на моем компьютере, против 63 секунд для алгоритма ΤΖΩΤΖΙΟΥ и, возможно, дней вычисления для алгоритма Тафкаса (и всех других алгоритмов, которые используют 3 встроенных цикла вместо 2).

def pythagore_triplets(n=1000):
   maxn=int(n*(2**0.5))+1 # max int whose square may be the sum of two squares
   squares=[x*x for x in xrange(maxn+1)] # calculate all the squares once
   reverse_squares=dict([(squares[i],i) for i in xrange(maxn+1)]) # x*x=>x
   for x in xrange(1,n):
     x2 = squares[x]
     for y in xrange(x,n+1):
       y2 = squares[y]
       z = reverse_squares.get(x2+y2)
       if z != None:
         yield x,y,z

>>> print list(pythagore_triplets(20))
[(3, 4, 5), (5, 12, 13), (6, 8, 10), (8, 15, 17), (9, 12, 15), (12, 16, 20)]

Обратите внимание, что если вы собираетесь рассчитать первый миллиард триплетов, то этот алгоритм сработает до того, как он даже начнется из-за ошибки из памяти. Таким образом, алгоритм ΤΖΩΤΖΙΟΥ, вероятно, является более безопасным выбором для больших значений n.

Кстати, вот алгоритм Тафкаса, переведенный на python для моих тестов производительности. Его недостаток состоит в том, чтобы потребовать 3 цикла вместо 2.

def gcd(a, b):
  while b != 0:
    t = b
    b = a%b
    a = t
  return a

def find_triple(upper_boundary=1000):
  for c in xrange(5,upper_boundary+1):
    for b in xrange(4,c):
      for a in xrange(3,b):
        if (a*a + b*b == c*c and gcd(a,b) == 1):
          yield a,b,c

Ответ 6

def pyth_triplets(n=1000):
    "Version 1"
    for x in xrange(1, n):
        x2= x*x # time saver
        for y in xrange(x+1, n): # y > x
            z2= x2 + y*y
            zs= int(z2**.5)
            if zs*zs == z2:
                yield x, y, zs

>>> print list(pyth_triplets(20))
[(3, 4, 5), (5, 12, 13), (6, 8, 10), (8, 15, 17), (9, 12, 15), (12, 16, 20)]

Алгоритм V.1 имеет монотонно возрастающие значения x.

ИЗМЕНИТЬ

Кажется, этот вопрос все еще жив:)
Поскольку я вернулся и снова просмотрел код, я попробовал второй подход, который почти в 4 раза быстрее (около 26% времени процессора для N = 10000) в качестве моего предыдущего предложения, поскольку он позволяет избежать множества ненужных вычислений:

def pyth_triplets(n=1000):
    "Version 2"
    for z in xrange(5, n+1):
        z2= z*z # time saver
        x= x2= 1
        y= z - 1; y2= y*y
        while x < y:
            x2_y2= x2 + y2
            if x2_y2 == z2:
                yield x, y, z
                x+= 1; x2= x*x
                y-= 1; y2= y*y
            elif x2_y2 < z2:
                x+= 1; x2= x*x
            else:
                y-= 1; y2= y*y

>>> print list(pyth_triplets(20))
[(3, 4, 5), (6, 8, 10), (5, 12, 13), (9, 12, 15), (8, 15, 17), (12, 16, 20)]

Обратите внимание, что этот алгоритм имеет увеличенные значения z.

Если алгоритм был преобразован в C, где, будучи ближе к металлу, умножения занимают больше времени, чем дополнения, можно было бы минимализовать необходимые умножения, учитывая, что шаг между последовательными квадратами:

(x + 1) ² - x² = (x + 1) (x + 1) - x² = x² + 2x + 1 - x² = 2x + 1

поэтому все внутренние x2= x*x и y2= y*y будут преобразованы в дополнения и вычитания, такие как:

def pyth_triplets(n=1000):
    "Version 3"
    for z in xrange(5, n+1):
        z2= z*z # time saver
        x= x2= 1; xstep= 3
        y= z - 1; y2= y*y; ystep= 2*y - 1
        while x < y:
            x2_y2= x2 + y2
            if x2_y2 == z2:
                yield x, y, z
                x+= 1; x2+= xstep; xstep+= 2
                y-= 1; y2-= ystep; ystep-= 2
            elif x2_y2 < z2:
                x+= 1; x2+= xstep; xstep+= 2
            else:
                y-= 1; y2-= ystep; ystep-= 2

Конечно, в Python дополнительный байт-код, произведенный фактически замедляет алгоритм по сравнению с версией 2, но я бы поставил (не проверяя:), что V.3 быстрее в C.

Приветствует всех:)

Ответ 7

Я просто протянул Кайла Гуллиона, чтобы троицы были отсортированы по гипотенузу, затем самой длинной стороне.

Он не использует numpy, но требует SortedCollection (или SortedList), например этот

def primitive_triples():
""" generates primitive Pythagorean triplets x<y<z
sorted by hypotenuse z, then longest side y
through Berggren matrices and breadth first traversal of ternary tree
:see: https://en.wikipedia.org/wiki/Tree_of_primitive_Pythagorean_triples
"""
key=lambda x:(x[2],x[1])
triples=SortedCollection(key=key)
triples.insert([3,4,5])
A = [[ 1,-2, 2], [ 2,-1, 2], [ 2,-2, 3]]
B = [[ 1, 2, 2], [ 2, 1, 2], [ 2, 2, 3]]
C = [[-1, 2, 2], [-2, 1, 2], [-2, 2, 3]]

while triples:
    (a,b,c) = triples.pop(0)
    yield (a,b,c)

    # expand this triple to 3 new triples using Berggren matrices
    for X in [A,B,C]:
        triple=[sum(x*y for (x,y) in zip([a,b,c],X[i])) for i in range(3)]
        if triple[0]>triple[1]: # ensure x<y<z
            triple[0],triple[1]=triple[1],triple[0]
        triples.insert(triple)

def triples():
""" generates all Pythagorean triplets triplets x<y<z 
sorted by hypotenuse z, then longest side y
"""
prim=[] #list of primitive triples up to now
key=lambda x:(x[2],x[1])
samez=SortedCollection(key=key) # temp triplets with same z
buffer=SortedCollection(key=key) # temp for triplets with smaller z
for pt in primitive_triples():
    z=pt[2]
    if samez and z!=samez[0][2]: #flush samez
        while samez:
            yield samez.pop(0)
    samez.insert(pt)
    #build buffer of smaller multiples of the primitives already found
    for i,pm in enumerate(prim):
        p,m=pm[0:2]
        while True:
            mz=m*p[2]
            if mz < z:
                buffer.insert(tuple(m*x for x in p))
            elif mz == z: 
                # we need another buffer because next pt might have
                # the same z as the previous one, but a smaller y than
                # a multiple of a previous pt ...
                samez.insert(tuple(m*x for x in p))
            else:
                break
            m+=1
        prim[i][1]=m #update multiplier for next loops
    while buffer: #flush buffer
        yield buffer.pop(0)
    prim.append([pt,2]) #add primitive to the list

код доступен в math2 module мой Python библиотека. Он протестирован на некоторых сериях OEIS (код здесь внизу), что только позволило мне найти ошибку в A121727: -)

Ответ 8

Я написал эту программу в Ruby и это похоже на реализацию python. Важная строка:

if x*x == y*y + z*z && gcd(y,z) == 1:

Затем вам нужно реализовать метод, который возвращает наибольший общий делитель (gcd) двух заданных чисел. Очень простой пример в Ruby:

def gcd(a, b)
    while b != 0
      t = b
      b = a%b
      a = t
    end
    return a
end

Полный метаморфизм Ruby для поиска триплетов будет следующим:

def find_triple(upper_boundary)

  (5..upper_boundary).each {|c|
    (4..c-1).each {|b|
      (3..b-1).each {|a|
        if (a*a + b*b == c*c && gcd(a,b) == 1)
          puts "#{a} \t #{b} \t #{c}"
        end
      }
    }
  }
end

Ответ 9

Старый вопрос, но я все равно буду вводить свои вещи. Существует два общих способа создания уникальных пифагорейских троек. One Is by Scaling, а другой - с помощью этой архаичной формулы.

Что такое масштабирование, в основном он принимает константу n, а затем умножает базовую тройку, скажем, 3,4,5 на n. Поэтому, беря n, чтобы быть 2, мы получаем 6,8,10 нашей следующей тройки.

масштабировании

def pythagoreanScaled(n):
    triplelist = []
    for x in range(n):
        one = 3*x
        two = 4*x
        three = 5*x
        triple = (one,two,three)
        triplelist.append(triple)
return triplelist

Метод формулы использует тот факт, что если мы возьмем число x, вычислим 2m, m ^ 2 + 1 и m ^ 2-1, эти три всегда будут пифагорейским триплетом.

Формула

def pythagoreantriple(n):
    triplelist = []
    for x in range(2,n):
        double = x*2
        minus = x**2-1
        plus = x**2+1
        triple = (double,minus,plus)
        triplelist.append(triple)
    return triplelist

Ответ 10

Да, есть.

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

for z in range (y+1, 1000)

Ответ 11

from  math import sqrt
from itertools import combinations

#Pythagorean triplet - a^2 + b^2 = c^2 for (a,b) <= (1999,1999)
def gen_pyth(n):
if n >= 2000 :
  return
ELEM =   [  [ i,j,i*i + j*j ] for i , j in list(combinations(range(1, n +   1 ), 2)) if sqrt(i*i + j*j).is_integer() ]
print (*ELEM , sep = "\n")


gen_pyth(200)

Ответ 12

for a in range(1,20):
    for b in range(1,20):
        for c in range(1,20):
            if a>b and c and c>b:
                if a**2==b**2+c**2:
                    print("triplets are:",a,b,c)

Ответ 13

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

Так как X может быть макс 'N-2', а Y может быть макс 'N-1' для диапазона 1..N. Поскольку Z max - N и Y max - N-1, X может быть max 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
  }
 }

Ответ 14

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

ullong беззнаковый длинный, и я создал пару функций для квадратов и корней моя корневая функция в основном говорила, если квадратный корень из заданного числа (после создания целого числа (целочисленный)) в квадрате, не равном числу, дает тогда return -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 было установлено в 10 000, что дало 12 471 тройку в каждом случае.)

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

Результаты моего исследования Сколько троек для генерации: 10000

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

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

Я немного изменил код и получил ограничение 10 000 до 1 секунды (без оптимизации). Кроме того, с осторожным мышлением моя могла быть разбита на куски и нарезана на заданные диапазоны (например, 100 000 разделить на 4 равных куска для 3 cpu (1 дополнительный, чтобы надеяться, потреблять время процессора на всякий случай) с диапазонами от 1 до 25 000 (начинаются с 1 и ограничивают это до 25 000), от 25 000 до 50 000, от 50 000 до 75 000 и до 75 000. Я могу сделать это и посмотреть, ускорит ли он его (у меня будут готовые темы и не включать их в фактическую сумму времени, чтобы выполнить тройную функцию.Мне нужен более точный таймер и способ конкатенировать векторы.Я думаю, что если 1 3.4 ГГц cpu с 8 gb бара в нем может сделать 10000 как lim за 1 секунду, а затем 3 cpus должен делать это в 1/3 секунды (и я раунд до более высокой секунды, как и atm).

Ответ 15

Следует отметить, что для 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.

Ответ 16

# 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))

Ответ 17

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

  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)

Ответ 18

Вы должны использовать Евклидово доказательство трифлетов Пифагора. Следуйте ниже...

Вы можете выбрать любое произвольное число больше нуля, скажем, m,n

Согласно Евклиду, триплет будет a(m*m-n*n), b(2*m*n), c(m*m+n*n)

Теперь примените эту формулу, чтобы узнать триплеты, скажем, наше одно значение триплета равно 6, а другие два? Хорошо, давайте решим...

a(m*m-n*n), b(2*m*n), c(m*m+n*n)

Уверен, что b(2*m*n) явно четный. Так что теперь

(2*m*n)=6 =>(m*n)=3 =>m*n=3*1 =>m=3,n=1

U может принимать любое другое значение, а не 3 и 1, но эти два значения должны содержать произведение двух чисел, которое равно 3 (m*n=3)

Теперь, когда m=3 и n=1 Тогда,

a(m*m-n*n)=(3*3-1*1)=8, c(m*m-n*n)=(3*3+1*1)=10

6,8,10 - это наш триплет для ценности, это наша визуализация того, как генерировать триплеты.

если данное число нечетное, как (9), то здесь слегка изменено, потому что b(2*m*n)

никогда не будет странным. Итак, здесь мы должны взять

a(m*m-n*n)=7, (m+n)*(m-n)=7*1, So, (m+n)=7, (m-n)=1

Теперь найдите m и n отсюда, а затем найдите два других значения.

Если вы этого не понимаете, внимательно прочитайте его.

Делайте код в соответствии с этим, он будет эффективно генерировать различные триплеты.