অনুমান করুন উচ্চতর বা নিম্ন XNUMX


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক গুগল মাইক্রোসফট
বিন্যাস ডায়নামিক প্রোগ্রামিং

সমস্যা বিবৃতি

"অনুমানের নম্বর উচ্চতর বা নিম্ন দ্বিতীয়" এর বিবরণে বলা হয়েছে যে আমরা একটি গেম খেলতে যাচ্ছি যা অনুমান গেম বলে। গেমটি বলে যে আমি 1 থেকে এন পর্যন্ত একটি সংখ্যা বাছাই করি। যখনই আপনি যে নম্বরটি আমি বেছে নিইনি অনুমান করি, আমি আপনাকে বলতে চাই যে আপনি একটি নম্বর উচ্চতর বা নিম্ন চয়ন করেছেন।

এবং গুরুত্বপূর্ণ এবং আকর্ষণীয় অংশটি হ'ল আপনি যদি ভুল নম্বরটি বেছে নিয়ে থাকেন তবে x বলে দিন, আপনি পরিমাণের একক ইউনিট প্রদান করবেন। আপনি সঠিক সংখ্যাটি অনুমান করার সময় আপনার গেমটি জিতবে বলে মনে করা হচ্ছে, অর্থাৎ এটিই আমি বেছে নিয়েছি।

উদাহরণ

n = 10, আমি 6 বাছাই করি।

প্রথমে চয়ন করুন: আপনি অনুমান 2, এটি এর চেয়েও বড়, তার থেকেও উপরে যান। আপনি $ 2 দিতে হবে।

দ্বিতীয় চয়ন: আপনার ধারণা 4, এটি এর চেয়েও বড়, তার থেকেও উপরে যান go আপনি $ 4 দিতে হবে।

তৃতীয়টি চয়ন করুন: আপনার অনুমান 5, এটি এর চেয়েও বড়, তার চেয়েও উপরে যান। আপনি $ 5 দিতে হবে।

গেমটি এখন শেষ হয়েছে কারণ আপনি সঠিক নম্বরটি 6 বাছাই করেছেন।

আপনি $ 2 + $ 4 + $ 5 = $ 11 প্রদান শেষ করবেন।

মনে করুন, যদি আপনাকে এমন নম্বর দেওয়া হয় যা এন ≥ 1, আপনার কত পরিমাণ অর্থের পরিমাণ থাকা উচিত তা নির্ধারণ করুন যাতে আপনি নিশ্চিত করতে পারেন যে এই পর্যাপ্ত পরিমাণের সাহায্যে আপনি এই গেমটি জিততে চলেছেন।

অনুমান করুন উচ্চতর বা নিম্ন XNUMX

অনুমান নম্বর উচ্চতর বা দ্বিতীয় দ্বিতীয় সমস্যার জন্য অ্যালগরিদম

1. Declare a 2-d array of size n+1.
2. Set output to the maximum value of an integer.
3. Set val to start + (end – start) / 2.
4. While val is less than or equal to end,
  1. Recursively call the function and find out the maximum between the values and Set table [start][end] to x + maximum of the number below the x value and number greater than the x value.
  2. Find out the minimum between the output and table[start][end] and update it into the output.
  3. Increase the value of x by 1.
4. Return table [start][end].

ব্যাখ্যা

আমরা একটি নম্বর দিয়েছি n যাতে আমরা আমাদের জয়ের আশ্বাস দিতে পারি এমন পরিমাণ অর্থের সন্ধান করতে পারি, এর জন্য আমরা একটি সংখ্যা ধরে নিতে পারি এবং সেই সংখ্যার নীচে এবং সেই সংখ্যার উপরে কাজ করতে পারি above এই কোড যাচ্ছে পুনরাবৃত্তি এর ফাংশন কল।

সমস্যাটি আপনার কাছে প্রত্যাশা করে সর্বাধিক কমান জয়ের জন্য আপনাকে অর্থ প্রদান করতে হবে। অবশ্যই আলাদা অনুমানের ক্ষেত্রে জয়ের জন্য আলাদা আলাদা ব্যয় প্রয়োজন তবে আমাদের লক্ষ্যটি 1… n এর মধ্যে সংখ্যাটি অনুমান করার জন্য প্রয়োজনীয় সর্বনিম্ন পরিমাণ গণনা করা,

ফলাফল = ম্যাথ.মিন (ফলাফল, পরিমাণ (i)) [প্রদত্ত সর্বনিম্ন ইনপুট প্রদান করে]

যেখানে পরিমাণ (i) সংখ্যাটি অনুমান করার জন্য সবচেয়ে খারাপ সম্ভাব্য পরিমাণ।

এখন, যখন আপনি 3 ধরে নিচ্ছেন তখন এই নিকৃষ্টতম পরিস্থিতিটি কী।

আপনি 1 বাছাই করেছেন, সেরা ক্ষেত্রে 1টি আপনার অনুমানের সংখ্যা হতে পারে, অতএব পরিমাণ (i) = 0, কিন্তু আমরা সে সম্পর্কে উদ্বিগ্ন নই, আমরা সবচেয়ে খারাপ ক্ষেত্রে উদ্বিগ্ন, i, e 1 বাছাই করা নম্বর নয় সুতরাং 1 টি যখন নেওয়া হয় তখন ব্যয় হয় = 1+ থেকে (2,3)।

আপনি ২ টি বাছাই করেছেন, সেরা ক্ষেত্রে ২ টি উত্তর এবং ব্যয়টি 2 হয় তবে সবচেয়ে খারাপ ক্ষেত্রে 2 বা হয় 0 টি উত্তর হয় এবং একটি সংখ্যা অনুমান করার পরে আপনি সর্বদা জানতে পারবেন যে বাছাই করা সংখ্যাটি বেশি কিনা বা সংখ্যার চেয়ে কম, অতএব আমরা জানতে পারি 3 হ'ল উত্তর বা 1 উত্তর is অতএব সবচেয়ে খারাপ ক্ষেত্রে ব্যয় 1।

সবচেয়ে খারাপ ক্ষেত্রে 3 বাছাই করা দামটি (3) থেকে 1,2+ খরচ হবে। চূড়ান্ত ব্যয় হবে এই সমস্ত খারাপ-ব্যয়ের সর্বনিম্ন ব্যয়। উত্তর পেতে এবং এটি মুখস্ত করার জন্য আমাদের এটিকে পুনরাবৃত্তভাবে করতে হবে।

বাস্তবায়ন

অনুমান নম্বর উচ্চতর বা দ্বিতীয় দ্বিতীয় সমস্যাটির জন্য সি ++ প্রোগ্রাম

#include<iostream>
#include<vector>

using namespace std;

int helper(int low,int high,vector<vector<int>> &dp)
{
    if(low>=high)
        return 0;
    if(dp[low][high]!=INT_MAX)
        return dp[low][high];
    for(int j=low; j<=high; j++)
    {
        dp[low][high]=min(dp[low][high],max(j+helper(low,j-1,dp),j+helper(j+1,high,dp)));
    }
    return dp[low][high];

}
int getMoneyAmount(int n)
{
    vector<vector<int>> dp(n+1,vector<int>(n+1,INT_MAX));
    return helper(1,n,dp);
}

int main()
{
    cout<<getMoneyAmount(10);
}
16

অনুমান নম্বর উচ্চতর বা দ্বিতীয় দ্বিতীয় সমস্যাটির জন্য জাভা প্রোগ্রাম

class guessNumber
{
    public static int getNumber(int n)
    {
        return guessNumberRec(new int[n+1][n+1], 1, n);
    }
    public static int guessNumberRec(int[][] arr, int left, int right)
    {
        if (left >= right)
        	return 0;
        if (arr[left][right] != 0)
        	return arr[left][right];

        arr[left][right] = Integer.MAX_VALUE;
        for (int a = left; a <= right; a++)
        {
            arr[left][right] = Math.min(arr[left][right], a + Math.max(guessNumberRec(arr, left, a - 1), guessNumberRec(arr, a + 1, right)));
        }
        return arr[left][right];
    }
    public static void main(String [] args)
    {
        System.out.println(getNumber(10));
    }
}
16

জটিলতা বিশ্লেষণ

সময় জটিলতা

চালু2) কোথায় "এন" সংখ্যার ব্যাপ্তিটি বেছে নেওয়া যেতে পারে।

স্পেস জটিলতা ity

ও (এন লগ এন) কোথায় "এন" সংখ্যার ব্যাপ্তিটি বেছে নেওয়া যেতে পারে।