ਅੰਦਾਜ਼ਾ ਲਗਾਓ ਨੰਬਰ ਉੱਚਾ ਜਾਂ ਹੇਠਲਾ II


ਮੁਸ਼ਕਲ ਪੱਧਰ ਦਰਮਿਆਨੇ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ ਗੂਗਲ Microsoft ਦੇ
ਅਰੇ ਡਾਇਨਾਮਿਕ ਪ੍ਰੋਗਰਾਮਿੰਗ

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ

“ਅੰਦਾਜ਼ਾ ਨੰਬਰ ਉੱਚਾ ਜਾਂ ਹੇਠਲਾ II” ਕਹਿੰਦਾ ਹੈ ਕਿ ਅਸੀਂ ਇੱਕ ਗੇਮ ਖੇਡਣ ਜਾ ਰਹੇ ਹਾਂ ਜਿਸ ਨੂੰ ਗੇਸ ਗੇਮ ਕਿਹਾ ਜਾਂਦਾ ਹੈ. ਖੇਡ ਕਹਿੰਦੀ ਹੈ ਕਿ ਮੈਂ 1 ਤੋਂ n ਤੱਕ ਇੱਕ ਨੰਬਰ ਚੁਣਦਾ ਹਾਂ. ਜਦੋਂ ਵੀ ਤੁਸੀਂ ਅੰਦਾਜ਼ਾ ਲਗਾਉਂਦੇ ਹੋ ਜਿਸ ਨੰਬਰ ਨੂੰ ਮੈਂ ਨਹੀਂ ਚੁਣਿਆ, ਮੈਂ ਤੁਹਾਨੂੰ ਇਹ ਕਹਿਣ ਜਾ ਰਿਹਾ ਹਾਂ ਕਿ ਤੁਸੀਂ ਇੱਕ ਨੰਬਰ ਉੱਚਾ ਜਾਂ ਘੱਟ ਚੁਣਦੇ ਹੋ.

ਅਤੇ ਮਹੱਤਵਪੂਰਣ ਅਤੇ ਦਿਲਚਸਪ ਹਿੱਸਾ ਇਹ ਹੈ ਕਿ ਜੇ ਤੁਸੀਂ ਗਲਤ ਨੰਬਰ ਚੁਣਿਆ ਹੈ, ਚਲੋ 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 ਤਾਂ ਜੋ ਅਸੀਂ ਕਾਫ਼ੀ ਰਕਮ ਦਾ ਪਤਾ ਲਗਾ ਸਕੀਏ ਜਿਸ ਤੋਂ ਅਸੀਂ ਆਪਣੀ ਜਿੱਤ ਦਾ ਭਰੋਸਾ ਦੇ ਸਕਦੇ ਹਾਂ, ਇਸਦੇ ਲਈ ਅਸੀਂ ਇੱਕ ਨੰਬਰ ਮੰਨ ਸਕਦੇ ਹਾਂ ਅਤੇ ਉਸ ਨੰਬਰ ਦੇ ਹੇਠਾਂ ਅਤੇ ਉਸ ਸੰਖਿਆ ਦੇ ਉਪਰ ਕੰਮ ਕਰ ਸਕਦੇ ਹਾਂ. ਇਹ ਕੋਡ ਜਾ ਰਿਹਾ ਹੈ ਲਗਾਤਾਰ ਇਸ ਦੇ ਫੰਕਸ਼ਨ ਨੂੰ ਕਾਲ ਕਰੋ.

ਸਮੱਸਿਆ ਤੁਹਾਡੇ ਤੋਂ ਉਮੀਦ ਕਰਦੀ ਹੈ ਵੱਧ ਤੋਂ ਘੱਟ ਕਰੋ ਤੁਹਾਨੂੰ ਜਿੱਤਣ ਲਈ ਰਕਮ ਦਾ ਭੁਗਤਾਨ ਕਰਨਾ ਪਏਗਾ. ਨਿਸ਼ਚਤ ਰੂਪ ਵਿੱਚ ਇੱਕ ਵੱਖਰੇ ਅੰਦਾਜ਼ੇ ਦੇ ਮਾਮਲੇ ਵਿੱਚ ਜਿੱਤਣ ਲਈ ਇੱਕ ਵੱਖਰੀ ਕੀਮਤ ਦੀ ਜ਼ਰੂਰਤ ਹੈ ਪਰ ਸਾਡਾ ਟੀਚਾ 1… n ਦੇ ਵਿਚਕਾਰ ਅੰਦਾਜ਼ਾ ਲਗਾਉਣ ਲਈ ਘੱਟੋ ਘੱਟ ਰਕਮ ਦੀ ਗਣਨਾ ਕਰਨਾ ਹੈ.

ਨਤੀਜਾ = ਮੈਥ.ਮਿਨ (ਨਤੀਜਾ, ਰਕਮ (i)) [ਪ੍ਰਦਾਨ ਕੀਤੇ ਨਿਵੇਸ਼ਾਂ ਦਾ ਘੱਟੋ ਘੱਟ ਵਾਪਸ ਕਰਦਾ ਹੈ]

ਜਿੱਥੇ ਰਕਮ (i) ਅੰਦਾਜ਼ਾ ਲਗਾਉਣ ਦੀ ਸੰਭਾਵਤ ਮਾਤਰਾ ਹੈ i.

ਹੁਣ, ਇਹ ਸਭ ਤੋਂ ਬੁਰਾ ਹਾਲ ਕੀ ਹੈ ਜਦੋਂ ਤੁਸੀਂ 3 ਮੰਨ ਲਓ.

ਤੁਸੀਂ 1 ਨੂੰ ਚੁਣਿਆ ਹੈ, ਸਭ ਤੋਂ ਵਧੀਆ ਕੇਸ ਵਿੱਚ 1 ਉਹ ਨੰਬਰ ਹੋ ਸਕਦਾ ਹੈ ਜਿਸਦਾ ਤੁਸੀਂ ਅੰਦਾਜ਼ਾ ਲਗਾ ਸਕਦੇ ਹੋ, ਇਸ ਲਈ ਮਾਤਰਾ (i) = 0 ਹੈ, ਪਰ ਸਾਨੂੰ ਇਸ ਬਾਰੇ ਪਰੇਸ਼ਾਨ ਨਹੀਂ ਕੀਤਾ ਜਾਂਦਾ, ਅਸੀਂ ਸਭ ਤੋਂ ਭੈੜੇ ਮਾਮਲੇ ਨਾਲ ਸਬੰਧਤ ਹਾਂ, i, e 1 ਹੈ ਨਹੀਂ ਚੁਣਿਆ ਨੰਬਰ. ਇਸ ਲਈ ਜਦੋਂ 1 ਨੂੰ ਚੁਣਿਆ ਜਾਂਦਾ ਹੈ ਤਾਂ ਕੀਮਤ = 1+ ਤੋਂ (2,3).

ਤੁਸੀਂ 2 ਨੂੰ ਚੁਣਿਆ, ਸਭ ਤੋਂ ਵਧੀਆ ਕੇਸ ਵਿੱਚ 2 ਉੱਤਰ ਹੁੰਦਾ ਹੈ ਅਤੇ ਲਾਗਤ 0 ਹੁੰਦੀ ਹੈ, ਪਰ ਫਿਰ ਸਭ ਤੋਂ ਮਾੜੇ ਹਾਲਾਤਾਂ ਵਿੱਚ 3 ਜਾਂ ਕੋਈ 1 ਉੱਤਰ ਹੁੰਦਾ ਹੈ, ਅਤੇ ਇੱਕ ਨੰਬਰ ਦਾ ਅਨੁਮਾਨ ਲਗਾਉਣ ਤੇ ਤੁਹਾਨੂੰ ਹਮੇਸ਼ਾਂ ਪਤਾ ਲੱਗ ਜਾਂਦਾ ਹੈ ਕਿ ਚੁਣੀ ਗਈ ਗਿਣਤੀ ਵਧੇਰੇ ਹੈ ਜਾਂ ਨਹੀਂ ਜਾਂ ਗਿਣਤੀ ਤੋਂ ਘੱਟ, ਇਸ ਲਈ ਅਸੀਂ ਜਾਣਦੇ ਹਾਂ ਕਿ 1 ਦਾ ਜਵਾਬ ਹੈ ਜਾਂ 3 ਦਾ ਜਵਾਬ ਹੈ. ਇਸ ਲਈ ਸਭ ਤੋਂ ਖਰਾਬ ਕੀਮਤ 2 ਹੈ.

3 ਸਭ ਤੋਂ ਖਰਾਬ ਖਰਚਿਆਂ ਨੂੰ ਚੁਣਨਾ (+ 3) ਤੋਂ 1,2+ ਦੀ ਕੀਮਤ ਹੋਵੇਗੀ. ਅੰਤਮ ਲਾਗਤ ਇਹ ਸਭ ਖਰਾਬ ਖਰਚਿਆਂ ਦੀ ਘੱਟੋ ਘੱਟ ਹੋਵੇਗੀ. ਸਾਨੂੰ ਜਵਾਬ ਪ੍ਰਾਪਤ ਕਰਨ ਲਈ ਇਸ ਨੂੰ ਲਗਾਤਾਰ ਕਰਨਾ ਪੈਂਦਾ ਹੈ ਅਤੇ ਫਿਰ ਇਸਨੂੰ ਯਾਦ ਰੱਖਣਾ ਹੁੰਦਾ ਹੈ.

ਲਾਗੂ

ਅਨੁਮਾਨ ਨੰਬਰ ਵਧੇਰੇ ਜਾਂ ਘੱਟ 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

ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਨ2) ਜਿੱਥੇ ਕਿ “ਐਨ” ਗਿਣਤੀ ਦੀ ਸੀਮਾ ਹੈ, ਜੋ ਕਿ ਚੁਣਿਆ ਜਾ ਸਕਦਾ ਹੈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

O (n ਲਾਗ n) ਜਿੱਥੇ ਕਿ “ਐਨ” ਗਿਣਤੀ ਦੀ ਸੀਮਾ ਹੈ, ਜੋ ਕਿ ਚੁਣਿਆ ਜਾ ਸਕਦਾ ਹੈ.