نحوه نوشتن یک برنامه جاوا برای دریافت سری فیبوناچی

Bikash Daga (Jain)

سری Fibonacci نوع خاصی از دنباله است که با 0 و 1 شروع می شود و هر شماره بعد از این دو نفر مجموع دو شماره قبلی است.

سری Fibonacci به این شکل پیش می رود: 0 ، 1 ، 1 ، 2 ، 3 ، 5 ، 8 ، 13 ، 21 ،… و غیره. این اولین بار در ریاضیات هند شرح داده شد.

منبع: مباحث مقیاس پذیر

سری Fibonacci در بسیاری از زمینه ها مانند امور مالی و فناوری استفاده می شود. همچنین می توانید آن را در بسیاری از فرآیندهای طبیعی مشاهده کنید.

اهمیت سریال فیبوناچی در طبیعت به زیبایی در نقل قول گای مورچی توضیح داده شده است

"دنباله فیبوناچی کلید درک چگونگی طراحی طبیعت است. و است. بخشی از همان موسیقی همه جا از حوزه هایی که باعث ایجاد هماهنگی در اتم ، مولکول ، کریستال ، پوسته ، خورشید و کهکشان می شوند و باعث می شود جهان آواز بخواند. "- گای مورچی ، هفت اسرار زندگی: کاوش در علم و فلسفه

آیا این حقایق را می دانید؟

• نسبت هر دو عدد متوالی در سری فیبوناچی تقریباً 1. 6 است. به عنوان مثال: 21 /13 = 1. 61 و 55 /34 = 1. 61
• 23 نوامبر روز فیبوناچی است ، زیرا تاریخ این روز شبیه سری فیبوناچی در قالب MM / DD است (11/23).

نحوه محاسبه سری فیبوناچی با استفاده از رویکرد از بالا به پایین

در این رویکرد از بالا به پایین ، ما مقدار شاخص مورد نیاز را به عنوان مجموع مقادیر در دو شاخص قبلی محاسبه می کنیم.

اگر دو مقدار قبلی در دسترس ما نباشد ، ما همان روند را نیز برای آنها تکرار می کنیم.

اگر مقادیر آنها نیز در دسترس ما نباشد ، ما همان روند را تکرار می کنیم تا این دو مقدار را دریافت نکنیم. این رویکردی است که تئوری محور است.

ما در اینجا از نوع درخت استفاده می کنیم - ما فقط به دنبال دو مقدار قبلی هستیم و اگر این مقادیر در دسترس ما نباشد ، روند را تکرار می کنیم تا زمانی که دو مقدار را دریافت نکنیم.

ما الگوریتم پیچیده را به قطعات کوچکتر می ریزیم که می توان ماژول ها نامید. و ما می توانیم این ماژول ها را بیشتر به قطعات کوچکتر تقسیم کنیم تا اینکه دیگر نتوانند تکه تکه شوند.

منبع: مباحث مقیاس پذیر

الگوریتم برای رویکرد از بالا به پایین

ابتدا برای دریافت شماره مربوطه در سری Fibonacci ، ورودی ‘n را می گیرید.

سپس ، شما مقدار شاخص مورد نیاز را به عنوان مجموع مقادیر در دو شاخص قبلی محاسبه می کنید (یعنی مقادیر اضافه شده در شاخص N-1 و شاخص N-2). اگر مقادیر برای دو شاخص قبلی پیدا نشود ، شما همین کار را برای یافتن مقادیر در آن فهرست انجام خواهید داد.

هر زمان که مقادیر دو شاخص قبلی متوالی را بدست آورید ، آنها را اضافه می کنید و نتیجه را به عنوان مقدار شاخص بعدی باز می گردانید.

سپس مقدار را در شاخص "N - 1" و "N - 2" اضافه می کنید و مقدار مورد نیاز را برمی گردانید.

مزایای رویکرد از بالا به پایین

• اشکال زدایی پروژه شما کارآمدتر می شود.
• اجرای کد آسان تر می شود.
• این باعث می شود کد برای حل و مدیریت آسان شود.
• فرآیند آزمایش به دلیل ماژول های جداگانه آسان تر می شود.

مضرات رویکرد از بالا به پایین

• وابستگی زیادی به ماژول های دیگر وجود دارد. تغییرات در یکی می تواند بر همه ماژول های دیگر تأثیر بگذارد.
• این یک رویکرد کندتر در مقایسه با رویکرد پایین به بالا در برنامه نویسی پویا به دلیل بازگشت است.

نحوه محاسبه سری فیبوناچی با استفاده از رویکرد از پایین به بالا

در این رویکرد از پایین به بالا ، ما یک آرایه ایجاد می کنیم و مقادیر دو شاخص اول را به ترتیب 0 و 1 پر می کنیم.

پس از آن ، ما مقدار تمام شاخص ها را با استفاده از این دو مقدار برای ذخیره آنها در یک آرایه محاسبه می کنیم.

ما می توانیم مقدار را از هر شاخص بدست آوریم تا شماره مربوطه را در سری Fibonacci بدست آوریم.

به عنوان مثال: اگر فیبنوم آرایه ای است که شماره های فیبوناچی را ذخیره می کند ، پس ما درج می کنیم:

سپس در داخل یک حلقه تکراری با متغیر اشاره گر من ، می نویسیم:

منبع: مباحث مقیاس پذیر

الگوریتم برای رویکرد پایین به بالا

ابتدا برای دریافت شماره مربوطه در سری Fibonacci ، ورودی را دریافت می کنید.

سپس باید مقادیر سری Fibonacci را ذخیره کنید ، بنابراین برای آن مجموعه ای از اندازه را اعلام می کنید.

در مرحله بعد ، مقدار را برای دو شاخص اول به ترتیب 0 و 1 وارد کنید.

از یک حلقه تکراری برای شاخص های سوم و دیگر باقیمانده استفاده کنید ، همانطور که در توضیحات بالا توضیح داده شده است.

سرانجام ، مقدار را در آخرین شاخص آرایه برگردانید.

مزایای رویکرد از پایین به بالا

• ایجاد موارد آزمایش ساده تر است.
• کد شما قابل استفاده مجدد است
• به دلیل محصور سازی داده ها و پنهان کردن داده ها ، افزونگی کمتری وجود دارد.

مضرات رویکرد از پایین به بالا

• گاهی اوقات فضای و زمان اضافی مصرف می کند.
• بعضی اوقات ، درک کار در مراحل اولیه دشوار است.

نحوه کدگذاری توالی فیبوناچی

روش های مختلفی برای نوشتن برنامه برای یافتن شماره های فیبوناچی در جاوا وجود دارد.

1. نحوه کدگذاری توالی فیبوناچی با استفاده از حلقه های تکراری ساده

در اینجا نحوه دریافت کد شماره شماره فیبوناچی در جاوا با استفاده از حلقه برای حلقه آورده شده است:

در اینجا نحوه دریافت کد شماره فیبوناچی نهم در جاوا با استفاده از حلقه مدتی آورده شده است:

پیچیدگی زمان:

پیچیدگی زمانی برای این رویکرد O(N) است، که پیچیدگی زمانی خطی است زیرا ما فقط یک بار از آرایه عبور کردیم.

پیچیدگی فضا:

پیچیدگی فضا برای این رویکرد O(N) است، که پیچیدگی فضای خطی است زیرا ما پاسخ‌های مسائل فرعی را در یک آرایه ذخیره می‌کنیم.

2. نحوه کدنویسی دنباله فیبوناچی با استفاده از بازگشت

اکنون الگوریتم سری فیبوناچی را با استفاده از بازگشت در جاوا مرور می کنیم.

در بازگشت، از یک تابع تعریف شده استفاده می کنیم (مثلاً در این کد فیب است) برای یافتن عدد فیبوناچی.

در تابع main() تابع fib() را برای عدد n در سری فیبوناچی فراخوانی می کنیم.

ما حالت پایه را برای این فراخوانی بازگشتی تعریف می کنیم - یعنی 0 و 1 را به ترتیب برای اعداد فیبوناچی 0 و 1 برمی گرداند.

تابع درون خودش را مانند fib(x) = fib(x-1) + fib(x-2) فراخوانی می کنیم تا زمانی که به حالت پایه برخورد کند و سپس مقادیر را از آنجا بدست می آوریم.

چگونه کد عدد فیبوناچی n را در جاوا با استفاده از بازگشت به دست آوریم

پیچیدگی زمان:

پیچیدگی زمانی برای این رویکرد O( 2 ^ N ) است که پیچیدگی زمانی نمایی است، که در آن n شاخص nامین عدد فیبوناچی است.

برای بدست آوردن هر مقدار باید دو مقدار قبلی را پیدا کنیم. برای آن ما تابع را دو بار برای هر مقدار فراخوانی می کنیم و درخت می تواند حداکثر n سطح داشته باشد.

این حدود 2 ^ n گره در درخت ایجاد می کند.

پیچیدگی فضا:

پیچیدگی فضا برای رویکرد با استفاده از بازگشت O(2 ^ N) است که پیچیدگی فضای نمایی است که در آن n شاخص nامین عدد فیبوناچی است.

از آنجایی که باید مقادیر هر گره را ذخیره کنیم و 2 گره ^ N داریم، کل فضایی که برای آن نیاز داریم 2 ^ N است.

3. نحوه کدنویسی دنباله فیبوناچی با استفاده از بازگشت با حافظه

به خاطر سپردن به این معنی است که ما به ذخیره کردن تمام راه حل های مربوط به مسائل فرعی ادامه می دهیم تا بتوانیم به طور مستقیم مقدار مورد نیاز را در آینده در برنامه بازیابی و استفاده کنیم. این می تواند در زمان و مکان برای ما صرفه جویی کند.

الگوریتم سری فیبوناچی با استفاده از بازگشت در جاوا

در اینجا یک تابع تعریف می کنیم (از fib() استفاده می کنیم و از آن برای یافتن عدد فیبوناچی مورد نظر خود استفاده می کنیم.

ما یک آرایه جهانی را به اندازه کافی طولانی اعلام می کنیم تا همه اعداد فیبوناچی پس از محاسبه ذخیره شوند.

در تابع main() تابع fib() را برای عدد n فراخوانی می کنیم. سپس موارد پایه را برای فراخوانی بازگشتی تنظیم می کنیم و برای شاخص 0 و 1 به ترتیب 0 و 1 برمی گردانیم.

We call fib(x) = fib( x-1 ) + fib( x-2 ) for all x >2 . برای هر مقدار محاسبه شده آن را در آرایه جهانی ذخیره می کنیم.

مقدار هر شماره فیبوناچی در شاخص مربوط به شاخص جهانی ذخیره می شود. سپس می توانیم آنها را برای اهداف بعدی بازیابی و استفاده کنیم. این به شدت پیچیدگی زمان را بهبود می بخشد.

چگونه می توان کد شماره شماره فیبوناچی را در جاوا با استفاده از بازگشت با Memoization دریافت کرد

پیچیدگی زمان:

پیچیدگی زمانی برای این روش O (n) است که پیچیدگی زمان خطی است ، جایی که n شاخص شماره فیبوناچی نهم است.

ما باید دو مقدار قبلی را برای به دست آوردن هر مقدار پیدا کنیم - اما در اینجا ما قبلاً آنها را در یک آرایه ذخیره کرده ایم ، بنابراین باید فقط یک بار برای همه عناصر این عملکرد را فراخوانی کنیم.

پیچیدگی فضا:

پیچیدگی فضایی برای این روش O (n) است که پیچیدگی فضایی خطی است ، جایی که n شاخص شماره فیبوناچی نهم است.

ما فقط باید مقادیر هر گره را ذخیره کنیم و فقط گره های N داریم.

نتیجه

در این مقاله ، ما یاد گرفتیم که چگونه سری Fibonacci را در جاوا به چهار روش مختلف پیدا کنیم ، دو مورد برای رویکرد از پایین به بالا و رویکرد بالا.

ما همچنین آموخته ایم که بازگشت با یادبود بیشترین زمان و فضا برای به دست آوردن شماره های فیبوناچی است.

در این مقاله ، ما در مورد پیچیدگی فضا و زمان هر رویکرد به همراه الگوریتم ها ، مزایا و معایب آنها بحث کرده ایم.