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_cs/srm.cs:
// Szybka rekurencja modularna
// www.algorytm.org
// (c) 2007 by Tomasz Lubinski
using System;
namespace srm_cs
{
/// <summary>
/// Szybka rekurencja modularna.
/// </summary>
class SRM
{
/// <summary>
/// Calculates
/// - - n
/// | 0 1 |
/// | |
/// | a b | mod m
/// - -
/// </summary>
/// <param name="n">n</param>
/// <param name="t">t - matrix with result</param>
/// <param name="a">a</param>
/// <param name="b">b</param>
/// <param name="m">m</param>
/// <returns>t - matrix with result</returns>
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;
}
/// <summary>
/// The main entry point for the application.
/// </summary>
[STAThread]
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
Console.WriteLine("Podaj n");
n = int.Parse(Console.ReadLine());
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;
}
Console.WriteLine("Ostatnia cyfra liczby Fibonacciego numer " + n + " to " + res);
}
}
}