අනුමාන අංකය ඉහළ හෝ පහළ 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 (ප්‍රති result ලය, ප්‍රමාණය (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 ගැටළුව සඳහා C ++ වැඩසටහන

#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” යනු තෝරා ගත හැකි සංඛ්‍යා පරාසයයි.

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (n ලොග් එන්) එහිදී “N” යනු තෝරා ගත හැකි සංඛ්‍යා පරාසයයි.