5

クラスの割り当てとして、与えられた値 't' よりも低いすべてのピタゴラス数を生成する C プログラムを作成します。最初にEuclid の Formulaを使用してプリミティブ トリプレット (a, b, c) を生成し、1 < kc < t の形式 (ka, kb, kc) のすべてのトリプレットを出力するコードを次に示します。

for (i = 2; i < (sqrt(t) + 1); i++)
    for (j = 1; j < i; j++)
        if ((gcd(i,j) == 1) && ((i-j) % 2) && ((i*i + j*j) < t))
        {
            k = 0;
            a = i * i - j * j;
            b = 2 * i * j;
            c = i * i + j * j;

            while ((++k) * c < t)
                printf("(%d, %d, %d)\n", k*a, k*b, k*c);
        }

私が遭遇した他のほとんどのアルゴリズムは、ネストされたループを使用して平方和をチェックし、t が大きくなるにつれてこれよりも大幅に遅くなります。実際に高速であるという証拠を推測することは可能ですか?

4

2 に答える 2

3

アルゴリズムの複雑さは、アルゴリズムのパフォーマンスを分析するための一般的な方法です。特に、big Oは、各アルゴリズムの最悪のケースの状況に基づいてアルゴリズムを比較するためによく使用されます。

あなたの場合、4つのループがあります：

  • for徹底的に反復するi
  • for徹底的に反復するj
  • 内側のループgcd
  • whileループ_

最悪の場合、これらのループのそれぞれがsqrt(t)反復を実行します。大きな O の複雑さは次のようになります。

O(for_i) * O(for_j) * (O(gcd) + O(while))
=
O(sqrt(t)) * O(sqrt(t)) * (O(sqrt(t)) + O(sqrt(t)))
=
O(t*sqrt(t))

メソッドよりも遅い他のアルゴリズムの場合。同じ推論を適用して彼らの大きな O を見つけ、この大きな O があなたのものよりも大きいことを示すことができます。たとえば、すべての平方和をチェックする素朴なアルゴリズムには、2 つのネストされたループがあります。それぞれtの反復回数は最大であるため、大きな O はO(t*t) > O(t*sqrt(t))です。

于 2013-08-18T01:26:11.337 に答える
1

ユークリッドのアルゴリズムの代替として、(a, b, c) が原始ピタゴラスの三重体である場合、(a-2b+2c, 2a-b+2c, 2a-2b+3c), (a+2b+2c, 2a+b+2c, 2a+2b+3c) および (-a+2b+2c, -2a+b+2c, -2a+2b+3c)。Python のアルゴリズムは次のとおりです (たまたま Python のアルゴリズムを持っていたので、C で書き直すのが面倒なので、とにかく、それはあなたの宿題です):

def pyth(n):
    def p(a, b, c):
        if n < a + b + c: return []
        return ([[a, b, c]] if a < b else [[b, a, c]]) \
             + p(a-b-b+c+c, a+a-b+c+c, a+a-b-b+c+c+c) \
             + p(a+b+b+c+c, a+a+b+c+c, a+a+b+b+c+c+c) \
             + p(c+c+b+b-a, c+c+b-a-a, c+c+c+b+b-a-a)
    return p(3, 4, 5)

次に、制限に達するまで、各プリミティブ三角形に連続する定数を掛けるのは簡単です。これが Euclid のアルゴリズムよりも速いかどうかはわかりませんが、gcd 計算がないためであることを願っています。

于 2013-08-18T11:54:22.863 に答える