algorytm.org

Implementacja w Delphi/Pascal

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Szybka rekurencja modularna - Implementacja w Delphi/Pascal
Ocena użytkownikóww: *****  / 1
SłabyŚwietny
Nadesłany przez Tomasz Lubiński, 11 stycznia 2007 01:00
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.

Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.

srm.dpr:
// Szybka rekurencja modularna
// www.algorytm.org
// (c) 2007 by Tomasz Lubinski

program srm;
{$APPTYPE CONSOLE}
uses
  SysUtils;

type macierz = array [0..3] of Integer;
  
function potega_macierzy_modulo(n: Integer; t: macierz; a: Integer; b: Integer; m: Integer): macierz;
var
        p1, p2: Integer;
begin
        if n >= 1 then
           begin
                t := potega_macierzy_modulo(n div 2, t, a, b, m);
                p1 := t[0]+t[3];
                p2 := t[2];
                t[0] := t[0]*t[0] + t[1]*t[2];
                t[2] := t[2]*p1;
                t[3] := t[3]*t[3] + t[1]*p2;
                t[1] := t[1]*p1;
                if (n mod 2) <> 0 then
                   begin
                        p1 := t[0];
                        t[0] := t[2];
                        t[2] := t[2]*b + p1*a;
                        p1 := t[1];
                        t[1] := t[3];
                        t[3] := t[3]*b + p1*a;
                   end;
                t[0] := t[0] mod m;
                t[1] := t[1] mod m;
                t[2] := t[2] mod m;
                t[3] := t[3] mod m;
           end
        else
           begin
                t[0] := 1;
                t[1] := 0;
                t[2] := 0;
                t[3] := 1;
           end;

        result := t;
end;


var

t: macierz;
n,a,b,x,y,m,res: Integer;

begin
        //dla ciagu Fibonacciego
        a := 1;
        b := 1;
        x := 1;
        y := 1;

        m := 10; //modulo 10 bo bedziemy obliczac tylko ostatnia cyfre

        writeln('Podaj n');
        readln(n);
        if n = 0 then
           res := x
        else if n = 1 then
           res := y
        else
           begin
                t := potega_macierzy_modulo(n-2, t, a, b, m);
                res := (x*(a*t[0]+b*t[2])+y*(a*t[1]+b*t[3])) mod m;
           end;

        writeln('Ostatnia cyfra liczby Fibonacciego numer ' + IntToStr(n) + ' to ' + IntToStr(res));
        readln;
end.
Dodaj komentarz