algorytm.org

Implementacja w C#

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 C#
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_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); 
		}
	}
}
Dodaj komentarz