Погодете го бројот поголем или долен II


Ниво на тешкотија Медиум
Често прашувано во Амазон Google Мајкрософт
Низа Динамичко програмирање

Изјава за проблем

„Погодете го повисокиот или долниот број на бројот“ наведува дека ние ќе играме игра што се вика Погодена игра. Играта вели дека избирам број од 1 до n. Кога и да го погодите бројот што не сум го избрал, ќе ви кажам дека одбирате број повисок или понизок.

И важниот и интересен дел е дека ако сте одбрале погрешен број, да речеме x, тогаш ќе платите x единици од износот. Треба да ја добиете играта кога ќе го погодите точниот број, т.е. тоа е бројот што го избрав.

пример

n = 10, избирам 6.

Прво изберете: Претпоставувате 2, тоа е поголемо, одете над тоа. Willе платите 2 УСД.

Втор избор: Претпоставувате 4, поголем е, одете над тоа. Willе платите 4 долари.

Трет избор: Претпоставувате 5, поголем е, одете над тоа. Willе платите 5 долари.

Играта заврши сега затоа што сте го одбрале точниот број што е 6.

На крај плаќате 2 $ + 4 $ + 5 $ = 11 $.

Да претпоставиме, ако ви дадат број кој е n ≥ 1, утврдете колку пари треба да имате за да можете да уверите дека со оваа доволно сума ќе ја добиете оваа игра.

Погодете го бројот поголем или долен 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,

резултат = математика.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). Конечната цена ќе биде минимум од сите овие најлоши трошоци. Ова мора да го направиме рекурзивно за да го добиеме одговорот и потоа да го запаметиме.

Имплементација

Програма C ++ за Погодете проблем со повисок или долен број XNUMX

#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

Јава програма за погоди проблем со повисок или долен број XNUMX

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) каде „Н“ е опсегот на броеви што може да се изберат.

Комплексноста на просторот

О (н дневник н) каде „Н“ е опсегот на броеви што може да се изберат.