题目28：1001×1001的螺旋中两条对角线之和是多少？,欧拉计划（Project Euler）,数据结构与算法,鱼C论坛

欧拉计划 发表于 2015-4-23 22:57:15

题目28：1001×1001的螺旋中两条对角线之和是多少？

本帖最后由欧拉计划于 2015-4-23 23:05 编辑

Number spiral diagonals

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

21 22232425
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
1716151413

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 22232425
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
1716151413

可以算出对角线上数字之和是 101.

1001×1001 的螺旋中对角线上数字之和是多少？

愤怒的大头菇 发表于 2016-9-1 20:21:41

count = 1
total = 1
list1 = []
while True:
   list2 = []
   count += 1
   total += (count - 1)*2*4
   temp = ((count - 1)*2*4+4)/4 - (1)
   tmp = total
   list2.append(tmp)
   while len(list2) <4:
         tmp -= temp
         list2.append(int(tmp))
   list1.append(list2)
   if count >1000:
         break
result = 0
for each in list1:
   result +=sum(each)
print(result)
结果是5343342001

愤怒的大头菇 发表于 2016-9-23 11:47:25

1 count = 1
2 total = 1
3 list1 = []
4 while True:
5       list2 = []
6       count += 1
7       total +=(count-1)*2*4
8       temp = ((count - 1)*2*4+4)/4-1
9       tmp = total
10       list2.append(tmp)
11       while len(list2) < 4:
12             tmp -= temp
13             list2.append(int(tmp))
14       list1.append(list2)
15       if count > 500:
16             break
17 result = 0
18 for each in list1:
19       result += sum(each)
20 print(result)
答案：669171001

芒果加黄桃 发表于 2017-1-12 17:08:55

本帖最后由芒果加黄桃于 2017-1-12 17:09 编辑

# encoding:utf-8
# 1001 * 1001 螺旋对角线之和
from time import time
def euler027(N):
l_result =
t = 1
for step in range(2, N + 1, 2):
   k = 1
   while k <= 4:
         k += 1
         t += step
         l_result.append(t)
print(sum(l_result))
if __name__ == '__main__':
start = time()
euler027(1001)
print('cost %.6f sec' % (time() - start))
669171001
cost 0.000000 sec

渡风发表于 2017-1-23 13:05:47

此代码使用matlab编程
Problem27所用时间为0.0021426秒
Problem27的答案为669171001
%% Problem28
% 题目28:1001×1001的螺旋中两条对角线之和是多少?
function Output=Problem28(Input)
tic
if nargin==0
Input=1001;
end
Circle=(Input+1)/2;%方阵阶数为n,矩阵圈数为（n+1)/2
Sum=0;
for ii=2:Circle
Temp=(2*ii-1)^2:-2*(ii-1):(2*ii-3)^2+1;%得到2-501圈的数的数
Sum=Sum+sum(Temp);
end
Output=Sum+1;%得到第一圈的数
toc
disp('此代码使用matlab编程')
disp(['Problem27所用时间为',num2str(toc),'秒'])
disp(['Problem27的答案为',num2str(Output)])

99592938 发表于 2017-3-18 21:51:07

sum0=n=1
temp=int(input('请输入螺旋矩阵的边：'))
for i in range(3,temp+1,2):
for j in range(1,5):
n+=i-1
sum0+=n
print('%d×%d的螺旋对角线上数字之和是：%d' %(temp,temp,sum0))
请输入螺旋矩阵的边：1001
1001×1001的螺旋对角线上数字之和是：669171001

hvagab 发表于 2018-4-23 21:34:55

s=0
for i in range(7,1002,2):
ys = i**2
zs = i**2-(i-1)
zx = zs - (i-1)
yx = zx-(i-1)
s+=ys+zs+zx+yx

print(s+101)

hk1057 发表于 2018-7-29 01:29:42

'''
这里利用规律发现右上角对角线上的数为3^2,5^2,...,(2n-1)^2，
而另外三个对角的数为(2n-1)^2 -(2n-1-1),
(2n-1)^2 -(2n-1-1)*2,
(2n-1)^2 -(2n-1-1)*3,
'''
total_sum = 1
for i in range(3, 1002, 2):
start_num = i**2
sum1 = start_num
for x in range(1,4):
sum1 += (start_num - (i-1) * x)
total_sum += sum1
print(total_sum)

hk1057 发表于 2018-7-29 01:30:56

由我们主宰 发表于 2018-7-29 08:16:45

public class Spiral{
public static void main(String[] args){
long sum = 1,n = 1;
int gap = 2;
for(int round = 1;round <= 500;round ++){
for(int i = 1;i <= 4;i ++){
n += gap;
sum += n;
}
gap += 2;
}
System.out.println(sum);
}
}
669171001

王小召 发表于 2019-6-12 14:05:45

本帖最后由王小召于 2019-6-12 14:10 编辑

对角线之和为:669171001
用时：0.17160109999999998 秒

#矩阵长度 N*N ：等比数列等差数列结合求和问题
import time

def get_result(n):
return sum()

print("对角线之和为:{}\n用时：{} 秒".format(get_result(1001), time.process_time()))

cwhsmile 发表于 2019-12-10 12:45:04

sum = 1
for i in range(3,1002,2):
m = i*i
n = m - (i-1)
x = m - 2*(i-1)
y = m - 3*(i-1)
sum =sum + m+n+x+y
print(sum)

leon0149 发表于 2020-5-17 11:24:11

669171001
#include <stdio.h>

int main(void)
{
int sum = 1;

int i = 1;
int j = 2;
while (i < 1001*1001)
{
   for (int k = 0; k < 4; ++k) {
         i += j;
         sum += i;
   }
   j += 2;
}

printf("%d", sum);
return 0;
}

debuggerzh 发表于 2020-8-2 19:39:11

https://wx3.sinaimg.cn/mw690/0081qlg6ly1ghcp56bhgdj315p0u0wjg.jpg
寻找规律，推出矩形框右边两数之和的通式
每个矩形框的左边两数之和与右边两数之和相等
#include<iostream>
using namespace std;

int main(){
int sum = 1;

for (int i = 3;i <= 1001;i+=2)
sum += 2*(2*i*i - 3*i + 3);

cout << sum;
return 0;
}

答案为 669171001

有马_冬巳 发表于 2020-10-21 16:03:47

'''1001×1001 的螺旋中对角线上数字之和是多少？'''

'''1.从右下角顺时针旋转依次初始和差为2，递增为8的二阶递增
2.去除最中间的一'''

def rotate(lines):
if lines % 2 != 1:
   print("行数需要是单数！")
else:
   sum = 0
   a1 = 3
   b1 = 10
   for i in range(4):
         an = a1
         bn = b1
         for i in range(int((lines - 1)/2)):
            sum += an
            an += bn
            bn += 8
         a1 += 2
         b1 += 2
   sum += 1
   print("在%d * %d 的螺旋中对角线上数字之和是：%d" %(lines,lines,sum))

start = time.time()
rotate(1001)
end = time.time()
print("共用时%f秒" %(end - start))

在1001 * 1001 的螺旋中对角线上数字之和是：669171001
共用时0.000496秒

a1351468657 发表于 2021-3-12 21:33:03

#include <stdio.h>

main()
{
int i, sum = 1;
int ne, nw, se, sw;//分别为东北，西北，西南，东南角的数

for (i = 3; i < 1002; i += 2)
{
ne = i * i;
nw = ne - i + 1;
sw = nw - i + 1;
se = sw - i + 1;
sum += ne + nw + sw + se;
}
printf("%d", sum);
}

答案为：669171001

mathtimes 发表于 2021-8-7 07:45:32

本帖最后由 mathtimes 于 2021-8-7 08:17 编辑

4段对角线函数分别是:
4x^2-4x+1
4x^2-6x+3
4x^2-8x+5
4x^2-10x+7
总和是16x^2-28x+16
减去重合的三个一
然后再求和

#include <stdio.h>
int main()
{
int i, sum = 0;
for(i=1;i<=501;i++)
sum += 16*i*i-28*i+16;
printf("%d", sum-3);
}

页: [1]

鱼C论坛's Archiver

题目28：1001×1001的螺旋中两条对角线之和是多少？