Hex-a-Bonacci ( LOJ – 1006 ) Hint

যদি তুমি এই পোস্টটি পড়ে থাকো। তাহলে হয়তোবা মনে মনে ভাবসো। কি এক আজব প্রব্লেমরে বাবা। এক হইল recursive প্রব্লেম তার উপর আরো optimize করতে হবে। তবে হ্যা এটাই একটা ভালো practise ডাইনামিক প্রোগ্রামিং এর হাতে খড়ির জন্যে।

Oops, Hint তো বলেই দিলাম। তাহলে প্রব্লেমটার স্ট্যাটমেন্ট নিয়ে আলোচনা করা যাক।

তোমাকে একটা কোড দেওয়া হলো যেটা কিনা নিখুত ভাবে করা নেই। তার মানে এই না যে কোডটা সঠিক উত্তর প্রিন্ট করে না। মুল ব্যাপার হচ্ছে, কোডটি সঠিক আউটপুট দেয় কিন্তু সর্বোচ্চ Test Case অথবা যে কোন Test case প্রিন্ট করতে TIme Limit অতিক্রম হয়ে যায়।

return( fn(n1) + fn(n2) + fn(n3) + fn(n4) + fn(n5) + fn(n6) );

মনে প্রশ্ন জাগতে পারে কেন Time Limit Exist হয়। প্রথম ব্যাপার হল এটা জানার আগে recursion এ হাতে খড়ি থাকতে হবে। তারপর দেখো ( উপরের কোডটি ) ফাংশন টি প্রত্যেকবার নিজেকে ৬ বার কল করে। এরপর ওই ছয় জন আরও ছয় জনকে কল করে। তারমানে বিশাল ব্যাপার সেপার। এর মানে Recursion এতো কঠিন তা না। মূলত অনেক বার কল করার কারনেই Time Limit Exist হয়।

তো সমাধান ঃ

তুমি যদি হাতে কলমে একটু Simulate করে দেখো। দেখবা ধরো Fn ( 6 ) এটার মান Recusively বারবার বের হচ্ছে আমরা যদি প্রথম বারেই এই মানকে কথাও Save করে রাখি তাহলে বারবার করা লাগসে না একবার করে check করলেই হবে। এই কাজটাই ডাইনামিক প্রোগ্রামিং করে। কিভাবে ডাইনামিক প্রোগ্রামিং মান Save করে রাখে সেটা জানলে আশা করি তমার মাথায় উত্তর ছলে আসবে।

অন্যের কোড দেখার আগে হিন্ট দেখো এবং চিন্তা করো। হাতে কলমে করার চেষ্টা করো।

ধন্যবাদ লেখাটি পড়ার জন্য। এরপর চিন্তিত হলে কমেন্টে জানাতে পারো।

Leave a reply:

Your email address will not be published.

Site Footer