Euler Project 挨个做- 之二 (Q51-Q78)

newkid

我写了个PLSQL不知道对不对？

DECLARE

   lv_limit NUMBER := 100;
   TYPE t_num IS TABLE OF NUMBER INDEX BY PLS_INTEGER;
   lv_num t_num;
   lv_cnt   t_num;
   lv_cnt2  t_num;
   lv_sum NUMBER ;
   lv_ptr NUMBER;
BEGIN
   lv_cnt(0):=1;
   FOR i IN 1..lv_limit LOOP
       lv_num(i):=i;
   END LOOP;
   
   FOR i IN REVERSE 1..lv_num.COUNT LOOP
       lv_sum := lv_num(i);
       lv_cnt2:=lv_cnt;
       WHILE lv_sum<=lv_limit LOOP
             lv_ptr := 0;
             WHILE lv_ptr IS NOT NULL LOOP
                   EXIT WHEN lv_ptr+lv_sum>lv_limit;
                   IF NOT lv_cnt.EXISTS(lv_ptr+lv_sum) THEN
                      lv_cnt(lv_ptr+lv_sum):= lv_cnt2(lv_ptr);
                   ELSE
                      lv_cnt(lv_ptr+lv_sum):= lv_cnt(lv_ptr+lv_sum)+lv_cnt2(lv_ptr);
                   END IF;
                   lv_ptr := lv_cnt2.NEXT(lv_ptr);
             END LOOP;
             lv_sum := lv_sum + lv_num(i);
       END LOOP;
   END LOOP;
   DBMS_OUTPUT.PUT_LINE(lv_cnt(lv_limit)-1);
END;
/

190569291

PL/SQL procedure successfully completed.

Elapsed: 00:00:00.02

tree_new_bee

newkid 发表于 2012-2-9 00:49
我写了个PLSQL不知道对不对？

DECLARE

测试了几个，都没问题。

用你的结果去解答，是对的。


但程序没看明白， 能不能把思路说说？

tree_new_bee

newkid 发表于 2012-2-9 00:49
我写了个PLSQL不知道对不对？

DECLARE

看到你的结果，就知道我179#的方法根本行不通了。
处理1.9亿个字符串，根本不可能在可接受的时间做到。

newkid

这是递归的思路，假设1~N个数，在N加入之前，F(1),F(2),...F(LIMIT) 表示和为1,2,...LIMIT 分解为加数1~N-1的方法的种数（F(0)恒为1），那么把N加入后，其可能的和就是：N+1,N+2,N+3,... 2N+1,2N+3,2N+3....3N+1,3N+2,3N+3.... LIMIT，这里面有重复的。
此处1N,2N,3N,...等等体现在下面WHILE循环的lv_sum变量。
F()的值体现在代码中的lv_cnt2数组。
随便拿一个为例，比如 3N+K 这个和，它必须包含加数3N, 所以拆法种数等于和为K的拆法种数（每种上面加3N而已）。
如果这个和是首次出现，拆法个数就相当于和为K的拆法的个数F(K)。
如果非首次出现（这个和可能在2N或1N的时候已经算过），那么现在就是在原来基础上增加F(K)。　

lv_cnt保存的是在lv_cnt2基础上增加N的各种拆法的个数，把所有N的组合算完了，再算N+1时这个结果就转移到lv_cnt2.

因为这些和肯定是连续的，昨天的第二个WHILE可以改为FOR LOOP.

DECLARE
   lv_limit NUMBER := 100;
   TYPE t_num IS TABLE OF NUMBER INDEX BY PLS_INTEGER;
   lv_cnt   t_num;
   lv_cnt2  t_num;
   lv_sum NUMBER ;
BEGIN
   lv_cnt(0):=1;  ---------- 和为0肯定只有一种拆法
   
   FOR i IN 1..lv_limit LOOP
       lv_sum := i;
       lv_cnt2:=lv_cnt;
       WHILE lv_sum<=lv_limit LOOP
             FOR lv_ptr IN 0..lv_cnt2.COUNT-1 LOOP
                   EXIT WHEN lv_ptr+lv_sum>lv_limit;
                   IF NOT lv_cnt.EXISTS(lv_ptr+lv_sum) THEN ----- 这个和首次出现
                      lv_cnt(lv_ptr+lv_sum):= lv_cnt2(lv_ptr);
                   ELSE
                      lv_cnt(lv_ptr+lv_sum):= lv_cnt(lv_ptr+lv_sum)+lv_cnt2(lv_ptr);
                   END IF;
             END LOOP;
             lv_sum := lv_sum + i;
       END LOOP;
   END LOOP;
   DBMS_OUTPUT.PUT_LINE(lv_cnt(lv_limit)-1);  ---------- 最后输出的是F(100), 因为至少必须有两个加数，100自身不算所以减去1
END;
/

tree_new_bee

看了半天，还是半懂。
还是自己琢磨了一下算法：

假设和为m，组合中最大的数为n,这样的组合数记为f(m,n)个
题目中求的就是f(100,99)   (因为至少两个数，所以不能含有100)

对于f(m,n)可分三种情况：
m<n, 因为超过和数m的n不可能出现， 所以f(m,n) = f(m,m)
m=n, 因为含有n的组合只有一种，剩下的不含n的组合也就是最大数为n-1的组合， 因此f(m,n) = 1+ f(m,n-1)
m>n, 分为含n和不含n两种情况考虑：含n的情况， 余下的数的和为m-n, 就是f(m-n, n);  不含n的情况，也就是最大数为n-1的组合，即f(m, n-1)
         所以f(m,n) = f(m-n, n) +  f(m, n-1)

有了这个，其实用excel都可以很轻松的算出任意f(m,n)

tree_new_bee

上面算法的pl/sql实现：

1. create or replace procedure Q76(arg number default 100) is
   
2. type t_nlist is table of number index by pls_integer;
   
3. type t_nlistlist is table of t_nlist index by pls_integer;
   
4. 
   
5. nlist t_nlistlist;
   
6. sm number;
   
7. begin
   
8. for i in 1..arg loop
   
9.     nlist(1)(i) := 1;
   
10.     nlist(i)(1) := 1;
    
11. end loop;
    
12.   
    
13. for i in 2..arg loop
    
14.   for j in 2..arg loop
    
15.       if j<i then
    
16.         nlist(i)(j) := nlist(i-j)(j) + nlist(i)(j-1);
    
17.       elsif j=i then
    
18.         nlist(i)(j) := nlist(i)(j-1) + 1;
    
19.       elsif j>i then
    
20.         nlist(i)(j) :=nlist(i)(j-1);
    
21.       end if;
    
22.   end loop;
    
23. 
    
24. end loop;
    
25. dbms_output.put_line(nlist(arg)(arg-1));
    
26. end Q76;

复制代码

非常快！

SQL> exec q76(100);

190569291

PL/SQL procedure successfully completed

Executed in 0 seconds

〇〇

tree_new_bee 发表于 2012-2-10 15:10
上面算法的pl/sql实现：非常快！

SQL> exec q76(100);

算法是王

tree_new_bee

同样的算法用model语句来实现。

1. with targ as (select 100 arg from dual)
   
2. ,t as (select level d  from targ connect by level<=arg)
   
3. ,t2 as (select tr.d r, tc.d c, 1  num from t tr, t tc)
   
4. ,t3 as (select r,c, num
   
5. from t2
   
6. MODEL
   
7.     DIMENSION BY (r,c)
   
8.     MEASURES (num)
   
9.     RULES update
   
10.      (
    
11.      num[any, any] order by r , c
    
12.      = case when cv(r)>1 and cv(c)>1 and cv(r)<cv(c) then num[cv(r),cv(r)]
    
13.             when cv(r)>1 and cv(c)>1 and cv(r)=cv(c) then 1+num[cv(r),cv(c)-1]
    
14.             when cv(r)>1 and cv(c)>1 and cv(r)>cv(c) then num[cv(r)-cv(c),cv(c)]+num[cv(r),cv(c)-1]  
    
15.             else  num[cv(r),cv(c)] end
    
16. ) order by r , c)
    
17. select r,c,num from t3,targ where r=arg and c=arg-1

复制代码

R          C        NUM
---------- ---------- ----------
       100         99  190569291

Executed in 0.078 seconds

newkid

你的不含n变成f(m-n,n)的思路比我要简洁，我的思路是考虑f(m,n-1)如何变成f(m,n)。
MODEL的简洁真是无敌，但不知道思路就看不懂了。

tree_new_bee

同样的思路，做Q31 ( http://www.itpub.net/forum.php?m ... 10&pid=17000140 )
比较起来，以前用的方法无论从简洁性还是从运行效率来讲，都太笨拙了。

1. create or replace procedure Q31new(arg number default 200) is
   
2. type t_nlist is table of number index by pls_integer;
   
3. type t_nlistlist is table of t_nlist index by pls_integer;
   
4. 
   
5. nlist t_nlistlist;
   
6. coins t_nlist;
   
7. sm number;
   
8. begin
   
9. 
   
10.   coins(1) := 1;
    
11.   coins(2) := 2;
    
12.   coins(3) := 5;
    
13.   coins(4) := 10;
    
14.   coins(5) := 20;
    
15.   coins(6) := 50;
    
16.   coins(7) := 100;
    
17.   coins(8) := 200;
    
18. 
    
19. for i in 1..arg loop
    
20.     nlist(1)(i) := 1;
    
21.     nlist(i)(1) := 1;
    
22. end loop;
    
23.   
    
24. for i in 2..arg loop
    
25.   for j in 2..8 loop
    
26.       if coins(j)<i then
    
27.         nlist(i)(coins(j)) := nlist(i-coins(j))(coins(j)) + nlist(i)(coins(j-1));
    
28.       elsif coins(j)=i then
    
29.         nlist(i)(coins(j)) := nlist(i)(coins(j-1)) + 1;
    
30.       elsif coins(j)>i then
    
31.         nlist(i)(coins(j)) :=nlist(i)(coins(j-1));
    
32.       end if;
    
33.   end loop;
    
34. 
    
35. end loop;
    
36. dbms_output.put_line(nlist(arg)(arg));
    
37. end Q31new;

复制代码

SQL> exec q31new(200)

73682

PL/SQL procedure successfully completed

Executed in 0.016 seconds