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.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.