Ocena użytkownikóww: ***** / 1
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;