loops - ネストされたループに関連するパズル

Question

与えられた入力Nに対して、囲まれたステートメントは何回実行されますか？

for i in 1 … N loop
  for j in 1 … i loop
    for k in 1 … j loop
      sum = sum + i ;
    end loop;
  end loop;
end loop;

誰もがこれを一般的に行うための簡単な方法や公式を理解できますか？説明してください。

Answer 1

• まず、C合計を生成するコードを 記述しました。

int main(){
  int i =0, k =0, j =0, n =0;
  int N =0; 
  int sum =0;
  N =10;
  for (n=1; n <= N; n++){
  // unindented code here
  sum =0;
  for (i=1; i<=n; i++)
      for (j=1; j<=i; j++)
          for (k=1; k<=j; k++)
              sum++;

  printf("\n N=%d  sum = %d",n, sum); 
  }
  printf("\n");
}

• 単純なコンパイルと結果の生成N=1 to N=10：

$ gcc sum.c
$ ./a.out

 N=1  sum = 1
 N=2  sum = 4
 N=3  sum = 10
 N=4  sum = 20
 N=5  sum = 35
 N=6  sum = 56
 N=7  sum = 84
 N=8  sum = 120
 N=9  sum = 165
 N=10  sum = 220

• 次に、How this works?いくつかの図を使って探索して みました。

  のために、N=1：

i<=N,     (i=1)       
            |
j<=i,     (j=1)       
            |
k<=j,     (K=1)       
            |
sum=0.    sum++       ---> sum = 1

つまり、（1）= 1

のために、N=2：

i<=N,     (i=1)-------(i=2)
            |     |-----|-----|
j<=i,     (j=1) (j=1)      (j=2)
            |     |     |----|----|
k<=j,     (K=1) (K=1) (K=1)    (K=2)               
            |     |     |        |    
sum=0,    sum++  sum++ sum++   sum++  --> sum = 4

つまり、（1）+（1 + 2）= 4

のために、N=3：

i<=N,     (i=1)-------(i=2)--------------------(i=3)
            |     |-----|-----|        |---------|-------------|
j<=i,     (j=1) (j=1)      (j=2)     (j=1)      (j=2)        (j=3)
            |     |     |----|----|    |     |----|----|    |-----|-----|
k<=j,     (K=1) (K=1) (K=1)    (K=2) (K=1) (K=1)    (K=2) (K=1) (K=2) (K=3)
            |     |     |        |     |     |        |     |     |        |
sum=0,    sum++  sum++ sum++  sum++ sum++  sum++    sum++  sum++ sum++  sum++
            --> sum = 10

つまり、（1）+（1 + 2）+（1 + 2 + 3）= 10

N = 1, (1)    = 1                                           

N = 2, (1) + (1 + 2)    = 4

N = 3, (1) + (1 + 2) + (1 + 2 + 3)  = 10

N = 4, (1) + (1 + 2) + (1 + 2 + 3) + (1 + 2 + 3 + 4)  = 20

N = 5, (1) + (1 + 2) + (1 + 2 + 3) + (1 + 2 + 3 + 4) + (1 + 2 + 3 + 4 + 5)  = 35

N 最後に、 3つのループ の合計は次のとおりであることが理解できました。

（1）+（合計0f 1から2）+ ... +（1から（N-2）の合計）+（1から（N-1）の合計）+（1からNの合計）

または、次のように書くことができます。

=>（1）+（1 + 2）+ ... +（1 + 2 + .... + i）+ ... +（1 + 2 + .... + N-1）+（1 + 2 + .... + N）

=>（N * 1）+（（N-1）* 2）+（（N-2）* 3）+ ... +（（N -i + 1）* i）+ ... +（1 * N）

簡略化の計算については、ここを参照してください:(ここで質問しました）

[あなたの答え]

= ( ((N) * (N+1) * (N+2)) / 6 )

そして、私はそれが正しいと思います。私は次のようにチェックしました：

N = 1,    (1 * 2 * 3)/6  = 1

N = 2,    (2 * 3 * 4)/6 = 4

N = 3,    (3 * 4 * 5)/6 = 6

N = 4,    (4 * 5 * 6)/6 = 10

N = 5,    (5 * 6 * 7)/6 = 35   

また、このアルゴリズムの複雑さはO（n ³） です。

編集：

次のループにも同じ数のカウントがあります。= ( ((N) * (N+1) * (N+2)) / 6 )

for i in 1 … N loop
  for j in i … N loop
    for k in j … N loop
      sum = sum + i ;
    end loop;
  end loop;
end loop;