有这样一个问题:
for(int i=0;i<n;i++)
for(int j=0;j<i;j++)
for(int k=0;k<j;k++)
;
执行的次数,当然通过程序可以计算出来,不过计算出来的数字是毫无意义的,因为n改变了又得重新计算.
下面根据k方和公司给出一个方法,即使是4次循环或者5次循环都可以计算.
这里设定 f(n,k) 表示 n的k次方法和(∑i^k) ,通过计算得出
f(n,1)=1+2+3+4+...+n = 1/2 n^2 +1/2 * n
f(n,2)=1^2+2^2+.....+n^2= 1/3 n^3 + 1/2 n^2 +1/6 * n
f(n,3)=1^3+2^3+....+n^3= 1/4 n^4 + 1/2 n^3 + 1/4 n^2
....
上面的问题:
f(1,1)+f(2,1)+f(3,1)+...f(n,1)
=∑f(i,1) (i从１到n)
=∑i(i+1)/2 (1->n)
=∑(i^2/2 + i/2) (1-->n)
=(1/2)∑(i^2) + (1/2)∑(i) (1-->n)
=(1/2)f(n,2)+(1/2)f(n,1)
=n(n+1)(2n+1)/12+ n(n+1)/4
=(1/6)*n*(n+1)(n+2)