Число предположений выше или ниже II


Сложный уровень средний
Часто спрашивают в Амазонка Google Microsoft
массив Динамическое программирование

Постановка задачи

«Угадай число выше или ниже 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, amount (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 ++ для задачи Guess Number Higher или Lower 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

Программа на Java для задачи Guess Number Higher или Lower 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) в котором «Н» это диапазон чисел, который можно выбрать.

Космическая сложность

O (п войти п) в котором «Н» это диапазон чисел, который можно выбрать.