写一个求和的程序，谢谢

janezhou_0806

we have a list of integer {1, 2, 3, 4, 5, 6, 7, 8, 9 }. Set each item as R, where i = 1..9.

write code to return each possible combination whose sum is less or equal to 25.

For example,

1;
1,2;
1, 2, 3;
....

dingjun123

SQL> WITH t AS
  2  (SELECT LEVEL val FROM dual
  3  CONNECT BY LEVEL<10)
  4  SELECT   trim(both ',' FROM a.val_list) val_list
  5     FROM
  6   (SELECT SYS_CONNECT_BY_PATH (val, ',') || ',' val_list
  7               FROM   t
  8               CONNECT BY  val > PRIOR val) a, t b
  9      WHERE    INSTR (a.val_list, ',' || b.val || ',') > 0
10      GROUP BY a.val_list
11     HAVING   SUM (b.val) <= 25
12  ORDER BY 1;

VAL_LIST
--------------------------------------------------------------------------------
1
1,2
1,2,3
1,2,3,4
1,2,3,4,5
1,2,3,4,5,6
1,2,3,4,5,7
1,2,3,4,5,8
1,2,3,4,5,9
1,2,3,4,6
1,2,3,4,6,7

...............
6,8,9
6,9
7
7,8
7,8,9
7,9
8
8,9
9

323 rows selected

影之哀伤

老丁做法不错，娴熟的运用了SQL的各种函数，打到求解的目的

但是感觉没做到效率上的最大化，很多无效的组合可以不用去尝试的。。感觉

〇〇

with t as(select level l from dual connect by level<=9)
,u (l,s) as (select cast(l as varchar(100)) l,l s from t
union all
select t.l||','||u.l l,u.s+t.l s from u,t where
cast(t.l as varchar(100))< substr(u.l,1,1) and u.s+t.l<=25)
select l from u ;

newkid

原帖由 影之哀伤 于 2011-5-30 20:53 发表
老丁做法不错，娴熟的运用了SQL的各种函数，打到求解的目的

但是感觉没做到效率上的最大化，很多无效的组合可以不用去尝试的。。感觉

你来写一个？
递归WITH可以在遍历过程中求和。

xqmei

Another option:

SQL> WITH t AS
  2   (SELECT LEVEL val FROM dual CONNECT BY LEVEL < 10)
  3  SELECT *
  4    FROM (SELECT ltrim(sys_connect_by_path(val, '+'), '+') vallist,
  5                 extractvalue(dbms_xmlgen.getxmltype('select 0' ||
  6                                                     sys_connect_by_path(val,'+') ||
  7                                                     ' cost from dual'),
  8                              '/ROWSET/ROW/COST') res
  9            FROM t
10          CONNECT BY val > PRIOR val)
11   WHERE res <= 25;

VALLIST                                                                          RES
-------------------------------------------------------------------------------- --------------------------------------------------------------------------------
1                                                                                1
1+2                                                                              3
1+2+3                                                                            6
1+2+3+4                                                                          10
1+2+3+4+5                                                                        15
1+2+3+4+5+6                                                                      21
1+2+3+4+5+7                                                                      22
1+2+3+4+5+8                                                                      23
1+2+3+4+5+9                                                                      24
....

gyhgood

原帖由 xqmei 于 2011-5-31 02:50 发表
Another option:

SQL> WITH t AS
  2   (SELECT LEVEL val FROM dual CONNECT BY LEVEL < 10)
  3  SELECT *
  4    FROM (SELECT ltrim(sys_connect_by_path(val, '+'), '+') vallist,
  5                 extractvalue(dbms_xmlgen.getxmltype('select 0' ||
  6                                                     sys_connect_by_path(val,'+') ||
  7                                                     ' cost from dual'),
  8                              '/ROWSET/ROW/COST') res
  9            FROM t
10          CONNECT BY val > PRIOR val)
11   WHERE res  

好复杂。。。。。。

3legcat

with t as (select level val from dual connect by level < 10)
select ltrim(p, ',') from (
  select val, sys_connect_by_path(val, ',') p,
  sys_connect_by_path(rpad('*',val,'*'), '/'),
  length(sys_connect_by_path(rpad('*',val,'*'), '/')) - level cnt
  from t
  connect by prior val < val
) where cnt <= 25

影之哀伤

后面的方法感觉大同小异呢。。

如果数组是1至10000，求和数位10的话，大家的语句效率应该不错。。。
看我自己写递归。。。。。。。。。

newkid

原帖由 影之哀伤 于 2011-5-31 17:41 发表
后面的方法感觉大同小异呢。。

如果数组是1至10000，求和数位10的话，大家的语句效率应该不错。。。
看我自己写递归。。。。。。。。。

如果有负数你打算怎么办？