دنباله فیبوناچی معروف این ویژگی را دارد که هر اصطلاح مجموع دو اصطلاح قبلی است. ما با f (0) = 0 ، f (1) = 1 برای مورد پایه شروع می کنیم. سپس ، f (2) به دو اصطلاح قبلی تبدیل می شود: f (2) = f (1)+f (0) = 1 ؛f (3) = f (2)+f (1) = 2 و غیره. به طور کلی ما دریافت می کنیم:

در اینجا چند اصطلاح اول در این سریال آورده شده است:

نوشتن یک برنامه برای محاسبه اصطلاح نهم احتمالاً ساده ترین سؤال برنامه نویسی پویا و اصلی در مصاحبه های فنی است. این برچسب در LeetCode آسان است (که فرصتی را که در مصاحبه علوم داده به آن می پردازید افزایش می دهد). راه حل استاندارد برنامه نویسی پویا که از شما انتظار می رود زمان O (n) است. با داشتن برخی از ریاضیات ، می توان یک فرم بسته را نیز دریافت کرد (که شامل نسبت طلایی ، ϕ). این سؤال همچنین در برنامه نویسی رقابتی نشان می دهد که در آن تعداد فیبوناچی بسیار بزرگ مورد نیاز است. شما انتظار دارید که راه حل فرم بسته با تمام زیبایی های آن انتخاب طبیعی باشد. اما مردم تمایل دارند با گزینه سوم که ظریف تر است ، عبور کنند و بروند. چرا این خواهد بود؟اگر می خواهید جزئیات را پرش کنید ، فقط به بخش آخر (5) مرور کنید.

1 سوال مصاحبه فنی آسان

ساده ترین راه برای حل این سوال احتمالاً بازگشت است. من کد Python را در زیر اضافه می کنم و باید از آنجا که بسیار شبیه به کد شبه است ، بتوانید آن را دنبال کنید.

خواهید دید که مقادیر زیادی در پشته تماس وجود دارد که بارها و بارها محاسبه می شوند (تعداد 4 نفر را حساب می کنید). اگر شماره فیبوناچی I-Th را در یک آرایه ذخیره کنیم ، فقط می توانیم آن را از آنجا که یک بار محاسبه شده است بخوانیم ، نیازی نیست هر بار یک درخت کامل از تماس ها را شاخه کنیم. این امر باعث می شود پیچیدگی زمان O (n) به جای نمایی باشد و به دلیل ذخیره مورد نیاز ، پیچیدگی فضایی O (n) را اضافه کند (تمام شماره های N را ذخیره کنید). اما بیایید به آن فکر کنیم ، هنگام محاسبه هر شماره خاص ، ما فقط به دو مورد قبلی احتیاج داریم. بنابراین ، ما حتی نیازی به ذخیره کل آرایه نداریم ، فقط دو عنصر قبلی در هر زمان معین. این منجر به نسخه تیز شده زیر می شود که زمان (n) زمان و o (1) فضای (فروشگاه ها فقط دو عنصر قبلی) است.

در مرحله بعد ، ما رابطه عود را که می دانیم درست است وصل می کنیم. ما دو اصطلاح اول را در جمع جدا می کنیم تا از برخورد با F (-1) و F (-2) جلوگیری کنیم. این ترفند ساده برای جلوگیری از دویدن به F (-1) و F (-2) چیزی است که من بعد از مدت طولانی به این کار برمی گردم و سعی می کنم دوباره به این نتیجه برسم.

نگران نباشید اگر بلافاصله نمی توانید این را ببینید ، اما با توجه به سری هندسی ، 1/(1-A) = A+A²+A³+... عبارت فوق به ما می گوید که شماره فیبوناچی N-Th (که استضریب z^n در بیان) تعداد روشهای متمایز است که از آن استفاده می کنیم فقط با استفاده از 1 و 2. و به نظر می رسد که این دنباله عود امضا را برآورده می کند (معادله (1)) ، زیرا برای دریافت n $ از این طریق می توانید ابتدا (n-2) $ دریافت کنید و یک صورتحساب 2 $ اضافه کنید یا (n-1) $ دریافت کنیدو یک قبض 1 دلار اضافه کنید.

اما چگونه می توانیم F (n) را بدست آوریم؟اول ، شما دو ریشه مخرج را پیدا می کنید (یک چند جمله ای درجه دوم است ، بنابراین دو ریشه نیز خواهد داشت) ، ϕ و ψ ، که در آن نسبت طلایی است:

و ψ = 1-درجه. بنابراین عبارت در معادله (3) می تواند به طور برابر نوشته شود:

من در معادلات فوق جزئیات زیادی را بیان کردم. این صفحه دارای یک پیاده روی دقیق تر است. اما از اینجا ، فرم بسته برای دنباله فیبوناچی در معرض دید است زیرا f (n) فقط ضریب z^n در f (z) است.

3 نمایش سریع

Note that the magnitude of ϕ>1 در حالی که از ψ. بنابراین وقتی N بزرگ می شود ، می توانیم اصطلاح ψ^n را نادیده بگیریم زیرا به سرعت کوچک می شود. اما ما هنوز باید ϕ را به قدرت n-th بالا ببریم (آن را با خود N-1 بار ضرب کنید). آیا این بدان معنی است که ما از بخش 1 چیزی بیش از راه حل برنامه نویسی پویا کسب نکرده ایم (زمان اجرا هنوز O (n) است)؟نه از آنجا که یک الگوریتم کارآمد برای محاسبه نمایندگان وجود دارد. ما می خواهیم ϕ^n را پیدا کنیم. اگر n یکنواخت باشد ، می توانیم بگوییم:

اکنون ϕ^(n/2) می تواند یک بار محاسبه شود و سپس با خودش ضرب شود. این باعث می شود محاسبات ما (N/2+1) به جای (N-1). اما پس از آن ما می توانیم همین کار را در اصطلاح ϕ^(n/2) انجام دهیم و تمام راه را به پایین برگردانیم. تعداد ضرب های مورد نیاز با این الگوریتم تقسیم و فتح به O (log n) می رود.

مقاله ویکی پدیا در این مورد بینش عمومی را برجسته می کند:

بنابراین ، ما اکنون یک بیان شکل بسته ظریف داریم که می تواند در زمان O (log n) ارزیابی شود. اما هنگامی که مشکل پیدا کردن شماره های بزرگ فیبوناچی در برنامه نویسی رقابتی ظاهر می شود ، مردم از آن عبور می کنند. حالا چرا می تواند باشد؟

4 با استفاده از ماتریس

اول ، بیایید استراتژی را که در برنامه نویسی رقابتی برای یافتن شماره های بزرگ فیبوناچی استفاده می شود ، پوشش دهیم. ما می توانیم عود در معادله (1) را به عنوان یک سیستم معادلات بنویسیم:

سپس می توانیم این معادلات را به صورت ماتریس بیان کنیم:

ادامه این کار را به تمام راه به F (0) و F (1) ادامه خواهیم داد ، ما دریافت خواهیم کرد:

اکنون ، ترفند سریع اکتشافی از بخش 2 روی ماتریس ها کار می کند و همچنین روی Scalars کار می کند. بنابراین ، ما می توانیم به جای زمان O (n) ، نمایشگاه A^n را در زمان O (log n) تکمیل کنیم. و سپس O (1) زمان بالای آن برای دریافت f (n). برای اجرای این ایده برای شماره های فیبوناچی ، به اینجا مراجعه کنید.

حتی اگر از پیچیدگی برخوردار باشد ، این روش شامل گسترش سریع ماتریس ها همانند محلول بسته فرم بسته است ، اما شامل چند برابر بیشتر از فرم بسته است زیرا هر ضرب A با خودش به هشت ضرب نیاز دارد به جای اینکه فقط در هنگام افزایش^ن. پس چرا بیش از فرم بسته ترجیح داده می شود؟

5 ملاحظات عددی

فرم بسته در معادله (4) شامل ضرب یک عدد غیر منطقی ، بارها و بارها با خودش است. غیر منطقی بودن ، نمی توان به طور کامل در انواع شماره های نقطه شناور که رایانه هایی برای ذخیره شماره های واقعی استفاده می کنند ، بیان شود. فقط تقریبی (گسترش اعشاری برای همیشه ادامه می یابد و ما باید در جایی متوقف شویم). اهمیت این از دست دادن دقت در حالی که ما به یک قدرت بزرگ می رسیم رشد می کند. این امر باعث می شود که ϕ^n به میزان قابل توجهی خاموش شود. هرچه N بزرگتر شود ، خطا به دلیل از بین رفتن دقت بیشتر می شود. به نظر می رسد که وقتی N فراتر از 100 می رود ، این خطا به دلیل از دست دادن دقت به یک مسئله واقعی تبدیل می شود و ما شروع به دریافت نتیجه می کنیم که به طور قابل توجهی خاموش است.

با بیان ماتریس از معادله (5) از طرف دیگر ، تمام ورودی های موجود در ماتریس عدد صحیح هستند. بنابراین ، تمام ضرباتی که در نهایت انجام می دهیم هرگز از قسمت اعداد صحیح خارج نمی شوند. و بنابراین ما هرگز دقت خود را از دست نمی دهیم. بنابراین با وجود معادله (5) که بیش از هشت برابر معادله ضرب (4) نیاز دارد ، ما این قیمت را به خاطر دقت عددی پرداخت می کنیم و هنوز هم با الگوریتم O (log n) به پایان می رسد.

جدا از افزایش شماره های نقطه شناور (و به ویژه موارد غیر منطقی) به مأمورین بزرگ ، یکی دیگر از موارد بزرگ و بدون تجزیه و تحلیل عددی ، دو عدد بزرگ را کم می کند. در نگاه اول ، این ممکن است خطری در معادله (4) باشد. با این حال ، اصطلاح دوم ψ^n در واقع بسیار کوچک است از | ψ |و در واقع می توان نادیده گرفت. بنابراین این مسئله در این مورد خاص مسئله ای نیست.

گذشته از این ، ماتریس A در معادله (5) می تواند از نظر ویژه ای باشد و ضرب و شتم حتی کارآمدتر انجام شود (برای جزئیات بیشتر به "فرم ماتریس" مقاله ویکی پدیا مراجعه کنید). اما ، افسوس ، تجزیه Eigen دوباره شرایط ϕ و ψ را به ما می دهد و ما به مسئله بی ثباتی عددی باز خواهیم گشت. در حقیقت ، ما می توانیم فرم بسته را از معادله (4) با رویکرد تجزیه Eigen نیز بدست آوریم (به مقاله ویکی پدیا مراجعه کنید). در حقیقت اگر ماتریس A برای هر یک از عناصر آن یک شماره نقطه شناور منفرد داشته باشد ، در بیشتر موارد معنی ندارد که به جای ماتریس اصلی ، کارآزمایی Eigen را انجام ندهید و به سرعت انجام دهید (به این پست stackoverflow مراجعه کنید).

اگر داستان را دوست داشتید ، عضو ارجاع شوید :)