Euler Project 挨个做- 之三 (Q79-?)

tree_new_bee

Q81. Find the minimal path sum from the top left to the bottom right by moving right and down.
n the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold red and is equal to 2427.

       
131        673        234        103        18
201        96        342        965        150
630        803        746        422        111
537        699        497        121        956
805        732        524        37        331
       

Find the minimal path sum, in matrix.txt (right click and 'Save Link/Target As...'), a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by only moving right and down.

tree_new_bee

81,82,83是一个系列的， 只是难度越来越大。

Q81本身很简单， 就是处理这个文件麻烦点，不过处理好了，后两道题就不用费神了。
其实要是不用SQL, 而是用excel来做的话，几分钟就能搞定。

对文件的读取，依然沿用以前Q67的外部表的方法， 把一整行读到表中的一个长字段中， 然后在语句中去处理。 (SQL*LOADER用的不熟，否则也许可以直接读成行列？)

1. create  table euler_q81(
   
2.   rn number,
   
3.   line varchar2 (400)
   
4.     )
   
5.   ORGANIZATION EXTERNAL (
   
6.          TYPE ORACLE_LOADER
   
7.          DEFAULT DIRECTORY euler_dir
   
8.          ACCESS PARAMETERS
   
9.          (
   
10.            records delimited by '\r\n'
    
11.            badfile euler_dir:'triangle%a_%p.bad'
    
12.            logfile euler_dir:'triangle%a_%p.log'
    
13.            fields terminated by '\r\n'
    
14.                    (rn RECNUM,
    
15.                    line char(400))
    
16.          )
    
17.          LOCATION ('matrix81.txt')
    
18. 
    
19.   );
    

复制代码

计算很简单， 每个单元加上左或上的单元中的较小值即可。 用MODEL语句最方便。

1. with td as (select level c from dual connect by level<=80)
   
2. , t as (select rn r, c,
   
3. to_number(substr(line,
   
4. case when c=1 then 1 else instr(line,',',1, c-1)+1 end,
   
5.   case when c=1 then instr(line,',',1, c) -1
   
6.        when c=80 then 10
   
7.        else instr(line,',',1, c) - instr(line,',',1, c-1)-1 end
   
8. )) num
   
9. from euler_q81 t, td)
   
10. -- select r,c, to_number(num) num from t;
    
11. ,t2 as (SELECT r,c,num
    
12.   FROM t
    
13. MODEL
    
14.     DIMENSION BY (r,c)
    
15.     MEASURES (num)
    
16.     RULES update
    
17.      (
    
18.      update num[any, any] order by r , c  =
    
19.      case when cv(r)=1 and cv(c)=1 then num[cv(r),cv(c)]
    
20.           when cv(r) = 1 and cv(c)>1 then num[cv(r),cv(c)] + num[cv(r), cv(c)-1]
    
21.           when cv(c) = 1 and cv(r)>1 then num[cv(r),cv(c)] + num[cv(r)-1, cv(c) ]
    
22.           else  num[cv(r),cv(c)] +  least(num[cv(r)-1,cv(c)], num[cv(r), cv(c)-1])
    
23.      end
    
24. ) order by r , c)
    
25. select * from t2  where r=80 and c=80

复制代码

R          C        NUM
---------- ---------- ----------
        80         80     427337

Executed in 0.093 seconds

tree_new_bee

Q82. Find the minimal path sum from the left column to the right column.
NOTE: This problem is a more challenging version of Problem 81.

The minimal path sum in the 5 by 5 matrix below, by starting in any cell in the left column and finishing in any cell in the right column, and only moving up, down, and right, is indicated in red and bold; the sum is equal to 994.

       
131        673        234        103        18
201        96        342        965        150
630        803        746        422        111
537        699        497        121        956
805        732        524        37        331
       

Find the minimal path sum, in matrix.txt (right click and 'Save Link/Target As...'), a 31K text file containing a 80 by 80 matrix, from the left column to the right column.


82看着好像跟81差不多，但实际上没那么简单。
附件我比较了一下，与Q81的附件完全相同。

newkid

外部表的语法其实就是从SQL LOADER来的。如果有分隔符比如逗号，可以直接加载到列里面。

Q81为什么这么简单？当前较小不意味着总值最小？

lastwinner

链接前将标题给一下，不然别人不知道是从Q几到Q几，呵呵

lastwinner

newkid 发表于 2012-2-18 00:52
外部表的语法其实就是从SQL LOADER来的。如果有分隔符比如逗号，可以直接加载到列里面。

Q81为什么这么简 ...

同newkid，我也认为当前最小并不等价于总值最小
不过model的方法我还没学会，所以TNB那语句我就没看

tree_new_bee

newkid 发表于 2012-2-18 00:52
外部表的语法其实就是从SQL LOADER来的。如果有分隔符比如逗号，可以直接加载到列里面。

Q81为什么这么简 ...

说起来简单，是因为有以前的基础。这问题与q15思路一样，都是找到到每一个点的最小路径。只是15中每段路的长度恒为1,这里是个数字; 那里是统计路径数目， 这里是选择最小值而已。
以前不知道，现在跟孩子一起看奥数，知道这种方法叫标数法。可以用奥数+标数法去搜索相关实例。

tree_new_bee

用题目中的示例来演示一下算法的含义：
131        673        234        103        18
201        96        342        965        150
630        803        746        422        111
537        699        497        121        956
805        732        524        37        331
从左上角(1,1)点到(1,1)点的path sum, 显然就是该点的数值131
因为只能朝右或下走， 所以到达第一行第二列(1,2)点的path sum只能是131+673
而到达达第二行第一列(2,1)点的path sum只能是131+201
同理， 到达(1,3)(1,4)(1,5) 的只能是从(1,1)开始向右的累加和， 到达(3,1)(4,1)(5,1) 的只能是从(1,1)开始向下的累加和
这样得到初步结果：
131        131+673        131+673+234        131+673+234+103        131+673+234+103+18
131+201
131+201+630
131+201+630+537
131+201+630+537+805

重要的第二步：
现在看(2,2)点，
从(1,1)到(2,2), 有两条路可走，也就是两个前置点((1,2)和(2,1). 因为当前点的数值是一定的，所以到该点的path sum 最小的路径前一站一定是path sum 较小的那个点，在这个例子中就是(2,1)对应的131+201， 所以(2,2)的path sum 为131+201+96

剩下的点与(2,2)点的算法一样，都能依次找到左和上的两个前置点， 所以也就能以此计算出最小的path sum.

计算完成后， (80,80)的数值就是到达该店的最小path sum

tree_new_bee

至于82， 由于路径不再是单向的， 做起来要复杂的多，
还是以题目中的例子来考虑思路：
131        673        234        103        18
201        96        342        965        150
630        803        746        422        111
537        699        497        121        956
805        732        524        37        331
       
首先，第一列不用考虑， 每个点的path sum就是自己的值。

然后，考虑第二列，这里要循环处理多遍：
第一遍：每个点先算出该点与左边点的和,作为初始path sum
第二遍： 检查每个点左边点的path sum, 与上面点和下面点之前计算的path sum， 找出最小值， 重新加上当前点的数值， 作为新的path sum
因为如果有新的path sum被更新的话， 上下相邻点有要重新计算， 所以第二遍要多次循环，直到不再有点被更新为止。(我做的时候，为了避免麻烦，直接循环了80遍，浪费不少性能)

最后，同样的方法处理第3,4,....列。


对于示例数据来说，就是第一遍得到：
131        804
201        297
630        1433
537        1236
805        1537
然后我们发现对于(3,2)来说，因为上面的297小于左面的630, 所以要更新为297+803 = 1100, 得到如下结果：
131        804
201        297
630        1100
537        1236
805        1537
现在不再有新的点需要更新， 所以第二列计算完毕， 可以进行第三列了。。。。。


用model处理复杂的逻辑对我来说有点吃力， 所以先用pl/sql来做。同时，为了省事，我直接用了之前的外部表和相应的SQL.

1. create or replace procedure Q82 is
   
2.     type tcol is table of number index by pls_integer;
   
3.     type tnums is table of tcol index by pls_integer;
   
4.     nums tnums;
   
5.     col tcol;   
   
6.     minsum number;
   
7.    
   
8. begin
   
9.    for cur in (with td as (select level c from dual connect by level<=80)
   
10. , t as (select rn r, c,
    
11. to_number(substr(line,
    
12. case when c=1 then 1 else instr(line,',',1, c-1)+1 end,
    
13.   case when c=1 then instr(line,',',1, c) -1
    
14.        when c=80 then 10
    
15.        else instr(line,',',1, c) - instr(line,',',1, c-1)-1 end
    
16. )) num
    
17. from euler_q81 t, td)
    
18. select * from t  ) loop
    
19.    nums(cur.r)(cur.c) := cur.num;
    
20.    end loop;
    
21. 
    
22.    col(0) := 99999999;
    
23.    col(81) := 99999999;   
    
24.    for j in 2..80 loop
    
25.      for i in 1..80 loop
    
26.        col(i):= nums(i)(j) + nums(i)(j-1);
    
27.      end loop;
    
28.       for k in 1..80 loop
    
29.            for i in 1..80 loop
    
30.              col(i):= least(col(i-1), col(i+1), nums(i)(j-1)) + nums(i)(j);
    
31.            end loop;
    
32.       end loop;
    
33.      for i in 1..80 loop
    
34.        nums(i)(j):= col(i);
    
35.      end loop;
    
36. 
    
37.    end loop;     
    
38. /*
    
39.    for i in 1..80 loop
    
40.      for j in 1..80 loop
    
41.        dbms_output.put (nums(i)(j) || ' ');
    
42.      end loop;
    
43.        dbms_output.put_line ( ' ');
    
44.    end loop;
    
45. */
    
46.    minsum:=  99999999;   
    
47.    for i in 1..80 loop
    
48.          if nums(i)(80) <minsum then
    
49.            minsum := nums(i)(80);
    
50.          end if;
    
51.    
    
52.    end loop;     
    
53.    dbms_output.put_line ( 'min path sum = ' || minsum);
    
54. 
    
55. end Q82;

复制代码

min path sum = 260324

PL/SQL procedure successfully completed

Executed in 0.281 seconds

SQL>

tree_new_bee

Q83. Find the minimal path sum from the top left to the bottom right by moving left, right, up, and down.

NOTE: This problem is a significantly more challenging version of Problem 81.

In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in bold red and is equal to 2297.

       
131        673        234        103        18
201        96        342        965        150
630        803        746        422        111
537        699        497        121        956
805        732        524        37        331
       

Find the minimal path sum, in matrix.txt (right click and 'Save Link/Target As...'), a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by moving left, right, up, and down.


这次是可以朝任意方向走， 所以难度又大大提高了。