গত পর্বে একটা
সমস্যার সমাধান করতে বলেছিলাম। সমস্যাটিতে বলা হয়েছিল একটা প্রোগ্রাম লিখতে হবে রিকার্শন ইউস করে যেটা একটা স্ট্রিং কে রিভার্স করে
প্রিন্ট করবে। আমি কোড দিয়ে দিচ্ছি তবে ভুলেও কপি পেস্ট করতে যেও না।
#include<stdio.h>
void reverse()
{
char ch;
scanf("%c",&ch);
if(ch!='\n')
reverse ();
printf("%c",ch);
}
int main()
{
reverse ();
return 0;
}
সমাধানটিতে কি করেছি দেখ- একটা করে
ক্যারেক্টার ইনপুট নিচ্ছি আর চেক করছি এটা নিউলাইন কিনা। যদি না হয় তাহলে রিকার্সিভ
ফাংশনকে কল করছি। যখন নিউলাইন পাচ্ছি তখন আর রিকার্সিভ ফাংশন কল হবে না এবং
প্রিন্ট করবে সেই ক্যারেক্টারটা(নিউলাইন)। এই ফাংশনের কাজ শেষ এবং রিটার্ন করবে আগের ফাংশন এ। রিটার্ন নিয়ে গতপর্বে
আলোচনা করেছি। আগের ফাংশন এ যখন রিটার্ন করবে তখন প্রিন্ট করবে তার আগের ক্যারেক্টারটা। সেটা আবার রিটার্ন করবে তার আগের
ফাংশন এ। প্রিন্ট করবে তার আগের ক্যারেক্টারটা। এভাবে যেতে যেতে শেষে রিটার্ন করবে
মূল ফাংশন এ এবং প্রিন্ট করবে প্রথম ক্যারেক্টার। সহজ না!
আর একটা অতি জনপ্রিয় একটা সমস্যা
আছে।
ইটালিয়ান গণিতবিদ Leonardo Pisano Bigolloযাকে আমরা ফিবোনাচ্চি নামে চিনি
খরগোশের বংশবৃদ্ধি পর্যবেক্ষণ করতে গিয়ে একটা নাম্বার সিরিজ আবিষ্কার করে বসলেন।
সিরিজটি এরকম:
১, ১, ২, ৩, ৫, ৮, ১৩, ২১………..
লক্ষ্য করে দেখ প্রথম দুটি সংখ্যা
ছাড়া প্রতিটি সংখ্যা হচ্ছে তার ঠিক আগের দুটি সংখ্যার যোগফল। এই সিরিজটি ফিবোনাচ্চি
সিরিজ নামে পরিচিত। আমরা একটি ফাংশন f(n) কল্পনা করতে পারি যা n তম ফিবোনাচ্চি সংখ্যা
রিটার্ন করে অর্থাৎ f(n)=n তম ফিবোনাচ্চি সংখ্যা।
প্রথম দুটি সংখ্যার ক্ষেত্রে,
f(1)=1;
f(2)=1;
এবং পরের গুলোর ক্ষেত্রে,
f(3)=f(2)+f(1)=2;
f(4)=f(3)+f(2)=3;
.
.
.
f(n)=f(n-1)+f(n-2);
এখানে f(1) আর f(2) এ দুটি হল রিকার্সিভ
ফাংশনের জন্য যে বেসকেস দরকার সেটা। তাহলে সহজেই আমরা n তম ফিবোনাচ্চি সংখ্যা বের
করার জন্য একটা কোড লিখে ফেলতে পারি।
#include<stdio.h>
int f(int n)
{
if(n==1||n==2)
return1;
return f(n-1)+f(n-2);
}
int main()
{
int n,fibonacci;
scanf("%d",&n);
fibonacci=f(n);
printf("%d",fibonacci);
return 0;
}
ওপরের সল্যুশন এ আমরা কি করেছি দেখ-
আমরা একটা সংখ্যা n ইনপুট দিচ্ছি আর কল করছি f(n), মানে আমরা n তম ফিবোনাচ্চিসংখ্যা চাচ্ছি। এখানে একটা বিষয়
আমাদের মনে রাখতে হবে যে আমরা ইনপুট দিচ্ছি n এবং ফাংশনটি আসলে রিটার্ন করছে n তম ফিবোনাচ্চি
সংখ্যা। এখন আমরা চেক করছি কেউ কি ১ম বা ২য় ফিবোনাচ্চি সংখ্যা চাচ্ছে? যদি চায়
তবে আমরা 1 রিটার্ন করব কারন ১ম ও ২য় ফিবোনাচ্চি সংখ্যা তো 1. আর যদি না চায় তবে
বলব যে না আসলে তোমার ফিবোনাচ্চি সংখ্যা আমরা জানি না, সেটা জানে তোমার আগের
দুজন।
মানে রিটার্ন করে দেব f(n-1)+f(n-2); এখানে দেখ রিকার্সিভ ফাংশনটি এবার আমাকে বলছে আমার ফিবোনাচ্চি সংখ্যা
জানো না তো আমার আগের দুজনের ফিবোনাচ্চি সংখ্যাগুলো বল। আমি আবারও বলব যে আমি
সেটাও জানি না সেটা জানে তাদের আগের চারজন। এভাবে যেতে যেতে শেষ পর্যন্ত সে আমার কাছে জানতে চাইবে তাহলে 3য় ফিবোনাচ্চি সংখ্যাটা
কত, আমি বলব তা তো জানি না কিন্তু হ্যাঁ আমি প্রথম দুটি ফিবোনাচ্চি সংখ্যা জানি।
তো সে ওই দুটো যোগ করে পাবে 3য় ফিবোনাচ্চি সংখ্যা। এবার 3য় সংখ্যা আর 2য় সংখ্যা
যোগ করে পাবে 4 নাম্বার ফিবোনাচ্চি সংখ্যা এবং এভাবে শেষ পর্যন্ত n তম পেয়ে যাবে
এবং সেটা রিটার্ন করে দেবে।
রিকার্শন ট্রি তে একটা বিষয় লক্ষণীয়
যে আমরা কোন একটা ফিবোনাচ্চি সংখ্যা নির্ধারণ করছি তার আগের দুটো ফিবোনাচ্চি সংখ্যা
দিয়ে, মানে তার চাইল্ড দিয়ে। আগে চাইল্ড দুটো বিবেচনা করছি তারপর রুট। তারমানে
পোস্টঅর্ডার! আমরা ট্রি টিকে পোস্টঅর্ডারে ভিসিট করে ফেলেছি! কি মজা!!
এখন তোমাদের যেটা করতে হবে সেটা হল –
একটা ট্রি দেয়া থাকবে যেটাকে প্রি, পোস্ট, ইন অর্ডার এ প্রিন্ট করতে হবে।
সমস্যাটির সমাধান করতে হবে রিকার্শন ইউস করে।
ওপরের ট্রি এরঃ
Inorder: 1 3 2 5 2 4 1 3 2
Preorder: 5 3 1 2 4 2 3 1 2
আজ এ পর্যন্তই।
হ্যাপি কোডিং !!! :)
কোন মন্তব্য নেই:
একটি মন্তব্য পোস্ট করুন