اندازہ لگائیں کہ اعلٰی اور لوئر II


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایمیزون گوگل مائیکروسافٹ
لڑی متحرک پروگرامنگ

مسئلہ یہ بیان

"گیس نمبر ہائیر یا لوئر II" بیان کرتا ہے کہ ہم ایک ایسا کھیل کھیل رہے ہیں جسے گیس گیم کہتے ہیں۔ کھیل کا کہنا ہے کہ میں 1 سے n تک ایک نمبر منتخب کرتا ہوں۔ جب بھی آپ اس نمبر کا اندازہ لگاتے ہیں جس کو میں نے نہیں اٹھایا ہے ، میں آپ کو یہ کہنے جا رہا ہوں کہ آپ کوئی نمبر اونچی یا کم منتخب کرتے ہیں۔

اور اہم اور دلچسپ بات یہ ہے کہ اگر آپ نے غلط نمبر کا انتخاب کیا ہے تو آئیے X کہیے ، پھر آپ اس رقم کے X یونٹ ادا کرنے جارہے ہیں۔ جب آپ کو صحیح نمبر کا اندازہ ہوتا ہے تو آپ کو کھیل جیتنا ہے ، یعنی یہ وہ نمبر ہے جو میں نے اٹھایا ہے۔

مثال کے طور پر

n = 10 ، میں 6 چنتا ہوں۔

پہلے انتخاب کریں: آپ کا اندازہ ہے کہ 2 ، یہ زیادہ ہے ، اس سے بھی اوپر چلے جائیں۔ آپ $ 2 ادا کریں گے۔

دوسرا انتخاب: آپ کا اندازہ ہے کہ 4 ، اس سے کہیں زیادہ ہے ، اس سے بھی اوپر جائیں۔ آپ $ 4 ادا کریں گے۔

تیسرا انتخاب: آپ کا اندازہ ہے کہ 5 ، یہ زیادہ ہے ، اس سے بھی اوپر جانا۔ آپ $ 5 ادا کریں گے۔

کھیل اب ختم ہوگیا ہے کیونکہ آپ نے صحیح نمبر منتخب کیا ہے جو 6 ہے۔

آپ نے $ 2 + $ 4 + $ 5 = $ 11 کی ادائیگی ختم کردی۔

فرض کریں ، اگر آپ کو ایک نمبر دیا جائے جو n ≥ 1 ہے تو ، اس بات کا تعین کریں کہ آپ کے پاس کتنی رقم ہونی چاہئے تاکہ آپ اس بات کی یقین دہانی کرواسکیں کہ آپ اس کھیل کو جیتنے جارہے ہیں۔

اندازہ لگائیں کہ اعلٰی اور لوئر II

قیاس نمبر اعلی یا لوئر II کے مسئلے کے لئے الگورتھم

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 تاکہ ہم کافی رقم کا پتہ لگاسکیں جس سے ہم اپنی جیت کی یقین دہانی کراسکیں ، اس کے ل we ہم ایک نمبر سمجھ سکتے ہیں اور اس نمبر کے نیچے اور اس نمبر سے اوپر پر کام کرسکتے ہیں۔ یہ کوڈ جا رہا ہے بار بار اس کے افعال کو کال کریں۔

مسئلہ آپ سے توقع کرتا ہے زیادہ سے زیادہ کم سے کم رقم جیتنے کے ل. آپ کو ادا کرنا پڑے گی۔ یقینی طور پر مختلف اندازوں کے معاملے میں جیتنے کے ل a مختلف لاگت کی ضرورت ہوتی ہے لیکن ہمارا مقصد 1… n کے درمیان تعداد کا اندازہ لگانے کے لئے درکار کم سے کم رقم کا حساب لگانا ہے۔

نتیجہ = ریاضی.ایمن (نتیجہ ، رقم (i)) [فراہم کردہ ان پٹ کی کم سے کم رقم واپس کرتا ہے]

جہاں مقدار (i) اندازہ لگانے کے لئے بدترین ممکنہ رقم ہے i۔

اب ، جب آپ 3 فرض کرتے ہیں تو یہ بدترین صورت حال کیا ہے؟

آپ نے 1 کا انتخاب کیا ہے ، بہترین صورت میں 1 آپ کا اندازہ لگانے والا نمبر ہوسکتا ہے ، لہذا اس رقم (i) = 0 ، لیکن ہم اس کی پرواہ نہیں کر رہے ہیں ، ہم بدترین معاملے سے متعلق ہیں ، i ، ای 1 منتخب کردہ نمبر نہیں لہذا جب 1 کا انتخاب کیا جاتا ہے تو اس کی قیمت = 1+ (2,3،XNUMX) ہے۔

آپ نے 2 کا انتخاب کیا ، بہترین معاملہ میں 2 جواب ہے اور قیمت 0 ہے ، لیکن پھر بدترین صورت میں 3 یا تو 1 ہی جواب ہوتا ہے ، اور کسی تعداد کا اندازہ لگانے پر آپ کو ہمیشہ یہ معلوم ہوجاتا ہے کہ منتخب کردہ نمبر زیادہ ہے یا نہیں یا تعداد سے کم ، لہذا ہم جانتے ہوں گے کہ 1 جواب ہے یا 3 جواب ہے۔ اس وجہ سے بدترین قیمت 2 ہے۔

3 سب سے خراب لاگت کا انتخاب 3+ لاگت (1,2،XNUMX) سے ہوگی۔ حتمی لاگت ان تمام خراب ترین لاگتوں میں سے کم سے کم ہوگی۔ ہمیں جواب حاصل کرنے اور پھر اسے حفظ کرنے کے لئے بار بار کرنا پڑتا ہے۔

عمل

اندازہ نمبر ہائیر یا لوئر II کے مسئلے کے لئے سی ++ پروگرام

#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

اندازہ نمبر اعلی یا لوئر II کے مسئلے کے لئے جاوا پروگرام

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

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (n)2) کہاں "این" تعداد کی حد ہے جسے منتخب کیا جاسکتا ہے۔

خلائی پیچیدگی

O (n لاگ این) کہاں "این" تعداد کی حد ہے جسے منتخب کیا جاسکتا ہے۔