Fibonacci algorytm Dijkstra w "Scheme" na C#

Odpowiedz Nowy wątek
2011-06-01 20:04
0

Witam. Prosiłbym o pomoc w przetłumaczeniu kodu napisanego w języku Scheme na C#. Szukałem tego algorytmu (Dijkstra ) na obliczanie fib zapisanego chociaż w C++,który bym ogarnął, ale nie udało mi się znaleźć..


(define (fib n)
  (define (fib-aux a b p q count)
    (cond ((= count 0) b)
          ((even? count)
           (fib-aux a
                    b
                    (+ (* p p) (* q q))
                    (+ (* q q) (* 2 p q))
                    (/ count 2)))
          (else
           (fib-aux (+ (* b q) (* a q) (* a p))
                    (+ (* b p) (* a q))
                    p
                    q
                    (- count 1)))))
  (fib-aux 1 0 0 1 n)) 

Pozostało 580 znaków

2011-06-01 21:58
2

pierwszy raz w życiu widzę Scheme na oczy, ale jeśli dobrze się domyślam znaczenia tej składni, będzie to coś w ten deseń:

static int fib_aux(int a,int b,int p,int q,int count)
{
  if (count == 0)
    return b;
  else if (count & 1 == 0)
    return fib_aux(a, b, p*p+q*q, q*q+2*p*q, count/2);
  else
    return fib_aux(b*q+a*q+a*p), b*p+a*q, p, q, count-1);
}

static int fib(int n)
{
  return fib_aux(1,0,0,1,n);
}

niesprawdzane.

edytowany 1x, ostatnio: Azarien, 2011-06-01 22:00
Niestety to co napisałeś nie działa wywala błędy... :( - adixt 2011-06-01 22:15
"wywala błędy" - liczysz na gotowca zamiast zastanowić się co może być nie tak? - Azarien 2011-06-02 00:12
Azarien - scheme jest z rodziny LISP'ów, składnię zrozumiałeś dobrze i tłumaczenie wygląda mi ok, abstrahując od ewentualnych jednej czy dwóch prostych literowek, przez które, zgaduję, autorowi się nie skompilowało:) - quetzalcoatl 2011-06-02 12:24

Pozostało 580 znaków

2011-06-01 22:17
0

Szczerze mówiąc też nie wiedziałem, że coś takiego jak Scheme istnieje ale wygooglowałem to jako "najszybsza" metoda na Fibonacciego. Zna ktoś może lepszą? :) Albo inaczej mam taki algorytm, który oblicza Fibonacciego ze złożonością O(n) przy użyciu mnożenia macierzy, a chciałbym zredukować do O(lg n)(wtedy byłoby naprawdę szybko) i da się to zrobić przez zastosowanie binarnego algorytmu potęgowania macierzy, ale nie wiem jak to zrobić...

public static int Fibonacci(int n)
{
    if (n == 0)
        return 0;
    if (n == 1 || n == 2)
        return 1;

    int[,] A = new int[2, 2] { { 0, 1 }, { 1, 1 } };
    int[,] B = (int[,])A.Clone();
    int[,] C = new int[2, 2];

    n -= 2;

    for (int i = 1; i <= n; i++)
    {
        C[0, 0] = B[0, 0] * A[0, 0] + B[0, 1] * A[1, 0];
        C[0, 1] = B[0, 0] * A[0, 1] + B[0, 1] * A[1, 1];
        C[1, 0] = B[1, 0] * A[0, 0] + B[1, 1] * A[1, 0];
        C[1, 1] = B[1, 0] * A[0, 1] + B[1, 1] * A[1, 1];

        B = (int[,])C.Clone();
    }
    return C[1, 1];
} 
edytowany 2x, ostatnio: adixt, 2011-06-01 23:36

Pozostało 580 znaków

2011-06-01 23:21
1

potęgowanie macierzy

typedef unsigned long long int ull;
#define MUL(a,b) ((ull)a*b)
#define M(a,b,c,d,N) (MUL(a,b)+MUL(c,d))%N
#define TMUL(a,b,c,d,e,f,g,h,N) {unsigned int A=M(e,a,g,b,N), B=M(f,a,h,b,N), \
                                 C=M(e,c,g,d,N);d=M(f,c,h,d,N); a=A; b=B; c=C;}

unsigned long long int fibo(ull n, ull mod){        //fibonacci(n) % mod
    if (n<2) return n;
    n--;
    unsigned long int xa=1,xb=1,xc=1,ra=1,rb=1,rc=1,rd=1,xd=0;  
    while(n){
        if(n&1)
            TMUL(ra,rb,rc,rd,xa,xb,xc,xd,mod)
        n/=2;
        if(n==0) break;
        TMUL(xa,xb,xc,xd,xa,xb,xc,xd,mod)
    }
    return rb%mod;
}

a tu inaczejlong long fib(long longcode>a tu inaczej`long long fib(long long n){
long long i,h,j,k,t;
i=h=1;
j=k=0;
while(n>0){
if(n%2==1){
t=jh;
j=i
h + jk +t;
i=i
k + t;
}
t=hh;
h=2
kh + t;
k=k
k + t;
n=n/2;}
return j;}

edytowany 1x, ostatnio: Xitami, 2011-06-01 23:38

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0