首页 > 代码库 > hdu 1178 Heritage from father (推导)

hdu 1178 Heritage from father (推导)

题意:

  有一个金币堆的金字塔,最上层就有一个金币,以后的i层都是边长为i的实心三角形,给你层数,问:一共有多少个金币?(用科学计数法表示,并且保留两位小数)

解题思路:

  根据题意可知求出1*n+2*(n-1)+3*(n-2)+4*(n-3)+.......+(n-2)*3+(n-1)*2+n*1的和即可,但是要化简一下求出n*(n+1)*(n+2)/6;

证明:

  1 * n + 2 (n - 1) + 3 (n - 2) + …… + (n - 2) * 3 + (n - 1) * 2 + n * 1

  = 1 * (n + 1 - 1) + 2 (n + 1 - 2) + 3 (n + 1 - 3) + …… + (n - 2) * (n + 1 - (n - 2)) + (n - 1) * (n + 1 - n - 1) + n * (n + 1 - n)

  =(1 + 2 + 3 + ... + n)(n + 1) - (1^2 + 2^2 + 3^2 + ..... + n^2)

  =n (n + 1)^2 / 2 - n (n + 1) (2n + 1) / 6       (n (n + 1) (2n + 1) / 6后面会证明)

  =n * (n + 1) * (n + 2) / 6          (证毕)

 

 

  (n+1)^3-n^3=3n^2+3n+1, 

  n^3-(n-1)^3=3(n-1)^2+3(n-1)+1 

  

  3^3-2^3=3*(2^2)+3*2+1 

  2^3-1^3=3*(1^2)+3*1+1.

  这n个等式两边分别相加得出:

  (n+1)^3-1=3(1^2+2^2+3^2+....+n^2)+3(1+2+3+...+n)+n, 

  (n+1)^3-1=3(1^2+2^2+3^2+....+n^2)+3((n+1)n/2)+n, 

  整理可得上述式子。

代码:

 1 #include <stdio.h> 2 int main () 3 { 4     int n, i, k; 5     double s; 6  7     while (scanf ("%d", &n), n) 8     { 9         s = 1.0 * n * (n+1) * (n+2) / 6;10         k = 0;11         while (s >= 10)12         {13             s /= 10;14             k++;15         }16         printf ("%.2fE%d\n", s, k);17     }18 19     return 0;20 }
View Code

 

 

 

 

  
 

 

hdu 1178 Heritage from father (推导)