Жоғары немесе төменгі II санын тап


Күрделілік дәрежесі орта
Жиі кіреді Amazon Google Microsoft
Array Динамикалық бағдарламалау

Проблемалық мәлімдеме

«Жоғары немесе төменгі II санды тап» ойынында «Ойын тап» деп аталатын ойын ойнайтынымызды айтады. Ойында мен 1-ден n-ге дейінгі санды таңдаймын дейді. Мен таңдамаған санды болжаған сайын мен сізге жоғары немесе төмен санды таңдаймын деп айтамын.

Маңызды және қызықты бөлігі - егер сіз қате санды таңдаған болсаңыз, х-ті алайық, сонда сіз соманың х бірлігін төлейтін боласыз. Сіз дұрыс санды тапқанда, яғни мен таңдаған санды ойнағанда жеңіске жетуіңіз керек.

мысал

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+ құрайды.

сіз 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 санына арналған 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

Күрделілікті талдау

Уақыттың күрделілігі

O (n2) қайда «N» таңдалатын сандар ауқымы.

Ғарыштың күрделілігі

O (n log n) қайда «N» таңдалатын сандар ауқымы.