Un puzzle relativo ai cicli nidificati

Question

Per un dato input N, quante volte viene eseguita la dichiarazione allegata?

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; 

Qualcuno può trovare un modo semplice o una formula per farlo in generale. Spiega per favore.

Answer 1

• In primo luogo, ho scritto un codice C per generare somma:

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"); 
} 

• compilazione semplice e generare risultato 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 

• Poi, cercato di esplorare How this works? con alcuni diagrammi:

  Per, N=1:

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

Ciò è (1) = 1

Per, 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 

Cioè (1) + (1 + 2) = 4

Per, 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 

Cioè (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 

Infine, ho potuto capito che somma di N in tre ciclo è:

(1) + (somma da 0 a 1 a 2) + ... + (somma da 1 a (N-2)) + (somma da 1 a (N-1)) + (somma da 1 a N)

oppure possiamo scrivere come:

=> (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)

È possibile fare riferimento qui per i calcoli di semplificazione: (I asked HERE)

[TUO RISPOSTA]

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

E, credo che la sua corretta. Ho controllato come segue:

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 

Inoltre, la complessità di questo algoritmo è O (n)

EDIT:

Il seguente ciclo ha anche stessi numeri di conteggio, che è = (((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;