سري معروف فيبوناچي كه معرف حضور شما هست. سري از اعداد است كه هر عدد آن مساوي حاصل جمع دو عدد ماقبل آن است. دو عدد اول اين سري هم 0 و 1 هستند.
اگر بخواهيم اين الگوريتم را به صورت يك متد بازگشتي نمايش دهيم به صورت زير خواهد بود:
public static int Fibonacci(int x)
{
if (x <= 1)
return 1;
return Fibonacci(x - 1) + Fibonacci(x - 2);
}
اين الگوريتم چند مشكل دارد:
الف) براي اعداد بزرگ حتي با بكارگيري Int64 و يا double و امثال آن هم باز به جواب نخواهيم رسيد (براي مثال 1500 را بررسي كنيد).
ب) بسيار كند است.
در دات نت 4 براي كار با اعداد بزرگ، فضاي نام System.Numerics معرفي شده است كه حاوي نوع جديدي از اعداد به نام BigInteger است.
اكنون اگر الگوريتم سري فيبوناچي را بر اساس اين نوع داده جديد بازنويسي كنيم خواهيم داشت:
using System;
using System.Collections.Generic;
using System.Numerics; //needs a ref. to this assembly
namespace Fibonaci
{
public class CFibonacci
{
public static int Fibonacci(int x)
{
if (x <= 1)
return 1;
return Fibonacci(x - 1) + Fibonacci(x - 2);
}
public static IEnumerable<BigInteger> BigFib(Int64 toNumber)
{
BigInteger previous = 0;
BigInteger current = 1;
for (Int64 y = 1; y <= toNumber; y++)
{
var auxiliar = current;
current += previous;
previous = auxiliar;
yield return current;
}
}
}
}
using System;
using System.Linq;
namespace Fibonaci
{
class Program
{
static void Main()
{
foreach (var i in CFibonacci.BigFib(10))
{
Console.WriteLine("{0}", i);
}
var num = 12000;
var fib = CFibonacci.BigFib(num).Last();
Console.WriteLine("fib({0})={1}", num, fib);
Console.WriteLine("Press a key...");
Console.ReadKey();
}
}
}
براي نمونه با عدد 12000 خروجي برنامه در كسري از ثانيه (و نه چند دقيقه يا ساعت) به شرح زير خواهد بود:
fib(12000)=514263424911336592579396579289954520826834443526829600435873863248622
65414020714013892551476261070010099275571144059579167356039437242089427136323689
02207956221569622791450891447905907668251232675988098246382902426783148546665404
47372384043164600945249911273857878346679362876357499204290285069442042444471200
52292329349103672302428662317285015525888210397583707071480178840772972692357054
71823998861896761687119434646250991702691100894769561810834542099577336821493905
41651658937860506067011215222435859797671748514023462634575877112541265857011723
31453990415231608729534781720381122965899871018532003735284559342372552627132300
63895825396012087948050855095233633638445668687440232926253620457459973889510838
23542785159371236389909470974738599166720611351903568781845409425624666559791912
02212289710838873334773835118391287956725504426150461421914844191810523257658770
99885492757927034409234340065928400769741802132203888929463702342324148343605275
28928280472094493359682662519127203581813404104542972181231076224891404730611459
03321942693225066038987483163709402601230467054944349111055850348779989058517069
96087626795709205215727843443054577680024507650678240240742421270422674907476927
22422733945450760323640619100021663675080870429299040891840880753646474330069332
72320218334582268219906763463261387161318500503970491314781100556494361063341371
43577787961183154125538371204296752028496084633103476783071177779604042581017888
28257784920659671082363171157289668904381254080676855815524987553372657063695970
39668109161449140707240711279859427919912443872405284305891366802954763421905970
15206311458187449420118838775707435857999310870199585760807680179258273461000460
97527064929564528474349547038178370043823628944670926601955537657427194815893365
88494863101667547896798728140224921584809355334379707156342620570496834086358692
30946467203330676206265047960072392991634456381998479411463182171816379650120684
35082399788137090460167819041845511951296934273988759169877839532492294430334328
46972905198131530224288922834125154211248159843609629469051889033085360540770480
25633451201705370447586177546577777759300410144166197439355903631773088812515215
09638377918595294747887970034209028019490210394392422302403687059119407005858379
52137098994457236290005745735420803758853723206992134642997705010940581386168427
47382973672816710014652632509888958851675894223117421829434728942878605569971512
65291783384910157203679779458354245579846973830472593370160977523707902575129803
072039857524154149354311250529579592001
