SQLonacci sequence

kata programming

مساله:

بله باز هم فیبوناچی! اما این بار با SQL.

شما باید select ای بنویسید که 90 عبارت اول فیبوناچی را تولید کند. نام ستون باید number باشد.

دنباله فیبوناچی به صورت زیر است:

 0, 1, 1, 2, 3, 5, 8, 13, ..., 89, 144, 233, 377, ...

که :

f(0) = 0
f(1) = 1
...
f(n) = f(n-1) + f(n-2)

Description:

Yes it’s Fibonacci yet again ! But this time it’s SQL.

You need to create a select statement which will produce first 90 Fibonnacci numbers. The column name is – number

Fibbonaccii sequence is:

 0, 1, 1, 2, 3, 5, 8, 13, ..., 89, 144, 233, 377, ...

where

f(0) = 0
f(1) = 1
...
f(n) = f(n-1) + f(n-2)

Have fun!


WITH RECURSIVE fib(number,n2) AS (
      SELECT 0::bigint,1::bigint
    UNION ALL
      SELECT n2::bigint,number+n2::bigint 
      FROM fib
)
SELECT number FROM fib LIMIT 90
select * from (
  values
  (0), (1), (1), (2), (3), (5), (8), (13), (21), (34), 
  (55), (89), (144), (233), (377), (610), (987), (1597), (2584), (4181), 
  (6765), (10946), (17711), (28657), (46368), (75025), (121393), (196418), (317811), (514229), 
  (832040), (1346269), (2178309), (3524578), (5702887), (9227465), (14930352), (24157817), (39088169), (63245986), 
  (102334155), (165580141), (267914296), (433494437), (701408733), (1134903170), (1836311903), (2971215073), (4807526976), (7778742049), 
  (12586269025), (20365011074), (32951280099), (53316291173), (86267571272), (139583862445), (225851433717), (365435296162), (591286729879), (956722026041), 
  (1548008755920), (2504730781961), (4052739537881), (6557470319842), (10610209857723), (17167680177565), (27777890035288), (44945570212853), (72723460248141), (117669030460994), 
  (190392490709135), (308061521170129), (498454011879264), (806515533049393), (1304969544928657), (2111485077978050), (3416454622906707), (5527939700884757), (8944394323791464), (14472334024676221), 
  (23416728348467685), (37889062373143906), (61305790721611591), (99194853094755497), (160500643816367088), (259695496911122585), (420196140727489673), (679891637638612258), (1100087778366101931), (1779979416004714189)
) as fibonacci (number)
select 0 as number union all
select 1 as number union all
select 1 as number union all
select 2 as number union all
select 3 as number union all
select 5 as number union  all
select 8 as number union all
select 13 as number union all
select 21 as number union all
select 34 as number union all
select 55 as number union all
select 89 as number union all
select 144 as number union all
select 233 as number union all
select 377 as number union all
select 610 as number union all
select 987 as number union all
select 1597 as number union all
select 2584 as number union all
select 4181 as number union all
select 6765 as number union all
select 10946 as number union all
select 17711 as number union all
select 28657 as number union all
select 46368 as number union all
select 75025 as number union all
select 121393 as number union all
select 196418 as number union all
select 317811 as number union all
select 514229as number union all
select 832040 as number union all
select 1346269 as number union all
select 2178309 as number union all
select 3524578 as number union all
select 5702887 as number union all
select 9227465 as number union all
select 14930352 as number union all
select 24157817 as number union all
select 39088169 as number union all
select 63245986 as number union all
select 102334155as number union all
select 165580141 as number union all
select 267914296 as number union all
select 433494437as number union all
select 701408733 as number union all
select 1134903170 as number union all
select 1836311903 as number union all
select 2971215073 as number union all
select 4807526976 as number union all
select 7778742049 as number union all
select 12586269025 as number union all
select 20365011074 as number union all
select 32951280099 as number union all
select 53316291173 as number union all
select 86267571272 as number union all
select 139583862445 as number union all
select 225851433717 as number union all
select 365435296162 as number union all
select 591286729879 as number union all
select 956722026041 as number union all
select 1548008755920 as number union all
select 2504730781961 as number union all
select 4052739537881 as number union all
select 6557470319842 as number union all
select 10610209857723 as number union all
select 17167680177565 as number union all
select 27777890035288 as number union all
select 44945570212853 as number union all
select 72723460248141 as number union all
select 117669030460994 as number union all
select 190392490709135 as number union all
select 308061521170129 as number union all
select 498454011879264 as number union all
select 806515533049393 as number union all
select 1304969544928657 as number union all
select 2111485077978050 as number union all
select 3416454622906707 as number union all
select 5527939700884757 as number union all
select 8944394323791464 as number union all
select 14472334024676221 as number union all
select 23416728348467685 as number union all
select 37889062373143906 as number union all
select 61305790721611591 as number union all
select 99194853094755497 as number union all
select 160500643816367088 as number union all
select 259695496911122585 as number union all
select 420196140727489673 as number union all
select 679891637638612258 as number union all
select 1100087778366101931 as number union all
select 1779979416004714189 order by number; 
CREATE OR REPLACE FUNCTION comb(n integer, k integer) RETURNS decimal AS $$
        BEGIN
                RETURN (n!)/((k!)*((n-k)!));
        END;
$$ LANGUAGE plpgsql;


CREATE FUNCTION f(n integer) RETURNS numeric AS $$
    SELECT
    SUM(comb(n-k-1,k))::numeric AS result
    FROM generate_series(0,(floor((n-1)/2))::integer) k;
$$ LANGUAGE SQL;

SELECT 0 AS number
UNION ALL
SELECT f(i)::bigint AS number
FROM generate_series(1,89) i;
CREATE TABLE numbers (
 id INTEGER,
 number bigint
 );

INSERT INTO numbers (id, number) VALUES (1, 0);
INSERT INTO numbers (id, number) VALUES (2, 1);
DO $$
BEGIN
  FOR counter IN 3..90 LOOP
    INSERT INTO numbers (id, number) VALUES (counter, (SELECT SUM(number) FROM numbers n WHERE n.id = counter - 1 OR n.id = counter - 2));
  END LOOP;
END; $$;

SELECT number FROM numbers
create function fib(n int) returns setof bigint 
as $$
declare  
  a bigint := 0;
  b bigint := 1;
  m bigint := 0;
  i int := 0;
begin
  while i < n loop
    return next a;
    m := a;
    a := b;
    b := b + m;
    i := i + 1;
  end loop;
end $$
language plpgsql;
select * from fib(90) as number

دیدگاهتان را بنویسید