题目149：搜索一个最大和子序列

欧拉计划 · 发表于 2016-8-31 23:07:25

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

Searching for a maximum-sum subsequence

Looking at the table below, it is easy to verify that the maximum possible sum of adjacent numbers in any direction (horizontal, vertical, diagonal or anti-diagonal) is 16 (= 8 + 7 + 1).

Now, let us repeat the search, but on a much larger scale:

First, generate four million pseudo-random numbers using a specific form of what is known as a "Lagged Fibonacci Generator":

For 1 ≤ k ≤ 55, s_k = [100003 − 200003k + 300007k³] (modulo 1000000) − 500000.
For 56 ≤ k ≤ 4000000, s_k = [s_k−24 + s_k−55 + 1000000] (modulo 1000000) − 500000.

Thus, s₁₀ = −393027 and s₁₀₀ = 86613.

The terms of s are then arranged in a 2000×2000 table, using the first 2000 numbers to fill the first row (sequentially), the next 2000 numbers to fill the second row, and so on.

Finally, find the greatest sum of (any number of) adjacent entries in any direction (horizontal, vertical, diagonal or anti-diagonal).

题目：

请看下面的表格，可以轻易验证：在任意方向上（水平，竖直，两个对角线）相邻数之和最大为 16（= 8 + 7 + 1）。

现在，在更大的规模上重复上面的搜索：

首先，用 Lagged Fibonacci Generator 的方法生成 400 万个伪随机数：

对于 1 ≤ k ≤ 55, s_k = [100003 − 200003k + 300007k³] (modulo 1000000) − 500000.
对于56 ≤ k ≤ 4000000, s_k = [s_k−24 + s_k−55 + 1000000] (modulo 1000000) − 500000.

因此, s₁₀ = −393027 and s₁₀₀ = 86613.

然后，将如此生成的 s 安放在一个 2000×2000 的表中，用前 2000 个数依次填充第一行，如此继续。

最后，求在这个表中任意方向上最大的相邻数（任意多个）之和。

jerryxjr1220 · 发表于 2017-7-26 17:30:15

from numba import jit
import numpy as np
@jit
def gen_s():
s = np.zeros(4000000, dtype='int64')
for k in range(0, 55):
s[k] = (100003-200003*(k+1)+300007*(k+1)**3) % 1000000 - 500000
for k in range(55, 4000000):
s[k] = (s[k-24]+s[k-55]+1000000) % 1000000 - 500000
return s.reshape(2000,2000)
@jit
def get_max_wd(s):
maxsum_w = np.max(np.sum(s, axis=1))
maxsum_d = np.max(np.sum(s, axis=0))
maxsum = max(maxsum_d, maxsum_w)
return maxsum
@jit
def get_max_lr(s, n):
maxsum = 0
for line in range(n):
total = 0
y = line
x = 0
while x<n and y<n:
total += s[x,y]
x += 1
y += 1
maxsum = max(maxsum, total)
for line in range(n-1,-1,-1):
total = 0
y = line
x = n-1
while x>=0 and y>=0:
total += s[x,y]
x -= 1
y -= 1
maxsum = max(maxsum, total)
for line in range(n-1,-1,-1):
total = 0
y = line
x = 0
while x<n and y>=0:
total += s[x,y]
x += 1
y -= 1
maxsum = max(maxsum, total)
for line in range(n):
total = 0
y = line
x = n-1
while x>=0 and y<n:
total += s[x,y]
x -= 1
y += 1
maxsum = max(maxsum, total)
return maxsum
@jit
def solve():
s = gen_s()
return max(get_max_wd(s), get_max_lr(s, 2000))
print(solve())

复制代码

速度应该是够了，算法还有些问题，下次再检查。

jerryxjr1220 · 发表于 2017-7-28 15:15:07

用4x4的矩形验算都是正确的，大的矩形第10个和第100个数值也都是正确的，不知道错哪了。。。

from numba import jit
import numpy as np
@jit
def gen_s():
s = np.zeros(4000000, dtype='int64')
for k in range(0, 55):
s[k] = (100003-200003*(k+1)+300007*(k+1)**3) % 1000000 - 500000
for k in range(55, 4000000):
s[k] = (s[k-24]+s[k-55]+1000000) % 1000000 - 500000
return s.reshape(2000,2000)
@jit
def get_max_w(s):
return np.max(np.sum(s, axis=1))
@jit
def get_max_d(s):
return np.max(np.sum(s, axis=0))
@jit
def get_max_l(s, n):
maxsum = 0
for line in range(n):
total = 0
y = line
x = 0
while x<n and y<n:
total += s[x,y]
x += 1
y += 1
maxsum = max(maxsum, total)
for line in range(n-1,-1,-1):
total = 0
y = line
x = n-1
while x>=0 and y>=0:
total += s[x,y]
x -= 1
y -= 1
maxsum = max(maxsum, total)
return maxsum
@jit
def get_max_r(s, n):
maxsum = 0
for line in range(n-1,-1,-1):
total = 0
y = line
x = 0
while x<n and y>=0:
total += s[x,y]
x += 1
y -= 1
maxsum = max(maxsum, total)
for line in range(n):
total = 0
y = line
x = n-1
while x>=0 and y<n:
total += s[x,y]
x -= 1
y += 1
maxsum = max(maxsum, total)
return maxsum
@jit
def solve():
s = gen_s()
return get_max_d(s),get_max_w(s),get_max_l(s, 2000),get_max_r(s, 2000)
print(solve())

复制代码

(48519449, 44540336, 43117448, 40358088)
[Finished in 2.8s]

账号		自动登录	找回密码
密码			立即注册

题目149：搜索一个最大和子序列

马上注册，结交更多好友，享用更多功能^_^

浏览过的版块