تخمين رقم أعلى أو أقل II


مستوى الصعوبة متوسط
كثيرا ما يطلب في أمازون جوجل Microsoft
مجموعة البرمجة الديناميكية

المشكلة بيان

تنص عبارة "تخمين الرقم الأعلى أو الأدنى 1" على أننا سنلعب لعبة تسمى لعبة التخمين. تقول اللعبة أنني أختار رقمًا من XNUMX إلى 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 ،

نتيجة = Math.min (نتيجة ، المبلغ (i)) [إرجاع الحد الأدنى من المدخلات المقدمة]

حيث المبلغ (i) هو أسوأ مبلغ ممكن لتخمين الرقم i.

الآن ، ما هي هذه الحالة الأسوأ عندما تفترض 3.

لقد اخترت 1 ، في أفضل الأحوال ، قد يكون الرقم 1 هو الرقم الذي يجب أن تخمنه ، ومن ثم فإن المبلغ (i) = 0 ، لكننا لا نشعر بالقلق حيال ذلك ، فنحن مهتمون بأسوأ الحالات ، i ، e 1 هو ليس الرقم المختار. ومن ثم فإن التكلفة عند اختيار 1 هي = 1+ تكلفة من (2,3،XNUMX).

لقد اخترت 2 ، في أفضل الحالات 2 هي الإجابة والتكلفة هي 0 ، ولكن في أسوأ الحالات ، إما 3 أو إما 1 هي الإجابة ، وعند تخمين رقم ، يمكنك دائمًا معرفة ما إذا كان الرقم المختار أكبر أو أقل من الرقم ، ومن ثم نعلم أن 1 هو الإجابة أو 3 هو الإجابة. ومن ثم فإن التكلفة الأسوأ هي 2.

اختيار 3 تكلفة أسوأ حالة ستكون 3+ تكلفة من (1,2،XNUMX). ستكون التكلفة النهائية هي الحد الأدنى لجميع هذه التكاليف الأسوأ. علينا القيام بذلك بشكل متكرر للحصول على الإجابة ثم حفظها.

تطبيق

برنامج C ++ لمشكلة Guess Number High أو Lower 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

برنامج Java لمشكلة التخمين رقم الأعلى أو السفلي الثاني

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) أين "ن" هو نطاق الأرقام التي يمكن اختيارها.

تعقيد الفضاء

س (ن سجل ن) أين "ن" هو نطاق الأرقام التي يمكن اختيارها.