第一行有块第二行有块第三行有块第nppt课件

1、n第一行有1=1块n第二行有1+2=3块n第三行有1+2+3=6块nn第n块有1+2+3+n块n所以，得：算法一(O(n2)nprogram t1;nvar n,i,j:longint;n ans:int64;/ans存储总块数nbeginn readln(n);n for i:=1 to n do/枚举层数n for j:=1 to i do/枚举斜列n inc(ans,j);n writeln(ans);nend.n察看每一层，用f(i)表示第i层的块数，得f(i)=f(i-1)+i;nf(1)=1;算法二(O(n)nprogram t2;nvar n,i,t:longint;/t用来存储

2、上一层块数n ans:int64;nbeginn readln(n);n for i:=1 to n don beginn t:=t+i;n inc(ans,t);n end;n writeln(ans);nend.n令1.S1=1+2+3+nn交换位置，得n 2.S1=n+n-1+2+1n 两式相加，得n 2*S1=(n+1)+(n+1)+(n+1)+(n+1)n 2*S1=(n+1)*nn S1=(n+1)*n/2n所以，得算法三(O(n)nprogram t3;nvar n,i:longint;n ans:int64;nbeginn readln(n);n for i:=1 to n d

3、on inc(ans,i*(i+1) div 2);/加上第i层的块数n writeln(ans);nend.n经过学习平方差公式，我们可以知道：n 1. 22-12=(2+1)*(2-1)=2*1+1;n 2. 32-22=(3+2)*(3-2)=2*2+1;n 3. 42-32=(4+3)*(4-3)=2*3+1;n n n. (n+1)2-n2=(n+1+n)*(n+1n)=2*n+1;n所以第i式*(n-i+1)，再相加，得n(n+1)2+n2+(n-1)2+22-1*n=n*(2*1+1)+(n-1)*(2*2+1)+2*(2*(n-1)+1)+1*(2*n+1)n令S2=12+22

4、+n2,对于右边第i式有n i*(2*(n-i)+1)n=i*2*(n-i)+in=2*i*n-2*i*i+in=2*i*n-2*i2+in那么 S2+(n+1)2-n=2*1*n-2*12+1*1+2*2*n-2*22+1*2+2*n*n-2*n*n+1*nn S2+(n+1)2=2*n*(1+2+n)-2(12+22+n2)+1*(1+2+n)n S2=2*n*n*(n+1)/2-2*S2+n*(n+1)/2n 3*S2=n*(n+1)/2*(2*n+1)n S2=n*(n+1)*(2*n+1)/6n此题中，第i层有i*(i+1)/2块n那么，得n总块数=1*(1+1)/2+2*(2+1)/2+3*(3+1)/2+(n-1)*n/2+n*(n+1)/2n=(1*1+1*1+2*2+2*1+3*3+3*1+(n-1)*(n-1)+(n-1)+n*n+n)/2n=(12+22+n2)+(1+2+3+n)/2n=n*(n+1)*(2*n+1)/6+n*(n+1)/2/2n=n*(n+1)*(n/3+1/6+1/2)/2n=n*(n+1)*(n/3+2/3)/2n=n*(n+1)*(n+2)/6算法四(O(1)nprog