Ocena użytkownikóww: ***** / 2
Nadesłany przez Rafał Świetlicki, 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.java:
// Szybka rekurencja modularna
// www.algorytm.org
// (c) 2007 by Rafal Swietlicki
public class SRM {
private static int[] potega_macierzy_modulo(int n, int t[], int a, int b, int m)
{
int p1,p2;
if(n>=1)
{
t = 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]*=p1;
t[3]=t[3]*t[3]+t[1]*p2;
t[1]*=p1;
if(n%2 != 0)
{
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;
}
t[0]%=m;
t[1]%=m;
t[2]%=m;
t[3]%=m;
}
else
{
t[0]=1;
t[1]=0;
t[2]=0;
t[3]=1;
}
return t;
}
/**
* @param args
*/
public static void main(String[] args) {
int t[] = new int[4];
int n,a,b,x,y,m,res;
//dla ciagu Fibonacciego
a = 1;
b = 1;
x = 1;
y = 1;
m = 10; //modulo 10 bo bedziemy obliczac tylko ostatnia cyfre
System.out.println("Podaj n");
n = Console.readInt("");
if (n==0) res = x;
else if (n==1) res = y;
else
{
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])) % m;
}
System.out.println("Ostatnia cyfra liczby Fibonacciego numer " + n + " to " + res);
}
}