Project Euler——Problem 28 - Daybreakcx's Blog - Keep Programming! With Algorithm! With Fun!
Project Euler——Problem 27
Project Euler——Problem 29

Project Euler——Problem 28

daybreakcx posted @ 2009年7月27日 17:58 in Prject Euler , 792 阅读

原题与答案:

Problem 28

11 October 2002

 

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

It can be verified that the sum of both diagonals is 101.

What is the sum of both diagonals in a 1001 by 1001 spiral formed in the same way?

Answer:669171001
 

分析与解答:

这题是求按照顺时针从中间展开的1001*1001的方阵对角线上数字的和,其实很简单,最初想法肯定是先列出这个方阵,然后求,但是实际上不用,我们一圈一圈来看,除了最里圈只有一个数字1外,其余都是四个数字,而且实际上沿着1向右上角走去是奇数的平方,那么我们可以根据[2*(k+1)-1]^2-(2*k-1)^2=(2*k+1)^2-(2*k-1)^2=8*k对角线上的最大数值的差是8乘以圈数-1,这样我们对于每一圈处理四个数值即可,最后便能很轻松得到结果,我的源程序代码如下所示:

 

  1. #include<stdio.h>
  2. int i,j,ans;
  3. int main()
  4. {
  5.         ans=1;
  6.         for (i=1,j=2;i<1002001;i+=4*j,j+=2) ans+=i*4+j*10;
  7.         printf("%d\n",ans);
  8.         return 0;
  9. }

 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter