আমাদের কথা খুঁজে নিন

   

কয়েন চেঞ্জ



ধরি, আমাদের কাছে ২ টাকা এবং ৪ টাকার কয়েন আছে আর আমরা জানতে চাই, ঠিক কতভাবে ১ থেকে ৮টাকা বানানো যায়, যেমন ৪ টাকা বানানো যায় ২ ভাবেঃ ২টাকার ২ টা কয়েন বা ৪ টাকার টা কয়েন দিয়ে। আর আরেকটা কথা, যে কোন কয়েন যে কোন সংখ্যকবার নেয়া যাবে। ধরি, একটা এরে নিলাম nway[], এতে থাকবে কোন টাকা কতভাবে বানানো যায়, মানে nway[1]=কতভাবে ১ টাকা বানানো যায়, nway[2] মানে কতভাবে ২ টাকা বানানো যায়… nway[0] = 1,কারন আমরা ০ টাকা বানাতে পারি ১ ভাবে(কোন টাকা না নিয়ে) এখন আমার nway array টা দেখতে এ রকমঃ ১ ০ ০ ০ ০ ০ ০ ০ ০ ০ ১ ২ ৩ ৪ ৫ ৬ ৭ ৮ এবার আসল কাজ শুরু করা যাক। প্রথমে ২ টাকার কয়েনটা নিই, ২ টাকার কয়েন দিয়ে অবশ্যই ১ টাকা বানানো যায় না,তাই টেস্ট করা শুরু করি ২ টাকা হতে। এখন ২ টাকার কয়েন দিয়ে কি ২ টাকা বানানো যায়?একটা জিনিস খুব ভালভাবে খেয়াল করতে হবেঃ ধরি,আমার কাছে ২ টাকা আছে, এটা দিয়ে ৫ টাকা বানাতে পারব, যদি আমার কাছে (৫-২) = ৩ টাকা থাকে।

তাহলে ৩ টাকার সাথে ২ টাকা যোগ করে ৫ টাকা বানাতে পারব। তেমনিভাবে, ১টা ২ টাকার কয়েন দিয়ে ২ টাকা বানানো যাবে যদি আমার কাছে (২-২)=০ টাকা থাকে, বা শুন্য টাকা বানাতে পারি। এখন কতভাবে ০ টাকা বানাতে পারি তা আছে nway[0] তে। এখন, nway[0]=1>০,মানে আমার কাছে ০ টাকা আছে বা আমি ০ টাকা বানাতে পারি, তাই আমি ২ টাকার কয়েন দিয়ে ০+২= ২ টাকা বানাতে পারি। কিন্তু কতভাবে বানাতে পারি? যতভাবে ০ টাকা বানাতে পারি +nway[2 ] এর বর্তমান মান যত।

nway[2] এর বর্তমান মান ০, আর ০ টাকা বানাতে পারি ১ ভাবে, তাই ২ টাকা বানাতে পারি ০+১ = ১ ভাবে। এটা সি তে লিখব এভাবেঃ nway[2] =nway[0]+ nway[2], বা আরো সংক্ষেপে,nway[2]+=nway[0]. এখন, ২ টাকার কয়েন দিয়ে কি ৩ টাকা বানাতে পারি? এজন্য আগে দেখি ৩-২ = ১ টাকা বানানো যায় কিনা। nway[1]=0.তার মানে আমি ১ টাকা বানাতে পারি না, তাই ১ টাকার হেল্প নিয়ে ৩ টাকাও বানানো সম্ভব না। একইভাবে nway[4] = nway[4]+nway[4-2] মানে nway[4]+nway[2],nway[5] = nway[5]+nway[3] … এভাবে ৮ টাকা পর্যন্ত চেক করার পরে আমার nway array টা এরকমঃ ১ ০ ১ ০ ১ ০ ১ ০ ১ ০ ১ ২ ৩ ৪ ৫ ৬ ৭ ৮ এবার ৪ টাকার কয়েন নিয়ে কাজ করা যাকঃ ৪ টাকার কয়েন দিয়ে ১,২ বা ৩ টাকা বানানো সনভব না,কারণ এরা সবাই ৪ এর ছোট। ৪ টাকার কয়েন দিয়ে ৪ টাকা বানানো যায়, কিন্তু কতভাবে বানানো যায়? আগের মতই, যতভাবে ৪-৪=০ টাকা বানাতে পারি +nway[4 ] এর বর্তমান মান।

nway[4] এর বর্তমান মান 1, আর ০ টাকা বানাতে পারি ১ ভাবে, তাই 4 টাকা বানাতে পারি 1+১ = 2 ভাবে। এভাবে ৮ টাকা পর্যন্ত চেক করার পরে আমার nway array টা এরকমঃ ১ ০ ১ ০ ২ ০ ২ ০ ৩ ০ ১ ২ ৩ ৪ ৫ ৬ ৭ ৮ কোড : int nways[9];/* ৮ টাকা পর্সন্ত চেক করতে হবে,০ হতে ৮= ৯ টা মান*/ int main(){ int coins[5]={2,4};/*আমার কাছে যে সব কয়েন আছে */ int cent,total; nways[0]=1;/*০ টাকা বানানোর উপায় ১ টা*/ for(int i=0;i

অনলাইনে ছড়িয়ে ছিটিয়ে থাকা কথা গুলোকেই সহজে জানবার সুবিধার জন্য একত্রিত করে আমাদের কথা । এখানে সংগৃহিত কথা গুলোর সত্ব (copyright) সম্পূর্ণভাবে সোর্স সাইটের লেখকের এবং আমাদের কথাতে প্রতিটা কথাতেই সোর্স সাইটের রেফারেন্স লিংক উধৃত আছে ।