حدس بزنید شماره بالاتر یا پایین II


سطح دشواری متوسط
اغلب در آمازون گوگل مایکروسافت
صف برنامه نویسی پویا

بیان مسأله

"حدس می زنم شماره بالاتر یا پایین II" بیان می کند که ما قصد داریم بازی ای را بازی کنیم که Guess Game نام دارد. این بازی می گوید که من یک عدد را از 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 به این ترتیب که می توانیم مقدار کافی پول را که از طریق آن می توانیم از پیروزی خود اطمینان حاصل کنیم ، دریابیم ، برای این منظور می توان یک عدد را در نظر گرفت و عملیات زیر آن و بالاتر از آن را انجام داد. این کد به بازگشتی توابع آن را فراخوانی کنید.

مشکل از شما انتظار دارد حداکثر را به حداقل برسانید مبلغی که برای برنده شدن باید بپردازید. مطمئناً برای برنده شدن در صورت حدس متفاوت هزینه دیگری متفاوت است اما هدف ما محاسبه حداقل مقدار مورد نیاز برای حدس زدن عدد بین 1… n است ،

result = Math.min (نتیجه ، مقدار (i)) [حداقل ورودی های ارائه شده را برمی گرداند]

جایی که مقدار (i) بدترین مقدار ممکن برای حدس زدن عدد i است.

حال ، شما بدترین حالت را هنگام فرض 3 می دانید.

شما 1 را انتخاب کرده اید ، در بهترین حالت 1 ممکن است عددی باشد که باید حدس بزنید ، از این رو مقدار (i) = 0 است ، اما ما از این بابت اذیت نمی شویم ، ما درگیر بدترین حالت هستیم ، i 1 e نه شماره انتخاب شده از این رو هزینه هنگام انتخاب 1 = 1+ هزینه از (2,3،XNUMX) است.

شما 2 را انتخاب کردید ، در بهترین حالت 2 جواب است و هزینه آن 0 است ، اما در بدترین حالت یا 3 یا هر 1 پاسخ است و با حدس زدن یک عدد همیشه می دانید که آیا تعداد انتخاب شده بیشتر است یا کمتر از عدد است ، بنابراین می دانیم که 1 جواب است یا 3 پاسخ است. بنابراین بدترین هزینه 2 است.

انتخاب 3 در بدترین حالت 3+ هزینه از (1,2،XNUMX) است. هزینه نهایی حداقل هزینه های بدترین موارد است. برای دریافت جواب باید این کار را به صورت بازگشتی انجام دهیم و سپس آن را حفظ کنیم.

پیاده سازی

برنامه C ++ برای حدس زدن مشکل شماره بالاتر یا پایین 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) جایی که "n" محدوده اعدادی است که می تواند انتخاب شود.

پیچیدگی فضا

O (n log n) جایی که "n" محدوده اعدادی است که می تواند انتخاب شود.