Тахмин кунед, ки рақами олӣ ё поёнии II


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Amazon Google Microsoft
тартиботи ҳарбӣ Барномарезии динамикӣ

Изҳороти мушкилот

"Тахмини рақами олӣ ё поёнии II" қайд мекунад, ки мо бозӣ кардан мехоҳем, ки онро Game Guess меноманд. Дар бозӣ гуфта мешавад, ки ман рақами аз 1 то n -ро интихоб мекунам. Ҳар вақте ки шумо рақамеро, ки ман интихоб накардаам, гумон мекунед, ман ба шумо мегӯям, ки шумо рақами болотар ё пасттарро интихоб мекунед.

Ва қисми муҳим ва ҷолиб он аст, ки агар шумо рақами нодурустро интихоб кардед, бигӯем х, пас шумо х воҳиди маблағро пардохт карданӣ ҳастед. Вақте ки шумо рақами дурустро тахмин мекунед, шумо бояд ғолиб шавед, яъне ин рақами интихобкардаи ман.

мисол

n = 10, ман 6 ро интихоб мекунам.

Аввал интихоб кунед: Шумо 2 гумон мекунед, ин бузургтар аст, аз он болотар равед. Шумо 2 доллар пардохт мекунед.

Дуюм интихоб кунед: Шумо тахмин мекунед, ки 4, ин бузургтар аст, аз он болотар равед. Шумо 4 доллар пардохт мекунед.

Сеюм интихоб кунед: Шумо 5-ро тахмин мекунед, ин бузургтар аст, аз он болотар равед. Шумо 5 доллар пардохт мекунед.

Ҳоло бозӣ ба охир расид, зеро шумо рақами дурустро интихоб кардед, ки он 6 аст.

Шумо дар охир $ 2 + $ 4 + $ 5 = $ 11 пардохт мекунед.

Фарз мекунем, ки агар ба шумо рақами n 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] хоҳад буд. Арзиши ниҳоӣ ҳадди аққали ҳамаи ин хароҷоти бадтарин хоҳад буд. Мо бояд инро ба даст орем, то посух бигирем ва сипас онро аз ёд кунем.

татбиќи

Барномаи C ++ барои тахмин рақами олӣ ё поёнии 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 барои тахмин рақами олӣ ё поёнии 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 (n log n) ки дар "Н" доираи рақамҳои интихобшаванда мебошад.