ITPub博客

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

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

原创 Linux操作系统 作者:yangtingkun 时间:2008-03-06 23:44:02 0 删除 编辑

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

 

 

首先建立测试用表:

SQL> CREATE TABLE T (ID NUMBER, VALUE NUMBER, POWER NUMBER);

表已创建。

SQL> INSERT INTO T VALUES (1, 2, 3);

已创建 1 行。

SQL> INSERT INTO T VALUES (2, 1, 2);

已创建 1 行。

SQL> INSERT INTO T VALUES (3, 4, 4);

已创建 1 行。

SQL> INSERT INTO T VALUES (4, 5, 2);

已创建 1 行。

SQL> INSERT INTO T VALUES (5, 4, 3);

已创建 1 行。

SQL> COMMIT;

提交完成。

由于楼主对于问题描述的不是很清晰,这里再简单描述一下。表中有三列,第一列是表的ID,第二列是一个ID对应的因子。而第三列是第二列值加权的上限。

以第一条记录为例,这条记录对应的因子是2,最大加权小于3,也就是说,这条记录可以对应三个值,024分布对应POWER列的加权值为012

现在根据配置表中给出的因子和每个因此的最大加权范围,找出因子加权后的总和为16时,所对应的所有加权值的情况。

一个简单的例子:每个加权值都是1的话,总和就是16,因此这就是所求的一种情况。

SQL> SELECT 2*1 + 1*1 + 4*1 + 5*1 + 4*1 FROM DUAL;

2*1+1*1+4*1+5*1+4*1
-------------------
                 16

同理,2/0/3/0/0也是一种情况:

SQL> SELECT 2*2 + 1*0 + 4*3 + 5*0 + 4*0 FROM DUAL;

2*2+1*0+4*3+5*0+4*0
-------------------
                 16

2/0/0/0/3虽然相加的结果也是16,但是对于ID5的记录,加权必须小于3,因此这组加权值是不正确的。

了解了需求就可以选择方法了,这种问题通过PL/SQL的过程性语言来实现要容易一些,这里尝试使用SQL来实现。

下面分析需求,SQL最终要实现的是一组乘积的和,并过滤和为16的结果。如何得到乘积是比较困难的,由于表中只给出了最大加权范围,因此需要通过构造的方式,获取到因子和所有可能加权的乘积。

为了构造出连续的数值,一般通过CONNECT BY ROWNUM < 数值的方式来实现,但是对于目前的情况,需要对多个多组记录分别构造,而直接使用CONNECT BY ROWNUM会造成大量的重复结果,因此这里选择了使用子查询作为列的方式来避免重复记录的出现。但是构造的加权结果一般都大于1条,对于子查询作为列的方式只能返回一条记录,这里使用了聚集函数MAX配合属性查询的SYS_CONNECT_BY_PATH来实现。

SQL> SELECT ID, VALUE,
  2   (
  3    SELECT MAX(SYS_CONNECT_BY_PATH(VALUE * (LEVEL - 1), ','))
  4    FROM DUAL CONNECT BY ROWNUM <= POWER
  5   ) POWER
  6  FROM T
  7  ;

        ID      VALUE POWER
---------- ---------- ------------------------------
         1          2 ,0,2,4
         2          1 ,0,1
         3          4 ,0,4,8,12
         4          5 ,0,5
         5          4 ,0,4,8

现在已经获得了加权的列表,需要通过SQL将其展开。最简单的思路就是通过5SQL,获取每一个ID所有可能的因子加权乘积。

5SQL关联起来,计算乘积的和,并过滤结果为16的情况,就可以得到最终结果了。

SQL> WITH T1 AS
  2  (
  3  SELECT ID, VALUE,
  4   (
  5    SELECT MAX(SYS_CONNECT_BY_PATH(VALUE * (LEVEL - 1), ','))
  6    FROM DUAL CONNECT BY ROWNUM <= POWER
  7   ) POWER
  8  FROM T
  9  )
 10  SELECT LEVEL - 1 LV,
 11   SUBSTR(POWER,
 12    INSTR(POWER, ',', 1, ROWNUM) + 1,
 13    INSTR(POWER || ',', ',', 1, ROWNUM + 1) - INSTR(POWER, ',', 1, ROWNUM) - 1) VALUE
 14  FROM (SELECT * FROM T1 WHERE ID = 1)
 15  CONNECT BY LEVEL <= LENGTH(POWER) - LENGTH(REPLACE(POWER, ','));

        LV VALUE
---------- ------------------------------
         0 0
         1 2
         2 4

这就是获取ID1的所有加权因子乘积的SQL

只需要将5SQL关联并求和,就可以得到最终的结果:

SQL> WITH T1 AS
  2  (
  3  SELECT ID, VALUE,
  4   (
  5    SELECT MAX(SYS_CONNECT_BY_PATH(VALUE * (LEVEL - 1), ','))
  6    FROM DUAL CONNECT BY ROWNUM <= POWER
  7   ) POWER
  8  FROM T
  9  )
 10  SELECT L1, L2, L3, L4, L5
 11  FROM
 12  (
 13   SELECT A.LV L1, B.LV L2, C.LV L3, D.LV L4, E.LV L5,
 14    A.VALUE + B.VALUE + C.VALUE + D.VALUE + E.VALUE TOTAL
 15   FROM
 16   (
 17    SELECT LEVEL - 1 LV,
 18     SUBSTR(POWER,
 19      INSTR(POWER, ',', 1, ROWNUM) + 1,
 20      INSTR(POWER || ',', ',', 1, ROWNUM + 1) - INSTR(POWER, ',', 1, ROWNUM) - 1) VALUE
 21    FROM (SELECT * FROM T1 WHERE ID = 1)
 22    CONNECT BY LEVEL <= LENGTH(POWER) - LENGTH(REPLACE(POWER, ','))
 23   ) A,
 24   (
 25    SELECT LEVEL - 1 LV,
 26     SUBSTR(POWER,
 27      INSTR(POWER, ',', 1, ROWNUM) + 1,
 28      INSTR(POWER || ',', ',', 1, ROWNUM + 1) - INSTR(POWER, ',', 1, ROWNUM) - 1) VALUE
 29    FROM (SELECT * FROM T1 WHERE ID = 2)
 30    CONNECT BY LEVEL <= LENGTH(POWER) - LENGTH(REPLACE(POWER, ','))
 31   ) B,
 32   (
 33    SELECT LEVEL - 1 LV,
 34     SUBSTR(POWER,
 35      INSTR(POWER, ',', 1, ROWNUM) + 1,
 36      INSTR(POWER || ',', ',', 1, ROWNUM + 1) - INSTR(POWER, ',', 1, ROWNUM) - 1) VALUE
 37    FROM (SELECT * FROM T1 WHERE ID = 3)
 38    CONNECT BY LEVEL <= LENGTH(POWER) - LENGTH(REPLACE(POWER, ','))
 39   ) C,
 40   (
 41    SELECT LEVEL - 1 LV,
 42     SUBSTR(POWER,
 43      INSTR(POWER, ',', 1, ROWNUM) + 1,
 44      INSTR(POWER || ',', ',', 1, ROWNUM + 1) - INSTR(POWER, ',', 1, ROWNUM) - 1) VALUE
 45    FROM (SELECT * FROM T1 WHERE ID = 4)
 46    CONNECT BY LEVEL <= LENGTH(POWER) - LENGTH(REPLACE(POWER, ','))
 47   ) D,
 48   (
 49    SELECT LEVEL - 1 LV,
 50     SUBSTR(POWER,
 51      INSTR(POWER, ',', 1, ROWNUM) + 1,
 52      INSTR(POWER || ',', ',', 1, ROWNUM + 1) - INSTR(POWER, ',', 1, ROWNUM) - 1) VALUE
 53    FROM (SELECT * FROM T1 WHERE ID = 5)
 54    CONNECT BY LEVEL <= LENGTH(POWER) - LENGTH(REPLACE(POWER, ','))
 55   ) E
 56  )
 57  WHERE TOTAL = 16;

        L1         L2         L3         L4         L5
---------- ---------- ---------- ---------- ----------
         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

已选择8行。

至此,通过硬编码式的SQL得到了最终的结果。

 

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

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

注册时间:2007-12-29

  • 博文量
    1955
  • 访问量
    10368993