លេខស្មានខ្ពស់ជាងឬទាបជាងលេខ ២


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon ក្រុមហ៊ុន google ក្រុមហ៊ុន Microsoft
អារេ ការសរសេរកម្មវិធីឌីណាមិក

សេចក្តីថ្លែងការណ៍បញ្ហា។

“ Guess Number Higher or Lower II” ចែងថាយើងនឹងលេងល្បែងមួយដែលមានឈ្មោះថា Guess Game ។ ល្បែងនិយាយថាខ្ញុំយកលេខពីលេខ ១ ដល់លេខ n ។ រាល់ពេលដែលអ្នកទាយលេខដែលខ្ញុំមិនបានជ្រើសរើសខ្ញុំនឹងប្រាប់អ្នកថាអ្នកយកលេខខ្ពស់ជាងឬទាបជាង។

ហើយផ្នែកសំខាន់និងគួរឱ្យចាប់អារម្មណ៍នោះគឺថាប្រសិនបើអ្នកជ្រើសរើសលេខខុសចូរនិយាយថា x បន្ទាប់មកអ្នកនឹងបង់ចំនួនឯកតា x ។ អ្នកត្រូវបានគេសន្មត់ថានឹងឈ្នះការប្រកួតនៅពេលដែលអ្នកទាយលេខត្រឹមត្រូវពោលគឺលេខដែលខ្ញុំបានជ្រើសរើស។

ឧទាហរណ៍

n = 10 ខ្ញុំជ្រើសរើសលេខ 6 ។

ជ្រើសរើសទីមួយ៖ អ្នកទាយលេខ ២ វាធំជាងនេះទៅទៀត។ អ្នកនឹងបង់ ២ ដុល្លារ។

ជ្រើសរើសទីពីរ៖ អ្នកទាយលេខ ៤ វាធំជាងនេះទៅទៀត។ អ្នកនឹងបង់ប្រាក់ ៤ ដុល្លារ។

ជ្រើសរើសទីបី៖ អ្នកទាយ ៥, វាធំជាង, លើសពីនេះ។ អ្នកនឹងបង់ ៥ ដុល្លារ។

ល្បែងបានចប់ហើយឥឡូវនេះពីព្រោះអ្នកបានជ្រើសរើសលេខត្រឹមត្រូវដែលមានលេខ ៦ ។

អ្នកបញ្ចប់ការបង់ប្រាក់ ២ ដុល្លារ ៤ ដុល្លារ ៥ ដុល្លារ = ១១ ដុល្លារ។

ឧបមាថាប្រសិនបើអ្នកត្រូវបានគេផ្តល់លេខដែលជាលេខ≥ ១ កំណត់ចំនួនទឹកប្រាក់ដែលអ្នកគួរតែមានដូច្នេះអ្នកអាចធានាថាជាមួយនឹងចំនួនទឹកប្រាក់គ្រប់គ្រាន់អ្នកនឹងឈ្នះហ្គេមនេះ។

លេខស្មានខ្ពស់ជាងឬទាបជាងលេខ ២

ក្បួនដោះស្រាយសម្រាប់លេខស្មានលេខខ្ពស់រឺទាបជាងលេខ ២

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 ដូច្នេះយើងអាចរកបានចំនួនទឹកប្រាក់គ្រប់គ្រាន់ដែលយើងអាចធានាបាននូវជ័យជំនះរបស់យើងសម្រាប់ចំណុចនេះយើងអាចសន្មត់លេខនិងធ្វើប្រតិបត្តិការនៅខាងក្រោមលេខនោះនិងខាងលើលេខនោះ។ លេខកូដនេះនឹងទៅ កើតឡើងវិញ ហៅមុខងាររបស់វា។

បញ្ហារំពឹងថាអ្នកនឹង បង្រួមអប្បបរមា ចំនួនទឹកប្រាក់ដែលអ្នកនឹងត្រូវចំណាយដើម្បីឈ្នះ។ ប្រាកដជាមានការចំណាយផ្សេងៗគ្នាដើម្បីឈ្នះក្នុងករណីមានការប៉ាន់ស្មានខុសគ្នាប៉ុន្តែគោលដៅរបស់យើងគឺត្រូវគណនាចំនួនអប្បបរមាដែលត្រូវការដើម្បីទាយលេខចន្លោះពី ១ …ន,

លទ្ធផល = Math.min (លទ្ធផលចំនួន (ខ្ញុំ)) [ត្រឡប់អប្បបរមានៃធាតុចូលដែលបានផ្តល់]

ដែលចំនួន (i) គឺជាករណីដ៏អាក្រក់បំផុតដែលអាចកើតមានសំរាប់ការទាយលេខ i ។

ឥឡូវនេះអ្វីដែលជាករណីដ៏អាក្រក់បំផុតនេះគឺនៅពេលដែលអ្នកសន្មត់ ៣ ។

អ្នកបានជ្រើសរើសលេខ ១ ក្នុងករណីដ៏ល្អបំផុត ១ អាចជាលេខដែលអ្នកត្រូវទាយហេតុដូចនេះចំនួន (i) = ០ ប៉ុន្តែយើងមិនធុញទ្រាន់នឹងរឿងនោះទេយើងបារម្ភពីករណីអាក្រក់បំផុតខ្ញុំ ១ គឺអ៊ី។ មិនមែនលេខដែលបានជ្រើសរើសទេ។ ថ្លៃដើមពេលជ្រើសរើស ១ ត្រូវបានចំណាយ = (១++) ពី (២,៣) ។

អ្នកជ្រើសរើសលេខ ២ ក្នុងករណីដែលល្អបំផុត ២ គឺចម្លើយហើយថ្លៃដើមគឺ ០ ប៉ុន្តែបន្ទាប់មកក្នុងករណីដែលអាក្រក់បំផុតទាំង ៣ រឺ ១ គឺជាចម្លើយហើយនៅពេលទាយលេខអ្នកតែងតែដឹងថាតើលេខដែលត្រូវបានជ្រើសរើសធំជាង ឬតិចជាងលេខដូចនេះយើងអាចដឹងថា ១ ជាចម្លើយឬ ៣ ជាចម្លើយ។ ហេតុដូច្នេះថ្លៃដើមដែលអាក្រក់បំផុតគឺ ២ ។

ការជ្រើសរើស ៣ ករណីដែលអាក្រក់បំផុតនឹងត្រូវចំណាយ ៣+ ពី (១.២) ។ ការចំណាយចុងក្រោយនឹងជាអប្បបរមានៃការចំណាយដ៏អាក្រក់បំផុត។ យើងត្រូវធ្វើរឿងនេះម្តងទៀតដើម្បីទទួលបានចម្លើយហើយបន្ទាប់មកទន្ទេញចាំវា។

ការអនុវត្តន៍

កម្មវិធី 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

កម្មវិធីចាវ៉ាសំរាប់បញ្ហាលេខខ្ពស់រឺទាបជាងលេខ ២

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” គឺជាជួរនៃលេខដែលអាចត្រូវបានជ្រើសរើស។

ភាពស្មុគស្មាញនៃលំហ

O (n log n) ដែលជាកន្លែងដែល “ n” គឺជាជួរនៃលេខដែលអាចត្រូវបានជ្រើសរើស។