工学1号馆

home

« | 返回首页 | »

Project Euler 28–Number spiral diagonals

By Wu Yudong on August 13, 2018

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 the numbers on the diagonals is 101.
What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?

螺旋数阵对角线

从1开始,按顺时针顺序向右铺开的5 × 5螺旋数阵如下所示:

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

可以验证,该数阵对角线上的数之和是101。

以同样方式构成的1001 × 1001螺旋数阵对角线上的数之和是多少?

由于数据不是特别大,故这道题可以直接根据数字在矩阵中的规律使用C循环来计算,代码如下:

#include<stdio.h>

void countSum()
{
	int i = 3;
	int sum = 1;
	int n = (1001 + 1) / 2 - 1;
	while (n--) {
		int t = i * i;
		sum += (4 * t - (i - 1) * 6);
		i = i + 2;
	}
	printf("%d\n", sum);
}

int main()
{
	countSum();
	return 0;
}

这道题还可以使用数列求和的方法,直接得到和的通项公式,思路如下:

注意到

(1),(3,5,7,9),(13,17,21,25)……(\((2n-1)^2-(2n-1)\times3, (2n-1)^2-(2n-1)\times2, (2n-1)^2-(2n-1)\times1, (2n-1)^2\))

数列求和:

\(\because (2n-1)^2-(2n-1)\times3+ (2n-1)^2-(2n-1)\times2+(2n-1)^2-(2n-1)\times1+ (2n-1)^2\)

\(=16n^2-28n+16\)

\(\therefore S_{n}=(1+1+1+1)+(3+5+7+9)+(13+17+21+25)+\cdots \)

\(+[(2n-1)^2-(2n-1)\times3+ (2n-1)^2-(2n-1)\times2+(2n-1)^2-(2n-1)\times1+ (2n-1)^2]-3\)

\(=16\times \frac{1}{6}n(n+1)(2n+1)-28\times\frac{n(n+1)}{2}+16\times n-3\)

\(=\frac{1}{3}(16n^3-18n^2+14n)-3\)

所以此时取n=501即可得到答案

Answer:669171001
Completed on Thu, 25 Jul 2013, 21:31

如果文章对您有帮助,欢迎点击下方按钮打赏作者

Comments

No comments yet.
To verify that you are human, please fill in "七"(required)