2

トリプルパワーの合計の不変量が何であるかは100％わかりません。

注：nは常に非負の値です。

擬似コード：

triplePower(n)
    i=0
    tot=0
    while i <= n LI1
        j = 0
        while j < i LI2
            k = 0
            while k < i LI3
                tot = tot + i
                k++
            j++
        i++

私はその厄介なことを知っており、はるかに簡単な方法で行うことができますが、これは私が期待していることです（主にアルゴリズム分析の練習のために）。

私は3つのループ不変条件を考え出すことになっています。LI1、LI2、およびLI3。
LI1の場合、不変量はtot =（i ^ 2（i + 1）^ 2）/ 4（0からiまでの立方体の合計の方程式）
と関係があると思います。ただし、LI2またはLI3に対して行います。LI2でのループはi^3を作成し、LI3はi ^ 2を作成しますが、それらをループ不変条件として定義する方法が完全にはわかりません。

whileループ本体のそれぞれに3つの別々の合計変数がある場合、不変条件を定義するのは簡単でしょうか？

あなたが与えることができるどんな助けにも感謝します。

また、この関数の成長の順序は次のとおりです：Θ（n ^ 3）？

4

2 に答える 2

2

合計を段階的に計算するこのようなループに直面した場合、これまでに計算した合計が、考えている合計の最初の部分と等しいかどうかを調べるのに適した不変条件です。この場合、最初のn個の正の完全な立方体の合計を計算し、一度に1つずつ立方体を追加して計算します。したがって、考えられる不変条件の1つは、

tot = sum（jは0からiになります）j 3

さらに、iとnの関係は何ですか？さて、おそらくi≤n+1である必要があります。なぜn+ 1なのですか？これは、最後の反復でi = nの場合でも、とにかくiをインクリメントするためです。これらの2つの不変条件を使用して、このループが正しい値を計算することを証明できます。

ランタイムに関しては、これを非常に簡単に計算できます。まず、各反復でどのくらいの作業が行われていますか？O（1）？の上）？O（n 2）？次に、ループの反復はいくつありますか？O（1）？の上）？O（n 2）？これらの2つの用語の積があなたにあなたの答えを与えるでしょう。

お役に立てれば！

于 2012-02-08T03:43:59.217 に答える
1

アルゴリズムは次のように簡略化できます（C言語の構文に慣れているといいのですが）。

tot = 0;
for ( i = 0 ; i <= n ; i ++ )
    for ( j = 0 ; j < i ; j ++ )
        for ( k = 0 ; k < i ; k ++ )
            tot = tot + i;

そして、それをシグマ表記に変換することができます。

ここに画像の説明を入力してください

于 2014-04-15T14:31:24.533 に答える