PDA

View Full Version : فيبوناچي , دا ت نت 4



saed2006
پنج شنبه 16 اردیبهشت 1389, 12:35 عصر
سري معروف فيبوناچي كه معرف حضور شما هست. سري از اعداد است كه هر عدد آن مساوي حاصل جمع دو عدد ماقبل آن است. دو عدد اول اين سري هم 0 و 1 هستند.
اگر بخواهيم اين الگوريتم را به صورت يك متد بازگشتي نمايش دهيم به صورت زير خواهد بود:



01.public static int Fibonacci(int x)
02.{
03. if (x <= 1)
04. return 1;
05. return Fibonacci(x - 1) + Fibonacci(x - 2);
06.}

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 است.
اكنون اگر الگوريتم سري فيبوناچي را بر اساس اين نوع داده جديد بازنويسي كنيم خواهيم داشت:



01.using System;
02.using System.Collections.Generic;
03.using System.Numerics; //needs a ref. to this assembly
04.
05.namespace Fibonaci
06.{
07. public class CFibonacci
08. {
09. public static int Fibonacci(int x)
10. {
11. if (x <= 1)
12. return 1;
13. return Fibonacci(x - 1) + Fibonacci(x - 2);
14. }
15.
16. public static IEnumerable<BigInteger> BigFib(Int64 toNumber)
17. {
18. BigInteger previous = 0;
19. BigInteger current = 1;
20.
21. for (Int64 y = 1; y <= toNumber; y++)
22. {
23. var auxiliar = current;
24. current += previous;
25. previous = auxiliar;
26. yield return current;
27. }
28. }
29. }
30.}

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;
}
}
}
}و مثالي در مورد نحوه استفاده از آن:



01.using System;
02.using System.Linq;
03.
04.namespace Fibonaci
05.{
06. class Program
07. {
08. static void Main()
09. {
10. foreach (var i in CFibonacci.BigFib(10))
11. {
12. Console.WriteLine("{0}", i);
13. }
14.
15. var num = 12000;
16. var fib = CFibonacci.BigFib(num).Last();
17. Console.WriteLine("fib({0})={1}", num, fib);
18.
19. Console.WriteLine("Press a key...");
20. Console.ReadKey();
21. }
22. }
23.}

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 خروجي برنامه در كسري از ثانيه (و نه چند دقيقه يا ساعت) به شرح زير خواهد بود:

view plaincopy to clipboardprint?
01.fib(12000)=514263424911336592579396579289954520 826834443526829600435873863248622
02.65414020714013892551476261070010099275571144059 579167356039437242089427136323689
03.02207956221569622791450891447905907668251232675 988098246382902426783148546665404
04.47372384043164600945249911273857878346679362876 357499204290285069442042444471200
05.52292329349103672302428662317285015525888210397 583707071480178840772972692357054
06.71823998861896761687119434646250991702691100894 769561810834542099577336821493905
07.41651658937860506067011215222435859797671748514 023462634575877112541265857011723
08.31453990415231608729534781720381122965899871018 532003735284559342372552627132300
09.63895825396012087948050855095233633638445668687 440232926253620457459973889510838
10.23542785159371236389909470974738599166720611351 903568781845409425624666559791912
11.02212289710838873334773835118391287956725504426 150461421914844191810523257658770
12.99885492757927034409234340065928400769741802132 203888929463702342324148343605275
13.28928280472094493359682662519127203581813404104 542972181231076224891404730611459
14.03321942693225066038987483163709402601230467054 944349111055850348779989058517069
15.96087626795709205215727843443054577680024507650 678240240742421270422674907476927
16.22422733945450760323640619100021663675080870429 299040891840880753646474330069332
17.72320218334582268219906763463261387161318500503 970491314781100556494361063341371
18.43577787961183154125538371204296752028496084633 103476783071177779604042581017888
19.28257784920659671082363171157289668904381254080 676855815524987553372657063695970
20.39668109161449140707240711279859427919912443872 405284305891366802954763421905970
21.15206311458187449420118838775707435857999310870 199585760807680179258273461000460
22.97527064929564528474349547038178370043823628944 670926601955537657427194815893365
23.88494863101667547896798728140224921584809355334 379707156342620570496834086358692
24.30946467203330676206265047960072392991634456381 998479411463182171816379650120684
25.35082399788137090460167819041845511951296934273 988759169877839532492294430334328
26.46972905198131530224288922834125154211248159843 609629469051889033085360540770480
27.25633451201705370447586177546577777759300410144 166197439355903631773088812515215
28.09638377918595294747887970034209028019490210394 392422302403687059119407005858379
29.52137098994457236290005745735420803758853723206 992134642997705010940581386168427
30.47382973672816710014652632509888958851675894223 117421829434728942878605569971512
31.65291783384910157203679779458354245579846973830 472593370160977523707902575129803
32.072039857524154149354311250529579592001

ramin_rp
پنج شنبه 16 اردیبهشت 1389, 13:30 عصر
منبع: وبلاگ وحید نصیری

http://vahidnasiri.blogspot.com/2010/04/4.html#comments