Project Euler——Problem 28

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

原题与答案：

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，这样我们对于每一圈处理四个数值即可，最后便能很轻松得到结果，我的源程序代码如下所示：

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

[回复]

<a href="https://bes 说:
2023年6月07日 14:58

it's really nice and meanful. it's really cool blog. Linking is very useful thing.you have really helped lots of people who visit blog and provide them usefull information.