1

私は、合計が特定の数（これがパラメーターになります）であるピタゴラスのトリプレットを出力するこのプログラムを作成しました。プログラムは完全に実行されますが、同じトリプレットが複数回表示されます。1 つのトリプレットを 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 つの数値の異なる組み合わせを 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()

前述のように、このアルゴリズムは最適とは言えませんが、少なくとも現在の問題は解決されます。

これは少し良い方法です (3 つではなく 2 つのネストされたループ):

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 に答える