递归with真是个好东西

tree_new_bee

原帖由 newkid 于 2010-12-10 09:17 发表
我把它称为“分解子查询”，自己杜撰的翻译。

好像还比较贴切。

tree_new_bee

看了看newkid的写法，才知道我先去构造序列表很愚蠢。
这个东西的思维习惯需要逐步适应。


修改后的阶乘：

with targ as (select 30 d from dual)
, prod(lastnum, lastprod) as
(select 1, 1  from dual
union all
select lastnum+1, (lastnum+1)*lastprod
from prod,targ
where lastnum < d
)
select * from prod,targ where lastnum = d

dingjun123

不错，再写写可以射你一下

tree_new_bee

原帖由 dingjun123 于 2010-12-10 12:50 发表
不错，再写写可以射你一下

什么叫射一下？

tree_new_bee

原帖由 newkid 于 2010-12-10 03:23 发表


前阵子我写了个辗转相除法求n个数的最小公倍数，你要不要来试一下？

两个数的好整：

with targ as (select 35 n1, 14 n2 from dual)
, gcd(a, b) as
(select n1 , n2  from targ
union all
select b,
mod(a,b)
from gcd where b>0
)
select * from gcd where b=0


多个数好麻烦，递归里面套递归， 一时想不清楚怎么往一块组装。

byzhuning

楼主好样儿的，楼主加油～～

tree_new_bee

苦战老半天， 终于整出一个n个数的gcd.

with t as (
select 20 n  from dual union all
select 30 from dual union all
select 10 from dual union all
select 45 from dual)
,t1 as (select n n1, lead(n ,1) over (order by n desc) n2 from t )
,t2 as (select max(n1) n1, max(n2)n2  from t1 )
, mgcd(a,b, a2, b2) as
(select n1, n2, n1, n2 from t2
union all
select
case when b2=0 then (select max(n) from t where n<a) else a end,
case when b2=0 then a2 else b end,
case when b2=0 then (select max(n) from t where n<a) else b2 end,
case when b2=0 then  a2 else mod(a2, b2) end
from mgcd where a is not null
)
cycle a,b,a2,b2 set iscycle to 'y' default 'n'
select min(a2) from mgcd where b2=0


SQL> /

   MIN(A2)
----------
         5

Executed in 0.031 seconds

SQL>

tree_new_bee

有了gcd, 看似计算lcm很容易， 实现起来却是很麻烦。

找了一个比较简单的递归算法来实现多个数的lcm

with t as ( select 20 n1, 30 n2, 10 n3, 45 n4 from dual)
, mlcm (m1, m2, m3, m4)
as ( select n1, n2, n3, n4 from t
union all
select
case when m1 = least(m1,m2,m3,m4) then m1+n1 else m1 end,
case when m2 = least(m1,m2,m3,m4) then m2+n2 else m2 end,
case when m3 = least(m1,m2,m3,m4) then m3+n3 else m3 end,
case when m4 = least(m1,m2,m3,m4) then m4+n4 else m4 end
from mlcm, t where not (m1= m2 and m1=m3 and m1=m4 )
)
select max(m1) from mlcm

SQL> /

   MAX(M1)
----------
       180

Executed in 0.063 seconds



至于辗转相除计算lcm, 实际上还是没做出来。 newkid, 我先欠着， 以后再说。

tree_new_bee

在顶楼，把做过的问题总结了一下。

tree_new_bee

菲波纳契数列。
弄过难的，这个就很简单了。

WITH t(r,a,b) AS (
SELECT 1,0,1 FROM DUAL
UNION ALL
SELECT r+1
      ,b
      ,a+b
  FROM t
WHERE r<10
)
cycle a,b set iscycle to 'y' default 'n'
select r,b from t

12  /

         R          B
---------- ----------
         1          1
         2          1
         3          2
         4          3
         5          5
         6          8
         7         13
         8         21
         9         34
        10         55

10 rows selected

Executed in 0.203 seconds

SQL>

如果不是从1,1开始， 而是从1,2开始， cycle语句就能省下了。