ഹയർ നമ്പർ ഉയർന്നതോ താഴ്ന്നതോ II  


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ആമസോൺ ഗൂഗിൾ മൈക്രോസോഫ്റ്റ്
അറേ ഡൈനാമിക് പ്രോഗ്രാമിംഗ്

പ്രശ്നം പ്രസ്താവന  

“ഗെസ്സ് നമ്പർ ഹയർ അല്ലെങ്കിൽ ലോവർ II” പറയുന്നത് ഞങ്ങൾ ഗെസ് ഗെയിം എന്ന് വിളിക്കുന്ന ഒരു ഗെയിം കളിക്കാൻ പോകുന്നു എന്നാണ്. 1 മുതൽ n വരെ ഞാൻ ഒരു നമ്പർ തിരഞ്ഞെടുക്കുന്നുവെന്ന് ഗെയിം പറയുന്നു. ഞാൻ തിരഞ്ഞെടുക്കാത്ത നമ്പർ നിങ്ങൾ when ഹിക്കുമ്പോഴെല്ലാം, ഞാൻ നിങ്ങളോട് പറയാൻ പോകുന്നത് നിങ്ങൾ ഒരു സംഖ്യ ഉയർന്നതോ അതിൽ കുറവോ ആണ്.

പ്രധാനപ്പെട്ടതും രസകരവുമായ ഭാഗം, നിങ്ങൾ തെറ്റായ നമ്പർ തിരഞ്ഞെടുക്കുകയാണെങ്കിൽ, നമുക്ക് x എന്ന് പറയാം, അപ്പോൾ നിങ്ങൾ തുകയുടെ x യൂണിറ്റുകൾ നൽകാൻ പോകുന്നു. ശരിയായ നമ്പർ ess ഹിക്കുമ്പോൾ നിങ്ങൾ ഗെയിം വിജയിക്കണം, അതായത്, അതാണ് ഞാൻ തിരഞ്ഞെടുത്ത നമ്പർ.

ഉദാഹരണം  

n = 10, ഞാൻ 6 തിരഞ്ഞെടുക്കുന്നു.

ആദ്യം തിരഞ്ഞെടുക്കുക: നിങ്ങൾ 2 ഹിക്കുന്നു, ഇത് വലുതാണ്, അതിനേക്കാൾ മുകളിലേക്ക് പോകുക. നിങ്ങൾ $ 2 നൽകും.

രണ്ടാമത്തേത് തിരഞ്ഞെടുക്കുക: നിങ്ങൾ 4 ഹിക്കുന്നു, ഇത് വലുതാണ്, അതിനേക്കാൾ മുകളിലേക്ക് പോകുക. നിങ്ങൾ $ 4 നൽകും.

മൂന്നാമത്തെ തിരഞ്ഞെടുപ്പ്: നിങ്ങൾ 5 ഹിക്കുന്നു, ഇത് വലുതാണ്, അതിനേക്കാൾ മുകളിലേക്ക് പോകുക. നിങ്ങൾ $ 5 നൽകും.

6 എന്ന ശരിയായ നമ്പർ നിങ്ങൾ തിരഞ്ഞെടുത്തതിനാൽ ഗെയിം ഇപ്പോൾ അവസാനിച്ചു.

നിങ്ങൾ pay 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 അതിനാൽ ഞങ്ങളുടെ വിജയത്തിന് ഉറപ്പ് നൽകാൻ കഴിയുന്നത്ര പണം കണ്ടെത്താനാകും, ഇതിനായി നമുക്ക് ഒരു നമ്പർ എടുത്ത് ആ സംഖ്യയ്ക്ക് താഴെയും ആ സംഖ്യയ്ക്ക് മുകളിലും പ്രവർത്തനങ്ങൾ നടത്താൻ കഴിയും. ഈ കോഡ് പോകുന്നു ആവർത്തിച്ച് അതിന്റെ ഫംഗ്ഷനുകൾ വിളിക്കുക.

പ്രശ്നം നിങ്ങളെ പ്രതീക്ഷിക്കുന്നു പരമാവധി കുറയ്ക്കുക വിജയിക്കാൻ നിങ്ങൾ നൽകേണ്ട തുക. തീർച്ചയായും മറ്റൊരു ess ഹത്തിന്റെ കാര്യത്തിൽ വിജയിക്കാൻ മറ്റൊരു ചിലവ് ആവശ്യമാണ്, എന്നാൽ 1… n തമ്മിലുള്ള സംഖ്യ ess ഹിക്കാൻ ആവശ്യമായ ഏറ്റവും കുറഞ്ഞ തുക കണക്കാക്കുക എന്നതാണ് ഞങ്ങളുടെ ലക്ഷ്യം.

result = Math.min (ഫലം, തുക (i)) [നൽകിയ ഇൻപുട്ടുകളുടെ ഏറ്റവും കുറഞ്ഞ തുക നൽകുന്നു]

ഇവിടെ സംഖ്യ (i) നമ്പർ i ഹിക്കാൻ ഏറ്റവും മോശമായ തുകയാണ്.

ഇപ്പോൾ, നിങ്ങൾ 3 എന്ന് when ഹിക്കുമ്പോൾ ഈ ഏറ്റവും മോശം അവസ്ഥ എന്താണ്.

നിങ്ങൾ 1 തിരഞ്ഞെടുത്തു, ഏറ്റവും മികച്ചത് 1 നിങ്ങൾ to ഹിക്കേണ്ട സംഖ്യയായിരിക്കാം, അതിനാൽ തുക (i) = 0, പക്ഷേ ഞങ്ങൾ അതിനെക്കുറിച്ച് ചിന്തിക്കുന്നില്ല, ഏറ്റവും മോശം അവസ്ഥയെക്കുറിച്ച് ഞങ്ങൾ ആശങ്കപ്പെടുന്നു, i, e 1 തിരഞ്ഞെടുത്ത നമ്പറല്ല. അതിനാൽ 1 തിരഞ്ഞെടുക്കുമ്പോൾ ചെലവ് = 1+ (2,3) മുതൽ.

ഇതും കാണുക
പലിൻഡ്രോം പാർട്ടീഷനിംഗ്

നിങ്ങൾ 2 തിരഞ്ഞെടുത്തു, മികച്ച കേസിൽ 2 ഉത്തരവും ചെലവ് 0 ഉം ആണ്, എന്നാൽ ഏറ്റവും മോശം അവസ്ഥയിൽ 3 അല്ലെങ്കിൽ 1 ആണ് ഉത്തരം, കൂടാതെ ഒരു നമ്പർ ing ഹിക്കുമ്പോൾ, തിരഞ്ഞെടുത്ത നമ്പർ വലുതാണോ എന്ന് നിങ്ങൾക്ക് എല്ലായ്പ്പോഴും അറിയാൻ കഴിയും. അല്ലെങ്കിൽ‌ സംഖ്യയേക്കാൾ‌ കുറവാണ്, അതിനാൽ‌ 1 ഉത്തരം അല്ലെങ്കിൽ‌ 3 ഉത്തരം ആണെന്ന് ഞങ്ങൾ‌ക്കറിയാം. അതിനാൽ ഏറ്റവും മോശം ചെലവ് 2 ആണ്.

ഏറ്റവും മോശം അവസ്ഥ 3 തിരഞ്ഞെടുക്കുന്നത് (3) എന്നതിൽ നിന്ന് 1,2+ വിലയായിരിക്കും. ഈ ഏറ്റവും മോശം ചെലവുകളുടെ ഏറ്റവും കുറഞ്ഞ നിരക്കാണ് അന്തിമ ചെലവ്. ഉത്തരം നേടുന്നതിനും മന or പാഠമാക്കുന്നതിനും ഞങ്ങൾ ഇത് ആവർത്തിച്ച് ചെയ്യണം.

നടപ്പിലാക്കൽ  

ഗസ്സ് നമ്പർ ഹയർ അല്ലെങ്കിൽ ലോവർ 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 (n2) എവിടെ “N” തിരഞ്ഞെടുക്കാവുന്ന സംഖ്യകളുടെ ശ്രേണിയാണ്.

ബഹിരാകാശ സങ്കീർണ്ണത

O (n ലോഗ് n) എവിടെ “N” തിരഞ്ഞെടുക്കാവുന്ന സംഖ്യകളുടെ ശ്രേണിയാണ്.