0
1

আমি নতুন । ডায়নামিক প্রোগ্রামিং কি জিনিস ? এটা দ্বারা কি করা হয় ?? ডায়নামিক প্রোগ্রামিং শেখার জন্য ভাল resource দিলে খুব উপকৃত হতাম ।

asked 31 Mar '16, 06:04

AhadKhan's gravatar image

AhadKhan
95223


ডাইনামিক প্রোগ্রামিং কোনো নির্দিষ্ট অ্যালগোরিদম নয় বরং একটি প্রবলেম সলভিং টেকনিক যা ব্যবহার করে বিভিন্ন সমস্যাকে খুবই কম সময়ের মধ্যে সলভ করা যায়। রিয়েল লাইফ অনেক প্রবলেম কম সময়ের মধ্যে একমাত্র ডাইনামিক প্রোগ্রামিং ব্যবহার করেই করা সম্ভব । একটি উদাহরন দেই। ফিবোনাচ্চি সিরিজ নিশ্চয় মনে আছে।

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

লক্ষ্য করলে দেখা যায়, ১ম দুটি সংখ্যা ছাড়া প্রতিটি সংখ্যা হলো আগের দুটি সংখ্যার যোগফল। আমরা একটি ফাংশন কল্পনা করি F(n) যা n তম ফিবোনাচ্চি সংখ্যা রিটার্ন করে,অর্থাত F(n)=n তম ফিবোনাচ্চি সংখ্যা। তাহলে:

F(0)=0
F(1)=1
F(2)=F(1)+F(0)=1
F(3)=F(2)+F(1)=2
F(4)=F(3)+F(2)=3

তাহলে আমরা জেনারেলভাবে বলতেই পারি:

F(0)=0
F(1)=1
F(n)=F(n-1)+F(n-2)

এখানে F(0) এবং F(1) হলো আমাদের রিকার্সিভ ফাংশনের জন্য যে বেসকেস দরকার সেটা। আমরা খুব সহজে C++ এ কোড লিখে ফিবোনাচ্চি সংখ্যা বের করতে পারি:

int F( int n ) {
if( n == 0 ) return 0;
if( n == 1 ) return 1;
return F( n-1 ) + F( n-2 );
}

এখন ধরো তুমি F(6) কে কল করলে। সে আবার কল করবে F(5) আর F(4) কে,এরা আরও কিছু ফাংশনকে কল করবে।এখন F(6) কিন্তু F(5) কে কল করার পর আবার F(4) কে কল করছে। কিন্তু আমরাতো F(4) এর মান হিসাব করেই ফেলেছি,কি দরকার আবার হিসাব করার? আগের মানটাই কি আমরা আবার ব্যবহার করতে পারিনা?

এখানেই আমরা একটা ছোট্ট ট্রিকস খাটাবো। কোনো একটি ফাংশনের হিসাব শেষ হয়ে গেলে আমরা একটি টেবিলে মানটি সেভ করে রাখবো। পরবর্তিতে একই ফাংশনকে আবার কল করলে আমরা পুরো হিসাব আবার না করে আগের মানটি রিটার্ন করে দিবো।

int dp[20];
//শুরুতে ডিপি অ্যারের সবগুলো ইনডেক্সে -১ বসিয়ে নাও
//যেমন for(int i=0;i<20;i++)dp[i]=-1; (এই কাজটা মেইন ফাংশনে করবে)
//কোনো ঘরে -১ থাকা মানে হচ্ছে ঘরটা খালি
int F( int n ) {
if( n == 0 ) return 0;
if( n == 1 ) return 1;
if( dp[n]!=-1 ) return dp[n];
else
{
dp[n] = F( n-1 ) + F( n-2 );
return dp[n];
}
}

যে সহজ কাজটা করে আমরা সময় বাচিয়ে ফেললাম সেটাকেই কম্পিউটার প্রোগ্রামার কঠিন ভাষায় বলে ডাইনামিক প্রোগ্রামিং বা ডিপি। আমরা যদি মানগুলো অ্যারেতে সেভ করে না রাখতাম তাহলে একি ফাংশন বারবার কল হয়ে প্রচুর সময় নষ্ট করতো,তুমি নিজে F(20) এর জন্য একবার সেভ করে আরেকবার না করে পরীক্ষা করে দেখতে পারো পার্থক্যটা কতখানি।

বিস্তারিত জানতে ও DP এর ভাল resource এর জন্য ভিসিট করঃ ডাইনামিক প্রোগ্রামিং এ হাতেখড়ি

permanent link

answered 31 Mar '16, 09:11

Kaiser%20Ahmed's gravatar image

Kaiser Ahmed
3.2k522

Thanks a lot brother!

(31 Mar '16, 09:17) AhadKhan
1

You welcome :)

(31 Mar '16, 10:15) Kaiser Ahmed
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Question tags:

×402
×214
×90

question asked: 31 Mar '16, 06:04

question was seen: 2,486 times

last updated: 31 Mar '16, 10:15