محاسبه سری فیبوناچی و فاکتوریل در SQL !

[محمد سلیم آبادی]

جالبه بدونید که در SQL هم می توانید از مفهوم بازگشتی (Recursive) استفاده کنید.

با استفاده از recursive CTE شما می توانید مسائلی که ماهیت بازگشتی دارند را پیاده سازی کنید.

بطور مثال الگوریتم های سری فیبوناچی و فاکتوریل را در نظر بگیرید.


n!= (n-1)! * n
1!=1
--------------------------
fib(n)= fib(n-1)+fib(n-2)
fib(1), fib(2)=1


در اینجا این دو الگوریتم با استفاده از recursive CTE پیاده سازی می شوند.

کافی است که آنها را در یک پنجره query اجرا (execute) کنید.





WITH fac AS (
SELECT
cast(1 as decimal(38)) AS [value]
,1 AS [Level]

UNION ALL SELECT
cast(f.[value] * ([level]+1) as decimal(38)) AS [value]
, f.[level] + 1 AS [level]
FROM
fac f
WHERE
[level] < 30
)

SELECT cast(level as char(2))+'! ='+cast(value as varchar(100)) FROM fac
OPTION (MAXRECURSION 0)


/*
1 ! =1
2 ! =2
3 ! =6
4 ! =24
5 ! =120
6 ! =720
7 ! =5040
8 ! =40320
9 ! =362880
10! =3628800
11! =39916800
12! =479001600
13! =6227020800
14! =87178291200
15! =1307674368000
16! =20922789888000
17! =355687428096000
18! =6402373705728000
19! =121645100408832000
20! =2432902008176640000
21! =51090942171709440000
22! =1124000727777607680000
23! =25852016738884976640000
24! =620448401733239439360000
25! =15511210043330985984000000
26! =403291461126605635584000000
27! =10888869450418352160768000000
28! =304888344611713860501504000000
29! =8841761993739701954543616000000
30! =265252859812191058636308480000000

(30 row(s) affected)
*/





;WITH fib AS (
SELECT
CAST(1 AS DECIMAL(38)) AS [value]
, CAST(0 AS DECIMAL(38)) AS [prec]
, CAST(1 AS INT) AS [Level]

UNION ALL SELECT
CAST(f.[value] + f.[prec] AS DECIMAL(38)) AS [value]
, f.[value] AS [prec]
, f.[level] + 1 AS [level]
FROM
fib f
WHERE
[level] < 30
)
SELECT [level], [value] FROM fib
OPTION (MAXRECURSION 0)


/*
level value
----------- ---------------------------------------
1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
10 55
11 89
12 144
13 233
14 377
15 610
16 987
17 1597
18 2584
19 4181
20 6765
21 10946
22 17711
23 28657
24 46368
25 75025
26 121393
27 196418
28 317811
29 514229
30 832040

(30 row(s) affected)
*/

[محمد سلیم آبادی]

پیمایش یک برگ به سمت ریشه ی آن



http://www.barnamenevis.org/forum/attachment.php?attachmentid=34858&stc=1&d=1249901846


فرض کنید ما می خواهیم ریشه ی گره K را از درخت فوق محاسبه کنیم.
ابتدا باید پدر این ریشه را بدست آوریم سپس پدر پدر اش را تا جایی که گره پدری نداشته باشد.


Root (V) = Parent (Parent (… (Parent (V))))


پس مساله ما حالت بازگشتی دارد. در نتیجه با استفاده از recursive CTE قابل محاسبه است.


برای ذخیره درخت فوق در یک جدول از کد زیر استفاده کنید و سپس گره های درخت را بصورت سطر در جدول وارد کنید.


CREATE TABLE Tree
(
ID CHAR(1) PRIMARY KEY,
Parent CHAR(1)
)

ID Parent
---------- ----------
A NULL
B A
C A
D A
E C
F C
G D
H G
I G
J G
K H



به کد زیر توجه کنید


DECLARE @a VARCHAR(100),
@NODE CHAR(1);
SET @a='';
SET @NODE='K';


WITH Navigation AS (
SELECT
(SELECT Parent FROM Tree WHERE ID=@NODE) AS [value]
,1 AS [Level]

UNION ALL SELECT
(SELECT Parent FROM Tree WHERE ID=n.[value]) AS [value]
, n.[level] + 1 AS [level]
FROM
Navigation n
WHERE
(SELECT Parent FROM Tree WHERE ID=n.[value]) IS NOT NULL
)



SELECT @a=@a+CAST([value] AS VARCHAR(1))+' --> '
FROM Navigation
ORDER BY [level] DESC


SELECT @a+@NODE


پس از اجرای query فوق نتیجه به شکل زیر خواهدا بود:




Result

A --> D --> G --> H --> K

(1 row(s) affected)

[Emad23]

Jaleb bood in Query ha ...
khaste nabashin