1

次のように、複数 (N) のネストされたループがあります。

int k = 0;
for (int i1 = 0; i1 < n; i1++)
{
  for (int i2 = 0; i2 <= i1; i2++)
  {
    for (int i3 = 0; i3 <= i2; i3++)
    {
       ...
            for (int iN = 0; iN <= i{N-1}; iN++)
            { 
              k++;
              //k = f(i1, ... , iN);
            }
    } 
  } 
}

、...、 にk基づいてループ内に入る式が必要です。i1iN

の場合N=1:k=f(i1)=i1

の場合N=2:k=f(i1,i2)=i1*(i1+1)/2+i2

4

2 に答える 2

0

一般に、ネストされた sum があります。

sum(sum(sum(1,i3=0..i2),i2=0..i1),i1=0..n-1)

これらの基本的な総和の公式を使用して、内側から単純化できます。izomorphius がコメントしたように、最終結果は N にのみ依存します。N は i1 の上限であり、i2 の上限です...

編集：わかりました、あなたの編集で、あなたは別の問題を念頭に置いていることがわかりました。今はもう少し複雑ですが、それでも問題ありません。

これにはいくつかのものを分割する必要があります。値 k= f(4,3,1) を計算します。その時点で、4 つの完全な i1 ループ (i1=0,1,2,3) を実行し、5 回目を実行しています。i1(=k_i1) の 4 つの完全なループの後 (5 回目を開始する直前) の k 値は、この関数を使用して計算できます (前と同じ種類)。

k_i1=sum(sum(sum(1,i3=0..i2),i2=0..l),l=0..i1-1) = f1(i1);

次に、5 番目のループを開始し、i2 ループに対して同じことを行います。その時点で、i2 の 3 つの完全なループを実行するので、次のようになります。

k_i2=sum(sum(1,i3=0..l),l=0..i2-1)=f2(i2);

これは、すべてのループに適用されます。最終的な値を取得するには、各 fi 関数を追加する必要があります。kは次のようになります

k=k_i1+k_i2+...

私の説明にはいくつかの小さな (+-1) エラーが含まれている可能性がありますが、基本的な考え方は、式を使用して完全なループをカウントすることです。

于 2012-11-11T13:28:38.197 に答える
0

この問題は、反復問題との組み合わせと見なすことができると思います。答えは C(n+N-1,N) です。詳細については、ウィキペディアの組み合わせ部分を確認してください。それが役に立てば幸い！

于 2012-11-11T14:44:29.640 に答える