多重嵌套循環指數

我有多個（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基於i1，...，iN環路內。

對於N=1：k=f(i1)=i1

對於N=2：k=f(i1,i2)=i1*(i1+1)/2+i2

來源

2012-11-11 nil

該公式只取決於'n'而不是'i {N}'。嘗試寫入'N'的前幾個值。 –

@izomorphius，我需要知道循環內部的'k'而不增加它。 – nil

一般來說，有一個嵌套的總和：

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

它可以從使用these basic summation formules內而外簡化。最終結果將只取決於N作爲izomorphius評論，因爲N是i1的上限，這是i2的上限，...

編輯：好吧，與您的編輯，我現在看到你有一個不同的問題。現在它有點複雜但仍然沒有問題。

我們需要爲此分配一些東西。我將計算值k = f（4,3,1）。在那個時候，我們將執行4個完整的i1循環（i1 = 0,1,2,3）並且正在執行第五個循環。可以使用此函數（與以前相同）計算i1（= k_i1）的4個完整循環後的k值（就在我們開始第五個之前）。

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

現在我們開始第5個循環，併爲i2循環執行相同的操作。此時，我們將完成3個完整循環的i2，所以我們得到

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

這對所有的循環都有效。爲了獲得最終的價值，你必須添加每個fi函數。 k將看起來像

k=k_i1+k_i2+...

一些小（±1）在我的解釋錯誤是可能的，但其基本思想是用公式來算完整循環。

來源

2012-11-11 13:28:38 Origin

請仔細閱讀這個問題 – nil

@Nil：我已經更新了我對你的更新問題的回答，我希望這是你的意思 – Origin

是的，它的作品謝謝 – nil

我想我們可以把這個問題當作的組合重複的問題。答案是C（n + N-1，N）。你可以查看維基百科的combination part以獲得更多的細節。希望能幫助到你！

來源

2012-11-11 14:44:29 Chasefornone

請仔細閱讀問題 – nil

真的很抱歉我的錯誤！ – Chasefornone

多重嵌套循環指數

回答

相關問題