1

我编写了这个程序，它输出总和为某个数字的毕达哥拉斯三元组（这将是参数）。该程序运行完美，但同一个三元组出现多次，我希望一个三元组只出现一次。我想知道是否有人可以帮助我。谢谢！

def pythagoreanCheck(tripletList):
    '''
        Checks whether the three numbers are pythagorean triplet
        returns True or False
    '''

    trip_list = [0,1,2]

    if tripletList[0]**2 + tripletList[1]**2 == tripletList[2]**2:
        return True
    else:
        return False

def givMeSum(target):
    '''
        returns 3 numbers such that their sum is equal to target
    '''       

    listOfa = xrange(1,target)
    listOfb = xrange(1,target)
    listOfc = xrange(1,target)

    for i in listOfa:
        for j in listOfb:
            for k in listOfc:
                add = i + j + k

                if add == target:
                    add_list = [i,j,k]
                    add_list.sort()

                    value = pythagoreanCheck(add_list)

                    if value:
                        print add_list


def main():
    givMeSum(12)

main()
4

3 回答 3

1

这是因为您在嵌套列表中进行计算，然后创建一个由相同数字的 3 个不同排列组成的排序列表。

由于 i、j、k 会输入相同的三个数字的不同组合 3 次，因此 add 每次都会等于 target，这意味着 add_list 被创建并排序了 3 次。这意味着它将创建相同的列表 3 次。

我认为你应该拿出 

add_list.sort()

Siddharth 是对的，您的算法确实效率低下。您正在将其转换为 O(n^3) 算法，如果目标数较大，这可能需要很长时间。

于 2012-11-02T06:20:50.693 回答
0

  1. 考虑将每个元组存储在哈希表（字典）中，而不是在最内层循环中打印它。在所有循环完成结束时，打印散列中的所有值。

  2. 除了您的问题之外，您可以通过创建整数散列并用散列搜索替换最内层循环来使算法更快。

于 2012-11-02T06:20:31.633 回答
0

您需要确保i <= j <= k：

def pythagoreanCheck(tripletList):
    '''
        Checks whether the three numbers are pythagorean triplet
        returns True or False
    '''
    a, b, c = tripletList
    return a**2 + b**2 == c**2

def givMeSum(target):
    '''
        returns 3 numbers such that their sum is equal to target
    '''       

    for i in xrange(1, target):
        for j in xrange(i, target):      # j >= i
            for k in xrange(j, target):  # k >= j   
                if i + j + k == target:
                    add_list = [i, j, k]  # no need to sort any more

                    if pythagoreanCheck(add_list):
                        print add_list


def main():
    givMeSum(12)

main()

如前所述，该算法远非最佳，但这至少可以解决您看到的问题。

这是一个稍微好一点的方法（两个嵌套循环而不是三个）：

def giveMeSum(target):
    '''
        returns 3 numbers such that their sum is equal to target
    '''    
    for i in xrange(1, target):
        for j in xrange(i, target):
            k = target - i - j
            if k < j:
                break  # skip to the next value of i - all remaining js are too big

            add_list = [i, j, k]

            if pythagoreanCheck(add_list):
                print add_list
于 2012-11-02T08:21:45.413 回答