题目150：在三角形数组中搜索具有最小和的子三角形

欧拉计划

Searching a triangular array for a sub-triangle having minimum-sum

In 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 s_k in the range ±2¹⁹, 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 2²⁰
    sk := t−2¹⁹

Thus: s₁ = 273519, s₂ = −153582, s₃ = 450905 etc

Our triangular array is then formed using the pseudo-random numbers thus:

s1
s2  s3
s4  s5  s6  
s7  s8  s9  s10
...

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 个伪随机数 s_k，范围在正负 2¹⁹ 之间：

t := 0
for k = 1 up to k = 500500:
t := (615949*t + 797807) modulo 2²⁰
s_k := t−2¹⁹

因此: s₁ = 273519, s₂ = −153582, s₃ = 450905 等等。

因此我们用随机数组成的三角型数组具有如下形式：

s1
s2 s3
s4 s5 s6
s7 s8 s9 s10
...

子三角形可以从数组中的任意元素开始，可以向下任意延伸（从下一行取两个元素，再下一行取三个元素，如此继续）。

定义“子三角形和”为子三角形内包含的所有元素之和。

求最小的子三角形和。

jerryxjr1220

1. from numba import jit
   
2. import numpy as np
   
3. @jit
   
4. def gen_s():
   
5.         s = np.zeros((1000,1000), dtype='int64')
   
6.         t = 0
   
7.         for l in range(1000):
   
8.                 i = 0
   
9.                 while i <= l:
   
10.                         t = (615949*t+797807) % 2**20
    
11.                         s[l,i] = t-2**19
    
12.                         i += 1
    
13.         return s
    
14. @jit
    
15. def get_sum(s, start_row, start_col, lines):
    
16.         total = s[start_row, start_col]
    
17.         for l in range(1, lines):
    
18.                 for i in range(l+1):
    
19.                         total += s[start_row+l, start_col+i]
    
20.         return total
    
21. @jit
    
22. def solve():
    
23.         s = gen_s()
    
24.         smallest = 99999999
    
25.         for lines in range(1000,1,-1):
    
26.                 x, y = 0, 0
    
27.                 while  x + lines <= 1000:
    
28.                         y = 0
    
29.                         while y <= x:
    
30.                                 smallest = min(smallest, get_sum(s, x, y, lines))
    
31.                                 y += 1
    
32.                         x += 1
    
33.         return smallest
    
34. print(solve())

复制代码

gunjang

继续采用pascal代码，d7编译通过，运行时间1~2s左右

1. program p150_2;
   
2. 
   
3. {$APPTYPE CONSOLE}
   
4. 
   
5. uses
   
6.   SysUtils, Types, Windows, Math;
   
7. const
   
8.   maxline = 1000;
   
9.   B220 = 1 shl 20;
   
10.   B219 = 1 shl 19;
    
11. type
    
12.   tline = array of Int64;
    
13.   Ttriangle = array[0..maxline - 1] of tline;
    
14.     //have n*(n+1)*(n+2)/6 triangle == 1.67billion
    
15. var
    
16.   triangle: Ttriangle;
    
17.   sumtriangle: Ttriangle;
    
18.   minsum: int64; //2^12 * 50w may >= 2^32
    
19.   st: DWORD;
    
20. 
    
21. procedure initSK;
    
22. var
    
23.   t, s: int64;
    
24.   line, col: integer;
    
25. begin
    
26.   minsum := 0;
    
27.   t := 0;
    
28.   for line := 0 to maxline - 1 do
    
29.   begin
    
30.     setlength(triangle[line], line + 1);
    
31.     for col := 0 to line do
    
32.     begin
    
33.       t := (615949 * t + 797807) mod B220;
    
34.       s := t - b219;
    
35.       triangle[line][col] := s;
    
36.       if s < minsum then
    
37.         minsum := s; //sidelength=1
    
38.     end;
    
39.   end;
    
40. end;
    
41. 
    
42. procedure calSumofTriangles;
    
43. var
    
44.   x, y: integer;
    
45.   sidelength: integer;
    
46.   x2, y2: integer;
    
47.   bottomsum: int64;
    
48. begin
    
49.   //calculate sidelength=2 Triangles
    
50.   for y := 0 to maxline - 2 do
    
51.   begin
    
52.     setlength(sumtriangle[y], y + 1);
    
53.     for x := 0 to y do
    
54.     begin
    
55.       sumtriangle[y][x] := triangle[y][x] + triangle[y + 1][x] + triangle[y + 1][x + 1];
    
56.       if sumtriangle[y][x] < minsum then
    
57.         minsum := sumtriangle[y][x];
    
58.     end;
    
59.   end;
    
60. 
    
61.   for sidelength := 3 to maxline do
    
62.   begin
    
63.     for y := 0 to maxline - sidelength do
    
64.     begin
    
65.       bottomsum := 0;
    
66.       y2 := y + sidelength - 1;
    
67.       for x2 := 0 to sidelength - 1 do
    
68.         inc(bottomsum, triangle[y2][x2]);
    
69.       inc(sumtriangle[y][0], bottomsum);
    
70.       if sumtriangle[y][0] < minsum then
    
71.         minsum := sumtriangle[y][0];
    
72. 
    
73.       for x := 1 to y do
    
74.       begin
    
75.         inc(bottomsum, -triangle[y2][x - 1] + triangle[y2][x - 1 + sidelength]);
    
76.         sumtriangle[y][x] := sumtriangle[y][x] + bottomsum;
    
77.         if sumtriangle[y][x] < minsum then
    
78.           minsum := sumtriangle[y][x];
    
79.       end;
    
80.     end;
    
81. 
    
82.     if sidelength mod 50 = 0 then
    
83.       writeln(Format('sidelenght=%d, minSum=%d', [sidelength, minsum]));
    
84.   end;
    
85. end;
    
86. 
    
87. begin
    
88.   st := gettickcount;
    
89.   initSK;
    
90.   calSumofTriangles;
    
91.   writeln(minsum); //-271248680
    
92.   writeln(Format('cost %n s', [(gettickcount - st) / 1000])); //1.56s-2.36s
    
93.   readln;
    
94. end.
    

复制代码