演算法--請問這麼for迴圈執行幾次

Question

for i=1to n{
for j=1to i{
for k=1to j{
x=x+1 請問這行執行幾次?
}
}
}

答案是 n*(n+1)*(n+2)/6

請問
1.這通式怎麼推導?
2.如果加上第4層迴圈for L=1 to k那又是執行幾次呢?

15分請盡量詳達 謝謝~

嗯,我知道第2層因為是等差級數所以可用梯形面積算
(上底+下底)*高/2

重點是第3層,怎麼推呢?

重點是,這是有通式嗎?不管幾層都有一定規律?放諸四海皆通呢?
謝謝

生命中的絕對大大 恕我愚昧:

當n=3時
會發現會做1+2*2+3*3次=14次?

套公式 n*(n+1)*(n+2)/6=10次?

i=1 2 3 3次
j=1 1 2 1 2 3 6次
k=1 1 12 1 12 123 10次

不曉得大大14次怎麼來的耶?

=1 2 3===========> 3次
j=1 1 2 1 2 3 =========>6次
k=1 1 12 1 12 123 ======>10次

不曉得大大14次怎麼來的耶?

請看一下
http://content.edu.tw/senior/computer/ks_ks/book/algodata/algorithm/algo5.htm
中間 "常見的Big-oh"一節上面他提到ㄉn(n+l)(n+2)/6怎麼來的~

n*(n+1)*(2n+1)/6 是 ∑i^2公式

以該回圈而言應該是 次數=∑i(i+1)/2 才是 非∑i^2

Leslie 大大:
針對您的推導有些疑問:
1. 我要算的是"執行次數"而非數值總合 ,也就是=>1,12,123共6次(6個數字)非1+1+2+1+2+3

2.針對方法2:
S = n+(n-1)2+(n-2)3+...+(n-(n-1))n= [ n(n+n^2)/2] - [let here be T]
從何得知 T = 2S - n(n+1)
S= [ n(n+n^2)/2] - [let here be T]
=>T= [ n(n+n^2)/2] -S =?= 2S - n(n+1)

Leslie大大:

嗯,我懂你的意思

不過我太笨了又有個問題:

2*S = [1*2+2*3+3*4+...+(n-1)n+n(n+1)]

怎麼導出來的呢?

3Q

Answer 1

Prove that (1)+(1+2)+(1+2+3)+...+(1+2+3+...+n) = n*(n+1)*(n+2)/6
也就是 Sigma[i(i+1)/2] = n*(n+1)*(n+2)/6

Solution:

第一方法--數學歸納法.
for n = 1, 成立.
設 n=k 成立, 即
(1)+(1+2)+(1+2+3)+...+(1+2+3+...+k)= k*(k+1)*(k+2)/6.
則, 當 n = k+1 時:
上式左邊多加一項 (k+1)(k+2)/2, 要推出右邊會變成 (k+1)*(k+2)*(k+3)/6,
這推導不難.

第貳方法--
Let 左邊為 S.
S 中, 共有 n 個 1, n-1 個 2, n-2 個 3, ..., 1 個 n
所以, S = n+(n-1)2+(n-2)3+...+(n-(n-1))n
= [n+2n+3n+...+nn] - [1*2+2*3+3*4+...+(n-1)n]
= [ n(n+n^2)/2] - [let here be T]

又 觀察到 T = 2S - n(n+1), 帶入, 得
3 S = [ n(n+n^2)/2]+n(n+1)
S = (n^3+3n^2+2n ) / 6

剛好等於右式.

2007-06-13 00:01:31 補充：
1. 我就是在算"執行次數". 您不是自己也發現, 說
"應該是 次數=∑i(i+1)/2 才是" 嗎?
像 n = 3, 就是您算的 10 次, n*(n+1)*(n+2)/6 也是 10.
我就是要證明或導出: 您的 ∑i(i+1)/2 和您老師的 n*(n+1)*(n+2)/6 是一樣的.

2. 我是令 T 為 [1*2+2*3+3*4+...+(n-1)n]
而 S = Sigma[i(i+1)/2] (Sigma 是 i=1 to n)
2*S = [1*2+2*3+3*4+...+(n-1)n+n(n+1)]
So, T = 2S - n(n+1)

2007-06-13 19:56:56 補充：
補充內容字數多, 竟然不被系統接受,
所以我只好 email 給您了.

2007-06-14 11:53:40 補充：
2.如果加上第4層迴圈for L=1 to k那又是執行幾次呢?
解:
答案內容在此字數多, 也是不被系統接受,
所以我也只好 email 給您了!!

Answer 2

到下面的網址看看吧

▶▶http://candy5660601.pixnet.net/blog

Answer 3

二次方公式打錯了
n(n+1)(2n+1)/6