সমস্যা বিবৃতি
সেখানে এন খেলোয়াড় আছে যারা একটি টুর্নামেন্ট খেলছে। বিজয়ী সর্বোচ্চ কতগুলি গেম খেলতে পারে তা আমাদের খুঁজে বের করতে হবে। এই টুর্নামেন্টে, দুজন খেলোয়াড়কে একে অপরের বিরুদ্ধে খেলার অনুমতি দেওয়া হয় শুধুমাত্র যদি তাদের খেলার মধ্যে পার্থক্য একের বেশি না হয়
উদাহরণ
যদি ৩ জন খেলোয়াড় থাকে তাহলে নিচের মত করে বিজয়ী নির্ধারণ করতে ২টি গেমের প্রয়োজন হয় −
খেলা – ১:প্লেয়ার ১ বনাম প্লেয়ার ২
খেলা - 2:খেলোয়াড় 2 বনাম গেম - 1
থেকে বিজয়ী৷অ্যালগরিদম
- আমরা প্রথমে ন্যূনতম সংখ্যক খেলোয়াড়ের কম্পিউট করে এই সমস্যার সমাধান করতে পারি যাতে বিজয়ী x গেম খেলতে পারে। একবার এটি গণনা করা হলে প্রকৃত সমস্যাটি এর বিপরীত। এখন অনুমান করুন যে dp[i] ন্যূনতম সংখ্যক খেলোয়াড়ের প্রয়োজন যাতে বিজয়ী i গেম খেলতে পারে
- আমরা dp মানগুলির মধ্যে একটি পুনরাবৃত্ত সম্পর্ক লিখতে পারি, dp[i + 1] =dp[i] + dp[i – 1] কারণ রানার আপ যদি (i – 1) গেম খেলে এবং বিজয়ী i গেম খেলে এবং যে সমস্ত খেলোয়াড়ের বিরুদ্ধে তারা ম্যাচ খেলেছে তারা বিচ্ছিন্ন, বিজয়ীর দ্বারা খেলা মোট গেম সেই দুই সেট খেলোয়াড়ের যোগ হবে।
- উপরে পুনরাবৃত্ত সম্পর্ককে dp[i] =dp[i – 1] + dp[i – 2] হিসাবে লেখা যেতে পারে যা ফিবোনাচি সিরিজের সম্পর্কের মতো, তাই আমাদের চূড়ান্ত উত্তর হবে সর্বাধিক ফিবোনাচি সংখ্যার সূচক যা ইনপুটে দেওয়া খেলোয়াড়ের সংখ্যার চেয়ে কম বা সমান
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int getMaxGamesToDecideWinner(int n) {
int dp[n];
dp[0] = 1;
dp[1] = 2;
int idx = 2;
do {
dp[idx] = dp[idx - 1] + dp[idx - 2];
} while(dp[idx++] <= n);
return (idx - 2);
}
int main() {
int players = 3;
cout << "Maximum games required to decide winner = " << getMaxGamesToDecideWinner(players) << endl;
return 0;
} আউটপুট
যখন আপনি উপরের প্রোগ্রামটি কম্পাইল এবং এক্সিকিউট করবেন। এটি নিম্নলিখিত আউটপুট −
তৈরি করেMaximum games required to decide winner = 2
