题目150：在三角形数组中搜索具有最小和的子三角形
Searching a triangular array for a sub-triangle having minimum-sumIn a triangular array of positive and negative integers, we wish to find a sub-triangle such that the sum of the numbers it contains is the smallest possible.
In the example below, it can be easily verified that the marked triangle satisfies this condition having a sum of −42.
We wish to make such a triangular array with one thousand rows, so we generate 500500 pseudo-random numbers sk in the range ±219, using a type of random number generator (known as a Linear Congruential Generator) as follows:
t := 0
for k = 1 up to k = 500500:
t := (615949*t + 797807) modulo 220
sk := t−219
Thus: s1 = 273519, s2 = −153582, s3 = 450905 etc
Our triangular array is then formed using the pseudo-random numbers thus:
s1
s2s3
s4s5s6
s7s8s9s10
...
Sub-triangles can start at any element of the array and extend down as far as we like (taking-in the two elements directly below it from the next row, the three elements directly below from the row after that, and so on).
The "sum of a sub-triangle" is defined as the sum of all the elements it contains.
Find the smallest possible sub-triangle sum.
题目：
在一个由正整数和负整数组成的三角形数组中，我们希望找到一个子三角形，使得该三角形中包含的所有数字之和最小。
在下图的例子中，可以验证红色标记的三角形满足上述条件，其和为 -42。
我们希望构造一个一千行的三角形数组，所以我们用如下一种名为线性同余法的随机数生成法生成 500500 个伪随机数 sk，范围在正负 219 之间：
t := 0
for k = 1 up to k = 500500:
t := (615949*t + 797807) modulo 220
sk := t−219
因此: s1 = 273519, s2 = −153582, s3 = 450905 等等。
因此我们用随机数组成的三角型数组具有如下形式：
s1
s2 s3
s4 s5 s6
s7 s8 s9 s10
...
子三角形可以从数组中的任意元素开始，可以向下任意延伸（从下一行取两个元素，再下一行取三个元素，如此继续）。
定义“子三角形和”为子三角形内包含的所有元素之和。
求最小的子三角形和。
from numba import jit
import numpy as np
@jit
def gen_s():
s = np.zeros((1000,1000), dtype='int64')
t = 0
for l in range(1000):
i = 0
while i <= l:
t = (615949*t+797807) % 2**20
s = t-2**19
i += 1
return s
@jit
def get_sum(s, start_row, start_col, lines):
total = s
for l in range(1, lines):
for i in range(l+1):
total += s
return total
@jit
def solve():
s = gen_s()
smallest = 99999999
for lines in range(1000,1,-1):
x, y = 0, 0
whilex + lines <= 1000:
y = 0
while y <= x:
smallest = min(smallest, get_sum(s, x, y, lines))
y += 1
x += 1
return smallest
print(solve()) 本帖最后由 gunjang 于 2017-9-7 16:39 编辑
继续采用pascal代码，d7编译通过，运行时间1~2s左右
program p150_2;
{$APPTYPE CONSOLE}
uses
SysUtils, Types, Windows, Math;
const
maxline = 1000;
B220 = 1 shl 20;
B219 = 1 shl 19;
type
tline = array of Int64;
Ttriangle = array of tline;
//have n*(n+1)*(n+2)/6 triangle == 1.67billion
var
triangle: Ttriangle;
sumtriangle: Ttriangle;
minsum: int64; //2^12 * 50w may >= 2^32
st: DWORD;
procedure initSK;
var
t, s: int64;
line, col: integer;
begin
minsum := 0;
t := 0;
for line := 0 to maxline - 1 do
begin
setlength(triangle, line + 1);
for col := 0 to line do
begin
t := (615949 * t + 797807) mod B220;
s := t - b219;
triangle := s;
if s < minsum then
minsum := s; //sidelength=1
end;
end;
end;
procedure calSumofTriangles;
var
x, y: integer;
sidelength: integer;
x2, y2: integer;
bottomsum: int64;
begin
//calculate sidelength=2 Triangles
for y := 0 to maxline - 2 do
begin
setlength(sumtriangle, y + 1);
for x := 0 to y do
begin
sumtriangle := triangle + triangle + triangle;
if sumtriangle < minsum then
minsum := sumtriangle;
end;
end;
for sidelength := 3 to maxline do
begin
for y := 0 to maxline - sidelength do
begin
bottomsum := 0;
y2 := y + sidelength - 1;
for x2 := 0 to sidelength - 1 do
inc(bottomsum, triangle);
inc(sumtriangle, bottomsum);
if sumtriangle < minsum then
minsum := sumtriangle;
for x := 1 to y do
begin
inc(bottomsum, -triangle + triangle);
sumtriangle := sumtriangle + bottomsum;
if sumtriangle < minsum then
minsum := sumtriangle;
end;
end;
if sidelength mod 50 = 0 then
writeln(Format('sidelenght=%d, minSum=%d', ));
end;
end;
begin
st := gettickcount;
initSK;
calSumofTriangles;
writeln(minsum); //-271248680
writeln(Format('cost %n s', [(gettickcount - st) / 1000])); //1.56s-2.36s
readln;
end.
页:
[1]