اعداد فیبوناچی- این یک سری اعداد است که در آن هر عدد بعدی برابر است با مجموع دو عدد قبلی: 1، 1، 2، 3، 5، 8، 13، .... گاهی اوقات سریال از صفر شروع می شود: 0، 1، 1، 2، 3، 5، .... در این صورت ما به گزینه اول پایبند خواهیم بود.
فرمول:
F1=1
F2 = 1
F n \u003d F n-1 + F n-2
مثال محاسبه:
F 3 \u003d F 2 + F 1 \u003d 1 + 1 \u003d 2
F 4 \u003d F 3 + F 2 \u003d 2 + 1 \u003d 3
F 5 \u003d F 4 + F 3 \u003d 3 + 2 \u003d 5
F 6 \u003d F 5 + F 4 \u003d 5 + 3 \u003d 8
...
محاسبه عدد n یک سری فیبوناچی با حلقه while
- مقادیر دو عنصر اول سری را به متغیرهای fib1 و fib2 اختصاص دهید، یعنی واحدهایی را به متغیرها اختصاص دهید.
- از کاربر تعداد عنصری را که می‌خواهد مقدار آن را بدست آورد بپرسید. یک عدد به متغیر n اختصاص دهید.
- مراحل زیر را n - 2 بار انجام دهید، زیرا دو عنصر اول قبلاً در نظر گرفته شده است:
- fib1 و fib2 را اضافه کنید و نتیجه را به یک متغیر ذخیره سازی موقت، مانند fib_sum اختصاص دهید.
- fib1 را روی fib2 قرار دهید.
- fib2 را روی fib_sum قرار دهید.
- نمایش مقدار fib2
توجه داشته باشید.اگر کاربر 1 یا 2 را وارد کند، بدنه حلقه هرگز اجرا نمی شود و مقدار اصلی fib2 نمایش داده می شود.
fib1=1 fib2=1 n=input() n=int(n) i=0 در حالی که i< n - 2 : fib_sum = fib1 + fib2 fib1 = fib2 fib2 = fib_sum i = i + 1 print (fib2)
نسخه فشرده کد:
fib1 = fib2 = 1 n = int(ورودی( "عدد عنصر سری فیبوناچی:") ) - 2 در حالی که n > 0 : fib1، fib2 = fib2، fib1 + fib2 n -= 1 چاپ (fib2)
خروجی اعداد فیبوناچی با حلقه for
در این حالت نه تنها مقدار عنصر مورد نظر از سری فیبوناچی نمایش داده می شود، بلکه تمام اعداد تا و شامل آن نیز نمایش داده می شود. برای انجام این کار، خروجی مقدار fib2 در یک حلقه قرار می گیرد.
fib1 = fib2 = 1 n = int (ورودی () ) اگر n باشد< 2 : quit() print (fib1, end= " " ) print (fib2, end= " " ) for i in range (2 , n) : fib1, fib2 = fib2, fib1 + fib2 print (fib2, end= " " ) print ()
مثال اجرا:
10 1 1 2 3 5 8 13 21 34 55
محاسبه بازگشتی عدد n از سری فیبوناچی
- اگر n = 1 یا n = 2، یکی را به شاخه فراخوان برگردانید، زیرا عناصر اول و دوم سری فیبوناچی برابر با یک هستند.
- در تمام موارد دیگر، همان تابع را با آرگومان های n - 1 و n - 2 فراخوانی کنید. نتیجه دو فراخوانی را اضافه کنید و آن را به شاخه فراخوانی برنامه برگردانید.
def فیبوناچی(n) : اگر n در (1، 2) باشد: 1 بازگشت فیبوناچی(n - 1) + فیبوناچی(n - 2) چاپ (fibonacci(10))
فرض کنید n = 4. سپس فیبوناچی (3) و فیبوناچی (2) به صورت بازگشتی فراخوانی می شوند. دومی یک را برمی گرداند و اولی به دو فراخوانی تابع دیگر منجر می شود: فیبوناچی(2) و فیبوناچی(1). هر دو تماس یکی، در مجموع دو تماس برمی گردند. بنابراین، فراخوانی به فیبوناچی (3) عدد 2 را برمی‌گرداند که از تماس با فیبوناچی (2) به عدد 1 اضافه می‌شود. نتیجه 3 به شاخه اصلی برنامه برگردانده می شود. چهارمین عنصر سری فیبوناچی سه است: 1 1 2 3.
برنامه نویسان اعداد فیبوناچی باید از قبل خسته شده باشند. نمونه هایی از محاسبه آنها در همه جا استفاده می شود. همه چیز از آنچه این اعداد ارائه می دهند ساده ترین مثالبازگشت و همچنین هستند مثال خوببرنامه نویسی پویا اما آیا محاسبه آنها در یک پروژه واقعی ضروری است؟ نیازی نیست. نه برنامه نویسی بازگشتی و نه برنامه نویسی پویا گزینه های ایده آلی نیستند. و نه یک فرمول بسته با استفاده از اعداد ممیز شناور. حالا راه درست را به شما می گویم. اما ابتدا بیایید تمام راه حل های شناخته شده را مرور کنیم.این کد برای پایتون 3 است، اگرچه باید برای پایتون 2 نیز کار کند.
ابتدا اجازه دهید تعریف را یادآوری کنم:
F n \u003d F n-1 + F n-2
و F 1 \u003d F 2 \u003d 1.
فرمول بسته
ما از جزئیات صرف نظر می کنیم، اما کسانی که مایلند می توانند با اشتقاق فرمول آشنا شوند. ایده این است که فرض کنیم مقداری x وجود دارد که برای آن F n = x n وجود دارد و سپس x را پیدا کنیم.چه می کند
x n-2 را کاهش می دهیم
معادله درجه دوم را حل می کنیم:
از جایی که "بخش طلایی" ϕ=(1+√5)/2 رشد می کند. با جایگزینی مقادیر اصلی و انجام برخی محاسبات بیشتر، به دست می آوریم:
چیزی که برای محاسبه F n استفاده می کنیم.
از __future__ واردات تقسیم واردات ریاضی def fib(n): SQRT5 = math.sqrt(5) PHI = (SQRT5 + 1) / 2 return int(PHI ** n / SQRT5 + 0.5)
خوب:
سریع و آسان برای n کوچک
بد:
عملیات نقطه شناور مورد نیاز است. n بزرگتر به دقت بیشتری نیاز دارد.
شر:
استفاده از اعداد مختلط برای محاسبه F n از نظر ریاضی زیبا، اما از نظر کامپیوتری زشت است.
بازگشت
واضح ترین راه حل، که قبلاً بارها دیده اید - به احتمال زیاد به عنوان نمونه ای از آنچه بازگشت است. برای کامل شدن دوباره آن را تکرار می کنم. در پایتون می توان آن را در یک خط نوشت:fib = lambda n: fib(n - 1) + fib (n - 2) اگر n > 2 other 1
خوب:
یک پیاده سازی بسیار ساده که تعریف ریاضی را تکرار می کند
بد:
زمان اجرا نمایی برای n بزرگ خیلی آهسته
شر:
سرریز پشته
حفظ کردن
راه حل بازگشتی یک مشکل بزرگ دارد: همپوشانی محاسبات. هنگامی که fib(n) فراخوانی می شود، fib(n-1) و fib(n-2) شمارش می شوند. اما هنگامی که fib(n-1) شمارش می شود، دوباره به طور مستقل fib(n-2) را شمارش می کند - یعنی fib(n-2) دو بار شمارش می شود. اگر استدلال را ادامه دهیم، مشاهده می شود که fib(n-3) سه بار شمارش می شود و به همین ترتیب. تقاطع های خیلی زیادبنابراین، فقط باید نتایج را به خاطر بسپارید تا دوباره آنها را بشمارید. این راه حل زمان و حافظه را به صورت خطی مصرف می کند. من از یک دیکشنری در راه حل استفاده می کنم، اما می توان از یک آرایه ساده نیز استفاده کرد.
M = (0: 0، 1: 1) def fib(n): اگر n در M: بازگشت M[n] M[n] = fib(n - 1) + fib(n - 2) بازگشت M[n]
(در پایتون، این کار را می توان با دکوراتور، functools.lru_cache نیز انجام داد.)
خوب:
فقط بازگشت را به یک راه حل به خاطر بسپارید. زمان اجرای نمایی را به زمان اجرای خطی تبدیل می کند که حافظه بیشتری مصرف می کند.
بد:
حافظه زیادی را تلف می کند
شر:
سرریز پشته احتمالی، مانند بازگشت
برنامه نویسی پویا
پس از حل با حفظ، مشخص می شود که ما به تمام نتایج قبلی نیاز نداریم، بلکه فقط به دو نتیجه آخر نیاز داریم. همچنین، به جای شروع از fib(n) و رفتن به عقب، می توانید از fib(0) شروع کنید و به جلو بروید. کد زیر دارای زمان اجرای خطی و مصرف حافظه ثابت است. در عمل، سرعت حل حتی سریعتر خواهد بود، زیرا هیچ فراخوانی تابع بازگشتی و کار مرتبط وجود ندارد. و کد ساده تر به نظر می رسد.این راه حل اغلب به عنوان نمونه ای از برنامه نویسی پویا ذکر می شود.
تعریف fib(n): a = 0 b = 1 برای __ در محدوده(n): a, b = b, a + b a را برمی گرداند
خوب:
سریع برای کد n کوچک و ساده
بد:
هنوز زمان اجرا خطی است
شر:
بله، چیز خاصی نیست.
جبر ماتریسی
و در نهایت، کمترین پوشش، اما صحیح ترین راه حلی که به طور هوشمندانه از زمان و حافظه استفاده می کند. همچنین می توان آن را به هر دنباله خطی همگن گسترش داد. ایده استفاده از ماتریس است. فقط دیدن آن کافی است
و تعمیم این است که
دو مقداری که قبلاً برای x به دست آوردیم، که یکی از آنها نسبت طلایی بود، مقادیر ویژه ماتریس هستند. بنابراین، راه دیگر برای استخراج فرمول بسته، استفاده از معادله ماتریسی و جبر خطی است.
پس چرا این عبارت مفید است؟ این واقعیت که توان را می توان در زمان لگاریتمی انجام داد. این کار از طریق مربع کردن انجام می شود. نکته اصلی این است که
جایی که عبارت اول برای زوج A، دومی برای فرد استفاده می شود. فقط برای سازماندهی ضرب ماتریس ها باقی مانده است و همه چیز آماده است. کد زیر معلوم می شود. من یک پیاده سازی بازگشتی از pow را سازماندهی کردم زیرا درک آن آسان تر است. نسخه تکراری را اینجا ببینید.
Def pow(x, n, I, mult): """ x را به توان n برمی گرداند. فرض می کنیم I همان ماتریس است که با mult ضرب می شود و n یک عدد صحیح مثبت """ است اگر n == 0: بازگشت I elif n == 1: برگردان x other: y = pow(x, n // 2, I, mult) y = mult(y, y) اگر n % 2: y = mult(x, y) بازگشت y defident_matrix (n): """یک n به n ماتریس هویت را برمی گرداند""" r = list(range(n)) بازگشت [ برای j در r] def matrix_multiply(A, B): BT = list(zip(*B) ) بازگشت [ برای row_a در A] def fib(n): F = pow([, ], n,identity_matrix(2), matrix_multiply) بازگشت F
خوب:
اندازه حافظه ثابت، زمان لگاریتمی
بد:
کد پیچیده تر است
شر:
شما باید با ماتریس ها کار کنید، اگرچه آنها چندان بد نیستند
مقایسه عملکرد
ارزش مقایسه فقط نوع برنامه نویسی پویا و ماتریس را دارد. اگر آنها را با تعداد کاراکترهای عدد n مقایسه کنیم، معلوم می شود که راه حل ماتریسیبه صورت خطی، در حالی که راه حل برنامه نویسی پویا نمایی است. یک مثال عملی محاسبه fib(10*6) است، عددی که بیش از دویست هزار کاراکتر خواهد داشت.N=10**6
محاسبه fib_matrix: fib(n) در مجموع دارای 208988 رقم است، محاسبه 0.24993 ثانیه طول کشید.
محاسبه fib_dynamic: fib(n) در مجموع دارای 208988 رقم است، محاسبه 11.83377 ثانیه طول کشید.
اظهارات نظری
ارتباط مستقیمی با کد بالا ندارد، این اظهار نظر هنوز هم مورد توجه است. نمودار زیر را در نظر بگیرید:
بیایید تعداد مسیرهای به طول n را از A تا B بشماریم. به عنوان مثال، برای n = 1 یک مسیر داریم، 1. برای n = 2، دوباره یک مسیر، 01. برای n = 3، دو مسیر داریم. ، 001 و 101 می توان به سادگی نشان داد که تعداد مسیرهای به طول n از A تا B دقیقاً F n است. پس از نوشتن ماتریس مجاورت برای نمودار، همان ماتریسی را خواهیم گرفت که در بالا توضیح داده شد. این یک نتیجه شناخته شده از نظریه گراف است که برای یک ماتریس مجاورت معین A، وقوع در A n تعداد مسیرهایی به طول n در نمودار است (یکی از مشکلات ذکر شده در فیلم Good Will Hunting).
چرا چنین علامت هایی در لبه ها وجود دارد؟ معلوم می‌شود که وقتی یک دنباله نامتناهی از نمادها را روی یک بی‌نهایت در هر دو جهت دنباله‌ای از مسیرها در یک نمودار در نظر می‌گیریم، چیزی به نام «subshifts از نوع محدود» به دست می‌آید که نوعی سیستم دینامیک نمادین است. این تغییر خاص نوع نهاییبه عنوان "تغییر نسبت طلایی" شناخته می شود و با مجموعه ای از "کلمات ممنوعه" (11) ارائه می شود. به عبارت دیگر، دنباله های باینری خواهیم داشت که در هر دو جهت نامحدود هستند و هیچ جفتی از آنها مجاور نخواهد بود. آنتروپی توپولوژیکی این سیستم دینامیکی برابر با نسبت طلایی φ است. جالب است که چگونه این عدد به صورت دوره ای در حوزه های مختلف ریاضیات ظاهر می شود.
خیلی اوقات در المپیادهای مختلف مشکلاتی از این دست وجود دارد که در نگاه اول به نظر می رسد با یک شمارش ساده می توان آنها را حل کرد. اما اگر عدد را بشماریم گزینه ها، سپس بلافاصله شاهد ناکارآمدی این رویکرد خواهیم بود: برای مثال، یک تابع بازگشتی ساده در زیر منابع قابل توجهی را از قبل در عدد 30 فیبوناچی مصرف می کند، در حالی که در المپیادها زمان حل اغلب به 1-5 ثانیه محدود می شود.
int fibo(int n) ( if (n == 1 || n == 2) ( return 1; ) else ( return fibo(n - 1) + fibo (n - 2); ) )
بیایید به این فکر کنیم که چرا این اتفاق می افتد. به عنوان مثال، برای محاسبه fibo(30) ابتدا fibo(29) و fibo(28) را محاسبه می کنیم. اما در همان زمان، برنامه ما "فراموش می کند" که fibo(28) ما قبلا محاسبه شده استهنگامی که به دنبال فیبو (29) هستید.
اشتباه اصلی این رویکرد مستقیم این است که مقادیر یکسان آرگومان های تابع بارها محاسبه می شوند - و اینها عملیات نسبتاً فشرده منابع هستند. روش برنامه نویسی پویا به ما کمک می کند تا از محاسبات تکراری خلاص شویم - این تکنیکی است که هنگام استفاده از آن کار به وظایف فرعی کلی و تکراری تقسیم می شود که هر کدام فقط 1 بار حل می شود - این کارایی برنامه را به میزان قابل توجهی افزایش می دهد. این روش به تفصیل در توضیح داده شده است، همچنین نمونه هایی از حل مسائل دیگر وجود دارد.
ساده ترین راه برای بهبود عملکرد ما این است که به یاد داشته باشیم چه مقادیری را قبلاً محاسبه کرده ایم. برای انجام این کار، ما باید یک آرایه اضافی را معرفی کنیم، که به عنوان نوعی "کش" برای محاسبات ما عمل می کند: قبل از محاسبه یک مقدار جدید، بررسی می کنیم که آیا قبلا محاسبه شده است یا خیر. اگر محاسبه کردیم، مقدار آماده را از آرایه می گیریم و اگر آن را محاسبه نکردیم، باید آن را بر اساس موارد قبلی محاسبه کنیم و برای آینده به خاطر بسپاریم:
حافظه نهان داخلی؛ int fibo(int n) ( if (cache[n] == 0) ( if (n == 1 || n == 2) ( cache[n] = 1; ) other ( cache[n] = fibo(n - 1) + fibo(n - 2); ) ) cache[n];
از آنجایی که در این کار تضمین شده است که برای محاسبه مقدار N به مقدار (N-1) نیاز داریم، بازنویسی فرمول به صورت تکراری دشوار نخواهد بود - ما به سادگی آرایه خود را در یک ردیف پر می کنیم تا زمانی که به مقدار مورد نظر برسیم. سلول مورد نظر:
<= n; i++) { cache[i] = cache + cache; } cout << cache;
اکنون می توانیم متوجه شویم که وقتی مقدار F(N) را محاسبه می کنیم، مقدار F(N-3) از قبل برای ما تضمین شده است. هرگزنیاز نخواهد داشت. یعنی کافی است فقط دو مقدار را در حافظه ذخیره کنیم - F(N-1) و F(N-2). علاوه بر این، به محض اینکه F(N) را محاسبه کردیم، ذخیره سازی F(N-2) معنی خود را از دست می دهد. بیایید سعی کنیم این افکار را در قالب کد بنویسیم:
//دو مقدار قبلی: int cache1 = 1; int cache2 = 1; //مقدار جدید int cache3; برای (int i = 2; i<= n; i++) { cache3 = cache1 + cache2; //Вычисляем новое значение //Абстрактный cache4 будет равен cache3+cache2 //Значит cache1 нам уже не нужен?.. //Отлично, значит cache1 -- то значение, которое потеряет актуальность на следующей итерации. //cache5 = cache4 - cache3 =>از طریق تکرار، cache2 ارتباط خود را از دست خواهد داد، یعنی. باید به cache1 تبدیل شود //به عبارت دیگر cache1 -- f(n-2), cache2 -- f(n-1), cache3 -- f(n). //بگذارید N=n+1 (عددی که در تکرار بعدی محاسبه می کنیم). سپس n-2=N-3، n-1=N-2، n=N-1. // مطابق با واقعیت های جدید، مقادیر متغیرهای خود را بازنویسی می کنیم: cache1 = cache2; cache2 = cache3; ) قطع كردن<< cache3;
یک برنامه نویس با تجربه می داند که کد بالا به طور کلی مزخرف است، زیرا cache3 هرگز استفاده نمی شود (فوراً در cache2 نوشته می شود)، و کل تکرار را می توان تنها با استفاده از یک عبارت بازنویسی کرد:
حافظه پنهان = 1; حافظه پنهان = 1; برای (int i = 2; i<= n; i++) { cache = cache + cache; //При i=2 устареет 0-й элемент //При i=3 в 0 будет свежий элемент (обновили его на предыдущей итерации), а в 1 -- ещё старый //При i=4 последним элементом мы обновляли cache, значит ненужное старьё сейчас в cache //Интуитивно понятно, что так будет продолжаться и дальше } cout << cache;
برای کسانی که نمی توانند بفهمند جادوی مدولو چگونه کار می کند، یا فقط می خواهند فرمول غیر واضح تر را ببینند، راه حل دیگری وجود دارد:
int x = 1; int y = 1; برای (int i = 2; i< n; i++) { y = x + y; x = y - x; } cout << "Число Фибоначчи: " << y;
سعی کنید اجرای این برنامه را دنبال کنید: از درستی الگوریتم مطمئن خواهید شد.
P.S. به طور کلی، یک فرمول واحد برای محاسبه هر عدد فیبوناچی وجود دارد که نیازی به تکرار یا بازگشت ندارد:
Const double SQRT5 = sqrt(5); const double PHI = (SQRT5 + 1) / 2; int fibo(int n)( return int(pow(PHI, n) / SQRT5 + 0.5)؛ )
اما، همانطور که ممکن است حدس بزنید، نکته مهم این است که قیمت محاسبه توان اعداد غیر صحیح و همچنین خطای آنها بسیار زیاد است.