யூக எண் அதிக அல்லது கீழ் 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 இதன் மூலம் நமது வெற்றியை உறுதிப்படுத்தக்கூடிய போதுமான பணத்தை நாம் கண்டுபிடிக்க முடியும், இதற்காக நாம் ஒரு எண்ணைக் கருதி அந்த எண்ணிக்கையின் கீழும் அந்த எண்ணுக்கு மேலேயும் செயல்பாடுகளைச் செய்யலாம். இந்த குறியீடு போகிறது மீண்டும் மீண்டும் அதன் செயல்பாடுகளை அழைக்கவும்.

பிரச்சனை உங்களை எதிர்பார்க்கிறது அதிகபட்சத்தைக் குறைக்கவும் வெற்றி பெற நீங்கள் செலுத்த வேண்டிய தொகை. நிச்சயமாக வேறு யூகத்தின் போது வெற்றிபெற வேறு செலவு தேவைப்படுகிறது, ஆனால் 1… n க்கு இடையிலான எண்ணை யூகிக்க தேவையான குறைந்தபட்ச தொகையை கணக்கிடுவதே எங்கள் குறிக்கோள்.

result = Math.min (முடிவு, தொகை (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) எங்கே “N” தேர்வு செய்யக்கூடிய எண்களின் வரம்பு.

விண்வெளி சிக்கலானது

O (n log n) எங்கே “N” தேர்வு செய்யக்கூடிய எண்களின் வரம்பு.