Определение пифагорейских троек на основе гипотенузы

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

#Victor C
#Determines if a right triangle with user inputted hypotenuse is capable of being a Pythagorean Triple

import math
triplecheck = True
while True:
    hypotenuse = int(input("Please enter the hypotentuse:")) #Smallest hypotenuse which results in a pythagorean triple is 5.
    if hypotenuse > 4:
        break
c = csqr = hypotenuse**2 #sets two variables to be equivalent to c^^2. c is to be modified to shorten factoring, csqr as a reference to set a value
if c % 2 != 0:   #even, odd check of value c, to create an integer when dividing by half.
    c = (c+1)//2
else:
    c = c//2
for b in range(1,c+1):  #let b^^2 = b || b is equal to each iteration of factors of c^^2, a is set to be remainder of c^^2 minus length b.
    a = csqr-b
    if (math.sqrt(a))%1 == 0 and (math.sqrt(b))%1 == 0: #if squareroots of a and b are both equal to 0, they are integers, therefore fulfilling conditions
       tripleprompt = "You have a Pythagorean Triple, with the lengths of "+str(int(math.sqrt(b)))+", "+str(int(math.sqrt(a)))+" and "+str(hypotenuse)
       print(tripleprompt)
       triplecheck = False
if triplecheck == True:
    print("Sorry, your hypotenuse does not make a Pythagorean Triple.")
11 голосов | спросил Victor C 3 62012vEurope/Moscow11bEurope/MoscowSat, 03 Nov 2012 05:09:31 +0400 2012, 05:09:31

3 ответа


9

Во-первых, давайте напишем это с небольшим стилем и идем оттуда:

import math

def is_triple(hypotenuse):
    """return (a, b, c) if Pythagrean Triple, else None"""
    if hypotenuse < 4:
        return None

    c = hypotenuse ** 2

    for a in xrange(3, hypotenuse):
        b = math.sqrt(c - (a ** 2)) 
        if b == int(b):
            return a, int(b), hypotenuse

    return None

Теперь, я проведу вас через него, построчно, и покажу вам, как я получил это.

Я понятия не имею, эффективнее ли это, но написано в лучшем стиле, что важно рассмотреть.

import math

Всегда помещайте свой импорт в верхнюю часть модуля.

def is_triple(hypotenuse):

Здесь мы скажем 'let's def ine некоторые функции и помещаем в него повторяемый шаблон повторного использования логики. Остальная часть моего ответа вращается вокруг этого и является основным первым шагом к программированию на Python.

def is_triple(hypotenuse):
    """return (a, b, c) if Pythagrean Triple, else None"""

Обратите внимание на тройные кавычки """. Это ваша docstring , что напоминает вам позже то, о чем вы думали, когда вы написал что-то. Постарайтесь сохранить его ниже 65 символов.

if hypotenuse < 4:
    return None

В первой строке def is_triple(hypotenuse):, я прошу пользователя дать мне что-то; переменную, которую я могу использовать позже. Если я позже вызову эту функцию в порядке is_triple(5), я в основном говорю функции, что моя гипотенуза равна 5 , и в остальное время здесь мы назовем его hypotenuse.

c = hypotenuse ** 2

Это действительно все, что вам нужно для этого расчета прямо сейчас.

for a in xrange(3, hypotenuse):
        b = math.sqrt(c - (a ** 2)) 
        if b == int(b):
            return a, int(b), hypotenuse

for a in xrange(3, hypotenuse) в основном говорит для каждого целого числа между 3 и гипотенузой, сделайте то, что я собираюсь написать .

Следуя предыдущему примеру,

>>> range(3, hypotenuse) #hypotenuse is == 5
[3, 4]

Не обращайте внимания на то, что я называю xrange(), он работает так же, как мы здесь, и, что важно, более эффективен.

Итак, теперь, когда мы создали цикл , a будет действовать так, как будто это каждое число в [3, 4] , так что сначала 3:

b = math.sqrt(c -  (a ** 2))
b = math.sqrt(25 - (3 ** 2))
b = math.sqrt(25 - (9))
b = math.sqrt(16)
b = 4.0

Как и на карандаше и бумаге. Заметьте, я положил .0 после, четыре. Это важно здесь:

if b == int(b):

В принципе, int помещает номер b от десятичной до целого числа. Мы просто проверяем, совпадают ли они.

>>> int(4.0)
4
>>> int(4.0) == 4
True

Итак, если число, которое мы получили для b, такое же, как и целое числовое представление b, выполните следующую часть:

return a, int(b), hypotenuse

Что возвращает значение обратно к тому, что вы назвали назначением для вызова функции.

>>> values = is_triple(5)
>>> values
(3, 4, 5)
>>> wrong = is_triple(7)
>>> wrong
>>> #it didn't print anything, because it gave me back None

Наконец, внизу:

return None

Это последнее, что можно поймать, если ничего не произойдет. Очевидно, если вы прошли этот цикл и не получили ответа? Ну, похоже, у тебя нет матча. Верните None, чтобы обозначить это.

Чтобы увидеть эту работу в действии, попробуйте следующее:

>>> import pprint
>>> pprint.pprint([{x: is_triple(x)} for x in xrange(101)])
ответил Droogans 3 62012vEurope/Moscow11bEurope/MoscowSat, 03 Nov 2012 06:21:22 +0400 2012, 06:21:22
5

Простая оптимизация

Вершись на Хороший ответ Droogan , вы можете добавить простую оптимизацию. Действительно, вместо выполнения for a in xrange(3, hypotenuse): вы можете попробовать меньший диапазон.

Кроме того, я воспользовался этой возможностью, чтобы удалить (преждевременное?) оптимизацию о if hypotenuse < 4

Суть заключается в том, чтобы ограничить себя решениями с помощью a <= b (что и делает Droogan, так как это первое решение, d find).

Затем вы можете погрузиться в простую математику и получить:

def is_triple(hypotenuse):
    """return (a, b, c) if Pythagrean Triple, else None"""
    # We have :
    # 0 < a < c and 0 < b < c (egality corresponds to uninteresting solutions).
    # If a = b, 2 * a^2 = c^2, impossible in |N
    # Therefore a != b.
    # We can assume a < b
    # 0 < a^2 < c^2/2 < b^2 < c^2
    c_sqr = hypotenuse ** 2
    for a in xrange(1, int(math.ceil(hypotenuse / math.sqrt(2)))):
        b = math.sqrt(c_sqr - (a ** 2))
        if b == int(b):
            return a, int(b), hypotenuse
    return None

Можно легко проверить, что:

  • у вас одинаковые результаты

  • он быстрее.

Более тонкая оптимизация

Это вдохновлено решением Joel . Он заметил, что как-то факторы 2 могут быть устранены из проблемы и использованы как множитель, когда мы находим решение. Фактически, это даже лучше, чем это, поскольку другие простые числа имеют одно и то же свойство.

В самом деле, согласно свойства примитивных пифагорейских троек a>:

  

Все простые множители с - простые числа вида 4n + 1.

Следовательно, мы можем пройти через простые коэффициенты гипотенузы, и если они не могут быть записаны 4*n + 1, то они должны быть часть мультипликативного фактора.

Таким образом, можно написать что-то вроде:

def prime_factors(n):
    """Yields prime factors of a positive number."""
    assert n > 0
    d = 2
    while d * d <= n:
        while n % d == 0:
            n //= d
            yield d
        d += 1
    if n > 1:  # to avoid 1 as a factor
        assert d <= n
        yield n

def is_triple(hypotenuse):
    """return (a, b, c) if Pythagrean Triple, else None"""
    # We have :
    # 0 < a < c and 0 < b < c.
    # If a = b, 2 * a^2 = c^2, impossible in |N
    # Therefore a != b.
    # We can assume a < b
    # 0 < a^2 < c^2/2 < b^2 < c^2
    if hypotenuse:
        factor = 1
        for prime, power in collections.Counter(prime_factors(hypotenuse)).iteritems():
            if prime % 4 != 1:
                factor *= prime ** power
        c = hypotenuse / factor
        c_sqr = c ** 2
        for a in xrange(1, int(math.ceil(c / math.sqrt(2)))):
            b = math.sqrt(c_sqr - (a ** 2))
            if b == int(b):
                return factor * a, factor * int(b), factor * c

Кажется, что он по крайней мере в 10 раз быстрее, чем код, с которого я начал работать.

Быстрее быстрее

Согласно Википедии :

  

Формула Евклида 1 является фундаментальной формулой для генерации пифагорейских троек при произвольной паре целых положительных чисел m и n с m> п. Формула утверждает, что целые числа

     

a = m ^ 2 - n ^ 2, b = 2mn, c = m ^ 2 + n ^ 2

     

образуют пифагорейскую тройку. Тройка, порожденная формулой Евклида, примитивна тогда и только тогда, когда m и n взаимно просты, а m - n нечетно. Если оба m и n нечетны, то a, b и c будут четными, и поэтому тройка не будет примитивной; однако деление a, b и c на 2 даст примитивную тройку, если m и n взаимно просты. 2

Таким образом, вы можете написать более быстрый код (O (sqrt (c)) вместо O (c)). Обратите внимание, что он может давать разные результаты, чем исходный код. Кроме того, эта оптимизация делает трюк с факторингом несколько менее впечатляющим, и вы легко избавляетесь от него.

def is_triple(hypotenuse):
    """return (a, b, c) if Pythagrean Triple, else None"""
    # We have :
    # a = m^2 - n^2, b = 2mn , c = m^2 + n^2 with m > n > 0
    # c >= 2 * n^2
    # 0 < n <= sqrt(c/2)
    if hypotenuse:
        factor = 1
        for prime, power in collections.Counter(prime_factors(hypotenuse)).iteritems():
            if prime % 4 != 1:
                factor *= prime ** power
        c = hypotenuse / factor
        c_sqr = c ** 2
        for n in xrange(1, int(math.ceil(math.sqrt(c/2)))):
            m = math.sqrt(c - n ** 2)
            if m == int(m):
                m = int(m)
                return factor*(m*m - n*n), 2*m*n*factor, hypotenuse
    return None

Это, по-видимому, в 100 раз быстрее, чем ваш код для значений до 20000 (и чем больше значений, которые вы считаете, тем более драматичным является улучшение).

ответил Josay 16 TueEurope/Moscow2014-12-16T17:27:34+03:00Europe/Moscow12bEurope/MoscowTue, 16 Dec 2014 17:27:34 +0300 2014, 17:27:34
3

Я собираюсь указать на одну вещь, которая является потенциальным источником путаницы. Представьте, что вы вернулись к этому через год, и вы заметили ошибку в одной строке этого кода. Вы хотите исправить эту строку кода, и вы спешите. Вы не будете читать всю функцию, если сможете с ней справиться. Быстрый - что делать a, b, и c означает?

Обычно a, b, и c - это длины сторон. Здесь вы получили их как квадрат длин сторон. Это будет запутать вас, когда вы попытаетесь пересмотреть этот код.

У вас даже уже началось некоторое замешательство - вы установили

c=csqr

Итак, вы думаете о c как о чем-то, и в то же время вы думаете о том же, что и csquared , У вас есть две разные концепции c. Аналогично, ваш комментарий #let b^^2 = b. Это просто просит неприятностей. В ваших комментариях вы явно думаете о b как о чем-то отличном от того, что код думает об этом как. Поэтому в другом месте, где ваши комментарии могут ссылаться на b - это тот же b, который вы имели в виду в своем комментарии ранее, или это версия b теперь в коде? (и обратите внимание, что это действительно b**2, not b^^2). У вас нет бонуса за то, что у вас есть только 3 имени одной переменной.

Если вы хотите выполнять вычисления в квадратичной переменной, используйте asq, bsq и csq. (и подумайте о том, чтобы написать aSquared и т. д., чтобы это стало ясно).

Я написал свою версию, не глядя на другое решение, но на Python должен быть один и только один очевидный способ сделать что-то (хотя, возможно, вам придется быть голландским, чтобы увидеть его). Решения почти идентичны:

def test(hypotenuse):
    factor = 1
    while hypotenuse %2 == 0:
        factor *=2
        hypotenuse/= 2

    hsq = hypotenuse**2

    success = False
    for b in xrange(1,hypotenuse):
        a = math.sqrt(hsq-b**2)
        if a == int(a):
            return sorted([factor*int(a), factor*b, factor*hypotenuse])
    return (None,None,None)



hypotenuse = int(input("Please enter the hypotentuse:"))

(a,b,c) = test(hypotenuse)

if a is None:
    print "failure, utter, utter failure"
else:
    print a, b, c

Единственное реальное отличие заключается в том, что я воспользовался тем, что можно доказать, что у нас есть пифагорейская тройка с четной гипотенузой, а затем разделение на 2 дает новую пифагорейскую тройку.

ответил Joel 16 TueEurope/Moscow2014-12-16T05:10:41+03:00Europe/Moscow12bEurope/MoscowTue, 16 Dec 2014 05:10:41 +0300 2014, 05:10:41

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132