algorytm.org

Implementacja w Ada



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 Ada
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.adb:
-- Szybka rekurencja modularna
-- www.algorytm.org
-- (c) 2007 by Tomasz Lubinski

with Text_IO;
use Text_IO;

procedure srm is

type macierz is array (0..3) of Integer;

procedure potega_macierzy_modulo(n: Integer; t: in out macierz; a: Integer; b: Integer; m: Integer) is
        p1, p2: Integer;
begin
        if n >= 1 then
                potega_macierzy_modulo(n/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
                        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 if;
                t(0) := t(0) mod m;
                t(1) := t(1) mod m;
                t(2) := t(2) mod m;
                t(3) := t(3) mod m;
        else
                t(0) := 1;
                t(1) := 0;
                t(2) := 0;
                t(3) := 1;
        end if;
end;


t: macierz;
n,a,b,x,y,m,res: Integer;
s: String := "        ";
length: Integer;

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

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

        Put_Line("Podaj n");
        Get_Line(s, length);
        n := Integer'Value(s);
        
        if n = 0 then
           res := x;
        elsif n = 1 then
           res := y;
        else
                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 if;

        Put_Line("Ostatnia cyfra liczby Fibonacciego numer " & Integer'Image(n) & " to " & Integer'Image(res));

end;
Dodaj komentarz