ITPub博客

首页 > Linux操作系统 > Linux操作系统 > 一个复杂问题的求解过程(四)

一个复杂问题的求解过程(四)

原创 Linux操作系统 作者:yangtingkun 时间:2008-03-09 23:52:56 0 删除 编辑

今天在PUB里面看到一个帖子:http://www.itpub.net/thread-949571-1-1.html。问题本身并不复杂,不过想借这个问题简单描述一下求解的思路。

前面几篇都是通过SQL的方式求解,这里尝试使用PL/SQL实现。

一个复杂问题的求解过程(一):http://yangtingkun.itpub.net/post/468/456641

一个复杂问题的求解过程(二):http://yangtingkun.itpub.net/post/468/456695

一个复杂问题的求解过程(三):http://yangtingkun.itpub.net/post/468/456778

 

 

在第一篇文章中就提到了,这个算法的实现使用PL/SQL会比用SQL实现容易一些,不过今天尝试完全使用PL/SQL实现,发现也不是想象中那样简单。

由于SQLPL/SQL的实现思路是完全不同的,这里尽量避免受前面SQL方法的影响,而选择了全表通过PL/SQL实现。

另外,提出这个问题的wangfans给出了递归方式的实现,这里就尝试采用循环的实现方式,通过一个存储过程直接获得答案。

SQL> CREATE OR REPLACE PROCEDURE P_RESULT AS
  2   TYPE T_VARRAY IS TABLE OF NUMBER INDEX BY BINARY_INTEGER;
  3   TYPE T_VAR_VAR IS TABLE OF T_VARRAY INDEX BY BINARY_INTEGER;
  4   TYPE T_VARCHAR2_VAR IS TABLE OF NUMBER INDEX BY VARCHAR2(20);
  5   TYPE T_VARCHAR2_VAR_TAB IS TABLE OF T_VARCHAR2_VAR INDEX BY BINARY_INTEGER;
  6   V_TAB T_VAR_VAR;
  7   V_SUM T_VARCHAR2_VAR_TAB;
  8   J VARCHAR2(20);
  9  BEGIN
 10   FOR I IN (SELECT ID, VALUE, POWER FROM T ORDER BY 1) LOOP
 11    FOR K IN 0..I.POWER - 1 LOOP
 12     V_TAB(I.ID)(K) := I.VALUE * K;
 13    END LOOP;
 14    IF I.ID = 1 THEN
 15     FOR K IN V_TAB(1).FIRST..V_TAB(1).LAST LOOP
 16      V_SUM(1)(K) := V_TAB(1)(K);
 17     END LOOP;
 18    ELSE
 19     J := V_SUM(I.ID - 1).FIRST;
 20     WHILE (V_SUM(I.ID - 1).EXISTS(J)) LOOP
 21      FOR K IN V_TAB(I.ID).FIRST..V_TAB(I.ID).LAST LOOP
 22       V_SUM(I.ID)(J || ',' || TO_CHAR(K)) := V_SUM(I.ID - 1)(J) + V_TAB(I.ID)(K);
 23       IF V_SUM(I.ID)(J || ',' || K) > 16 THEN
 24        V_SUM(I.ID).DELETE(J || ',' || K);
 25       END IF;
 26      END LOOP;
 27      J := V_SUM(I.ID - 1).NEXT(J);
 28     END LOOP;
 29    END IF;
 30   END LOOP;
 31   FOR I IN (SELECT MAX(ID) ID FROM T) LOOP
 32    J := V_SUM(I.ID).FIRST;
 33    WHILE (V_SUM(I.ID).EXISTS(J)) LOOP
 34     IF V_SUM(I.ID)(J) = 16 THEN
 35      DBMS_OUTPUT.PUT_LINE(J);
 36     END IF;
 37     J := V_SUM(I.ID).NEXT(J);
 38    END LOOP;
 39   END LOOP;
 40  END;
 41  /

过程已创建。

SQL> SET SERVEROUT ON
SQL> EXEC P_RESULT
0,0,2,0,2
0,0,3,0,1
1,1,0,1,2
1,1,1,1,1
1,1,2,1,0
2,0,1,0,2
2,0,2,0,1
2,0,3,0,0

PL/SQL 过程已成功完成。

过程中利用一个二维数组保存ID对应的加权与VALUE乘积的可能性。并建立了另一个二维数组,保存最终的汇总值。这个二维数组其中一个维度不是数值,而是字符串类型,且这个字符串中保存的值,就是需要计算的各个加权值列表。

采用这个方法效率应该还是相对比较高的,不过由于定义了两个二维数组,空间占用可能会相对大一些。

 

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/4227/viewspace-201865/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论
暂无介绍

注册时间:2007-12-29

  • 博文量
    1955
  • 访问量
    10367025