سري معروف فيبوناچي كه معرف حضور شما هست. سري از اعداد است كه هر عدد آن مساوي حاصل جمع دو عدد ماقبل آن است. دو عدد اول اين سري هم 0 و 1 هستند. اگر بخواهيم اين الگوريتم را به صورت يك متد بازگشتي نمايش دهيم به صورت زير خواهد بود: 1. public static int Fibonacci(int x) 2. { 3. if (x <= 1) 4. return 1; 5. return Fibonacci(x - 1) + Fibonacci(x - 2); 6. }
1. public static int Fibonacci(int x) 2. { 3. if (x <= 1) 4. return 1; 5. return Fibonacci(x - 1) + Fibonacci(x - 2); 6. }
اين الگوريتم چند مشكل دارد: الف) براي اعداد بزرگ حتي با بكارگيري Int64 و يا double و امثال آن هم باز به جواب نخواهيم رسيد (براي مثال 1500 را بررسي كنيد). ب) بسيار كند است.
در دات نت 4 براي كار با اعداد بزرگ، فضاي نام System.Numerics معرفي شده است كه حاوي نوع جديدي از اعداد به نام BigInteger است. اكنون اگر الگوريتم سري فيبوناچي را بر اساس اين نوع داده جديد بازنويسي كنيم خواهيم داشت: 1. using System; 2. using System.Collections.Generic; 3. using System.Numerics; //needs a ref. to this assembly 4. 5. namespace Fibonaci 6. { 7. public class CFibonacci 8. { 9. 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 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. }
1. using System; 2. using System.Collections.Generic; 3. using System.Numerics; //needs a ref. to this assembly 4. 5. namespace Fibonaci 6. { 7. public class CFibonacci 8. { 9. 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 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. }
و مثالي در مورد نحوه استفاده از آن:
1. using System; 2. using System.Linq; 3. 4. namespace Fibonaci 5. { 6. class Program 7. { 8. static void Main() 9. { 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. }
براي نمونه با عدد 12000 خروجي برنامه در كسري از ثانيه (و نه چند دقيقه يا ساعت) به شرح زير خواهد بود:
1. fib(12000)=514263424911336592579396579289954520826834443526829600435873863248622 2. 65414020714013892551476261070010099275571144059579167356039437242089427136323689 3. 02207956221569622791450891447905907668251232675988098246382902426783148546665404 4. 47372384043164600945249911273857878346679362876357499204290285069442042444471200 5. 52292329349103672302428662317285015525888210397583707071480178840772972692357054 6. 71823998861896761687119434646250991702691100894769561810834542099577336821493905 7. 41651658937860506067011215222435859797671748514023462634575877112541265857011723 8. 31453990415231608729534781720381122965899871018532003735284559342372552627132300 9. 63895825396012087948050855095233633638445668687440232926253620457459973889510838 10. 23542785159371236389909470974738599166720611351903568781845409425624666559791912 11. 02212289710838873334773835118391287956725504426150461421914844191810523257658770 12. 99885492757927034409234340065928400769741802132203888929463702342324148343605275 13. 28928280472094493359682662519127203581813404104542972181231076224891404730611459 14. 03321942693225066038987483163709402601230467054944349111055850348779989058517069 15. 96087626795709205215727843443054577680024507650678240240742421270422674907476927 16. 22422733945450760323640619100021663675080870429299040891840880753646474330069332 17. 72320218334582268219906763463261387161318500503970491314781100556494361063341371 18. 43577787961183154125538371204296752028496084633103476783071177779604042581017888 19. 28257784920659671082363171157289668904381254080676855815524987553372657063695970 20. 39668109161449140707240711279859427919912443872405284305891366802954763421905970 21. 15206311458187449420118838775707435857999310870199585760807680179258273461000460 22. 97527064929564528474349547038178370043823628944670926601955537657427194815893365 23. 88494863101667547896798728140224921584809355334379707156342620570496834086358692 24. 30946467203330676206265047960072392991634456381998479411463182171816379650120684 25. 35082399788137090460167819041845511951296934273988759169877839532492294430334328 26. 46972905198131530224288922834125154211248159843609629469051889033085360540770480 27. 25633451201705370447586177546577777759300410144166197439355903631773088812515215 28. 09638377918595294747887970034209028019490210394392422302403687059119407005858379 29. 52137098994457236290005745735420803758853723206992134642997705010940581386168427 30. 47382973672816710014652632509888958851675894223117421829434728942878605569971512 31. 65291783384910157203679779458354245579846973830472593370160977523707902575129803 32. 072039857524154149354311250529579592001
نشانی ایمیل شما منتشر نخواهد شد. بخشهای موردنیاز علامتگذاری شدهاند *
Current ye@r *
Leave this field empty
Copyright © 2010 Dlbook Team