CSE / ডাটা স্ট্রাকচার

ফিবোনাচি নাম্বার (Fibonacci Number)

ম্যাথমেটিক্সে,

ফিবোনাচি হল কিছু পূর্ণসংখ্যার ক্রম যাদের ফিবোনাচি ক্রম বলে।

ম্যাথমেটেশিয়ান ফিবোনাচি খরগোশের বংশবৃদ্ধি নিয়ে ম্যাথমেটিক্যালি চিন্তা করেন। সেখান থেকেই ফিবোনাচি নাম্বারের উৎপত্তি।

ফিবোনাচির রেবিটসঃ

একবছরে কয়জোড়া খরগোশ জন্ম নিবে। এই সমস্যাটি নিম্ন লিখিত শর্তের উপর নির্ভর করে,

  • গণনা শুরু হবে একটি পুরুষ ও একটি স্ত্রী খরগোশ নিয়ে।
  • একমাস পর তারা সেক্সুয়েল মিলনে সক্ষম
  • তারপর প্রত্যেক একমাস পর পর তারা একটি পুরুষ খরগোশ এবং একটি স্ত্রী খরগোশ জন্ম দিবে।

খরগোশ গুলো মরবেনা।

fibonacci_diagraph
fibonacci_diagraph

উপরের ডায়াগ্রাফ দেখে আমরা সহজেই বুঝতে পারি হিসাব টা।

পুরুষ ও স্ত্রী খরগোশ প্রথম মাস পর সেক্সুয়েল মিলনে সক্ষম।

২য় মাস পর তারা ১ টি পুরুষ খরগোশ এবং একটি স্ত্রী খরগোশ জন্ম দেয়।

প্রত্যেক একমাস পর পর অরিজিনাল প্যারেন্ট বাচ্চা দিতে থাকে।

কিন্তু বাচ্চা খরগোশ গুলো ঠিক আগের নিয়ম অনুযায়ী দুই মাস পর বাচ্চা দেওয়া শুরু করে এবং এর পর মাসে মাসে বাচ্চা দিতে সক্ষম।

এক বছর পর প্রায় ২৩৩ জোড়া খরগোশের বাচ্চা পাওয়া যাবে।

ম্যাথমেটিক্সে,

ফিবোনাচি হল কিছু পূর্ণসংখ্যার ক্রম যাদের ফিবোনাচি ক্রম বলে।

এই ক্রমের বৈশিষ্ট্য হল, প্রত্যেকটি সংখ্যা তার পূর্বের দুই সংখ্যার যোগফল।

প্রথম দুইটি সংখ্যা হল ০ এবং ১

ফিবোনাচি ক্রমঃ

০, ১, ১, ২, ৩, ৫, ৮, ১৩, ………………

 

ম্যাথমেটিক্স রিকারেন্স রিলেশন অনুযায়ী,            fn = fn-1 + fn-2

fibonacci series
fibonacci series

উপরের চিত্র থেকে আমরা সহজেই বুঝতে পারি কিভাবে ফিবোনাচি ক্রম গঠিত হয়।

প্রথমে ০ + ১ গণনা করা হয়। সেখান থেকে পাওয়া যোগফলের সাথে পূর্ববতী সংখ্যা ১ এর সাথে যোগ করে যোগফল ২ পাওয়া হয়। এই ২ এর সাথে পূর্বের যোগফল ১ এর যোগের ফলে ৩ পাওয়া যায়। ঠিক এই ভাবেই ক্রমের হিসাব টি বাড়তে থাকে।

সি বা সি++ কোড রিকার্শন ছাড়া

উপরের কোড টি মূলত ফিবোনাচি ক্রম প্রিন্ট করে।

 

সি বা সি++ কোড রিকার্শন দিয়ে

রিকার্সন স্ট্যাক ব্যবহার করে কাজ করে। অনেক বড় ডাটা নিয়ে রিকার্সনে কাজ করতে গেলে স্ট্যাক অভারফ্লো হওয়ার সম্ভাবনা থাকে।

Leave a Reply

Your email address will not be published.

2 × 1 =