ប្រតិបត្តិការអប្បបរមាដើម្បីបំលែង X ទៅអ៊ី


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon រោងចក្រ និយមជ្រុល Fourkites ដោយឡែកក្រុមហ៊ុន JP Morgan Myntra ក្រុមហ៊ុន Samsung តាម Online ការ៉េ
ការស្វែងរកដំបូង ក្រាប

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

បញ្ហា "ប្រតិបត្តិការអប្បបរមាដើម្បីបម្លែង X ទៅ Y" បញ្ជាក់ថាអ្នកត្រូវបានផ្តល់លេខពីរនិង X វាចាំបាច់ត្រូវបម្លែង X ទៅជា Y ដោយប្រើប្រតិបត្តិការដូចខាងក្រោមៈ

លេខចាប់ផ្តើមគឺ X។ ប្រតិបត្តិការដូចខាងក្រោមអាចត្រូវបានអនុវត្តលើ X និងលើលេខដែលត្រូវបានបង្កើតជាលទ្ធផលមធ្យម។

  1. គុណនឹងលេខដោយ ២ ។
  2. បន្ថយចំនួនដោយ ១ ។

ស្វែងយល់ពីចំនួនជំហានអប្បបរមាដែលត្រូវការដើម្បីបំលែង X ទៅជាអ៊ីដោយប្រើប្រតិបត្តិការដែលបានរៀបរាប់ខាងលើ។

ឧបសគ្គ៖ 0 <X, Y <១០០០

ឧទាហរណ៍

X = 3, Y = 11
3

ការពន្យល់: ៣ * ២ = ៦, ៦ * ២ = ១២, ១២-១ = ១១ ៣ ជំហាន

X = 2, Y = 10
5

ការពន្យល់: ២ * ២ = ៤, ៤-១ = ៣, ៣ * ២ = ៦, ៦-១ = ៥, ៥ * ២ = ១០ -> ៥ ជំហាន

វិធីសាស្រ្ត

យើងអនុវត្តក BFS ក្បួនដោះស្រាយដែលមានមូលដ្ឋាន។ បន្ទាប់មកយើងអាចធ្វើប្រតិបត្ដិការទាំង ២ ដោយយើងគុណនឹង ២ ឬដកដោយ ១ ។ តាមវិធីនេះយើងអាចទៅដល់ចំនួនទាំងអស់ដែលអាចត្រូវបានបង្កើតដោយប្រើលេខចាប់ផ្តើម X ហើយធ្វើប្រតិបត្តិការពីរដែលបានផ្តល់អោយ។ ប្រសិនបើលេខដែលបានបង្កើតស្មើនឹងចំនួនបញ្ចូល Y ត្រូវបានទទួល។ ដូច្នេះយើងគ្រាន់តែត្រឡប់ចំនួនជំហានដែលត្រូវធ្វើដើម្បីបង្កើតលេខ Y។ ខណៈពេលបង្កើតលេខវាចាំបាច់ត្រូវចងចាំចំណុចដូចខាងក្រោមៈ

  1. យើងមិនអើពើនឹងលេខពីការបញ្ចូលទៅក្នុងជួរ BFS ប្រសិនបើលេខដែលបានបង្កើតមិនពេញចិត្តនឹងឧបសគ្គ។
  2. ប្រសិនបើលេខដែលបានបង្កើតបច្ចុប្បន្នត្រូវបានបង្កើតរួចហើយពីមុន។ យើងមិនអើពើនឹងលេខដោយមិនបន្ថែមវាទៅជួរ BFS ។ ឈុតហាសត្រូវបានប្រើដើម្បីតាមដានលេខដែលត្រូវបានបង្កើតរហូតមកដល់ពេលនេះ។
  3. យើងតាមដានចំនួននៃប្រតិបត្តិការ (នៅក្នុងឈ្មោះដែលមានឈ្មោះ កម្រិត) អនុវត្តដើម្បីបង្កើតលេខពីលេខចាប់ផ្តើម X ដោយអនុវត្តប្រតិបត្តិការដែលត្រូវការ។

ក្បួនដោះស្រាយដើម្បីស្វែងរកប្រតិបត្តិការអប្បបរមាដើម្បីបម្លែង X ទៅ Y

  1. បង្កើត ជួរ សម្រាប់ការឆ្លងកាត់ BFS ហើយបញ្ចូលលេខចាប់ផ្តើម X ហើយវាឈានដល់ជួរ។ កម្រិតនៃលេខចាប់ផ្តើមគឺ ០ ព្រោះចំនួនប្រតិបត្តិការដែលត្រូវការដើម្បីប្តូរ X ទៅជា X គឺ ០ ។
  2. បង្កើត ហាស់សេត ដែលផ្ទុកចំនួនដែលបានបង្កើតរហូតមកដល់ពេលនេះ។
  3. បន្ទាប់មកចាប់ផ្តើមការផ្លាស់ប្តូរ BFS ។
  4. លោតថ្នាំងពីជួរប្រសិនបើតម្លៃថ្នាំងស្មើនឹងចំនួនបញ្ចូល Y. និងកម្រិតត្រឡប់មកវិញ (ចំនួនអប្បបរមានៃប្រតិបត្តិការពី X) នៃថ្នាំងនេះ។
  5. ម៉្យាងទៀតបន្ថែមថ្នាំងនេះទៅក្នុងឈុតហាសរបស់យើង (សម្គាល់វាថាបានទស្សនា) ។
  6. ឥឡូវគុណតំលៃថ្នាំងដែលបានបង្កើតដោយគុណនឹង ២ ហើយពិនិត្យមើលថាតើវាមាននៅក្នុងសំណុំដែរឬទេ។
  7. ប្រសិនបើលេខដែលបានបង្កើតមិនមាននៅក្នុងសំណុំ។ ដូច្នេះបញ្ចូលលេខទៅក្នុងជួររួមជាមួយកម្រិតរបស់វា (កម្រិតនៃថ្នាំងនេះបានបង្កើត = កម្រិតនៃកូនកាត់ (ឪពុកម្តាយ) + 1) ។
  8. បន្ថយតម្លៃថ្នាំងដែលបានកើនឡើងដោយ 1 ហើយពិនិត្យមើលថាតើវាមាននៅក្នុងសំណុំដែរឬទេ។
  9. ប្រសិនបើលេខដែលបានបង្កើតមិនមាននៅក្នុងសំណុំ។ ដូច្នេះបញ្ចូលលេខទៅក្នុងជួររួមជាមួយកម្រិតរបស់វា (កម្រិតនៃថ្នាំងនេះបានបង្កើត = កម្រិតនៃកូនកាត់ (ឪពុកម្តាយ) + 1) ។
  10. ធ្វើជំហានដដែលៗម្តងហើយម្តងទៀតនូវជំហាន ៣-៩ រហូតដល់យើងជួបស្ថានភាពវិលត្រឡប់ ជំហានទី ៤ ។

ក្បួនដោះស្រាយត្រូវបានបង្ហាញនៅខាងក្រោម៖

ប្រតិបត្តិការអប្បបរមាដើម្បីបំលែង X ទៅអ៊ី

លេខកូដ

កូដ C ++ ដើម្បីស្វែងរកប្រតិបត្តិការអប្បបរមាដើម្បីបំលែង X ទៅ Y

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

/* class definition to treat 
numbers generated as nodes */
class Node
{
    public:
    int num;
    int level;
    
    Node(int num,int level)
    {
        this->num = num;
        this->level = level;
    }
};

/* function to find minimum number of 
operations required to convert x into y */
int minOperation(int x,int y)
{
    queue<Node*> q;
    unordered_set <int> us;
    
    Node *node = new Node(x,0);
    q.push(node);
    
    while(!q.empty())
    {
        Node *top = q.front();
        q.pop();
        
        if(top->num == y)
        return top->level;
        
        us.insert(top->num);
        
        /* Multiplication Operation */
        if(us.find(2*top->num) == us.end())
        {
            Node *temp = new Node(2*top->num,top->level+1);
            q.push(temp);
        }
        
        /* Subtraction Operation */
        if(us.find(top->num-1) == us.end() && top->num-1 > 0)
        {
            Node *temp = new Node(top->num-1,top->level+1);
            q.push(temp);
        }
    }
}
/* Main function */
int main()
{
    int x = 2,y = 10;
    cout<<minOperation(x,y)<<endl;
    
    return 0;
}
5

កូដចាវ៉ាដើម្បីស្វែងរកប្រតិបត្តិការអប្បបរមាដើម្បីបំលែង X ទៅអ៊ី

import java.util.*;
import java.io.*;

class TutorialCup 
{
    /* class definition to treat 
    numbers generated as nodes */
    static class Node
    {
        int num;
        int level;
        
        Node(int num,int level)
        {
            this.num = num;
            this.level = level;
        }
    }
    
    /* function to find minimum number of 
    operations required to convert x into y */
    static int minOperation(int x,int y)
    {
        Queue <Node> q = new LinkedList<>();
        HashSet <Integer> hs = new HashSet<Integer>();
        
        Node node = new Node(x,0);
        q.add(node);
        
        while(!q.isEmpty())
        {
            Node top = q.poll();
            
            if(top.num == y)
            return top.level;
            
            hs.add(top.num);
            
            /* Multiplication Operation */
            if(!hs.contains(2*top.num))
            {
                Node temp = new Node(2*top.num,top.level+1);
                q.add(temp);
            }
            
            /* Subtraction Operation */
            if(!hs.contains(top.num-1) && top.num-1 > 0)
            {
                Node temp = new Node(top.num-1,top.level+1);
                q.add(temp);
            }
        }
        
        return 0;
    }
    /* Main function */
  public static void main (String[] args) 
  {
      int x = 2,y = 10;
        System.out.println(minOperation(x,y));
  }
}
5

ការវិភាគស្មុគស្មាញ

ស្មុគស្មាញពេលវេលា

វាពិបាកក្នុងការអត្ថាធិប្បាយអំពីភាពស្មុគស្មាញនៃពេលវេលាសម្រាប់ការស្វែងរកលេខដោយប្រើវិធីខាងលើ។ ប៉ុន្តែយើងនៅតែអាចផ្តល់យោបល់អំពីភាពស្មុគស្មាញពេលវេលាដ៏អាក្រក់បំផុត។ ក្នុងករណីដ៏អាក្រក់បំផុតអ្វីដែលអាចកើតឡើងគឺយើងត្រូវឆ្លងកាត់ចំនួនទាំងអស់ដែលមានវត្តមាននៅក្រោមឧបសគ្គ។ សូម្បីតែឆ្លងកាត់លេខទាំងអស់យើងមិនអាចរកលេខដែលយើងត្រូវការទេ។ ដូច្នេះពេលវេលាស្មុគស្មាញគឺ O (N)ដែល N ជាធាតុធំបំផុតដែលអាចធ្វើទៅបានក្រោមឧបសគ្គដែលបានផ្តល់។

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

វាពិបាកក្នុងការធ្វើអត្ថាធិប្បាយអំពីភាពស្មុគស្មាញនៃអវកាសផងដែរ។ ប៉ុន្តែស្រដៀងនឹងអ្វីដែលយើងបានធ្វើជាមួយពេលវេលាស្មុគស្មាញ។ ដូច្នេះភាពដូចគ្នាសម្រាប់ភាពស្មុគស្មាញនៃលំហ។ ក្នុងករណីដ៏អាក្រក់បំផុតយើងនឹងបញ្ចូលធាតុទាំងអស់ទៅក្នុងជួរ។ នេះធ្វើឱ្យក្បួនដោះស្រាយត្រូវយក O (N) ចន្លោះដែល N ជាចំនួនធំបំផុតដែលអាចធ្វើទៅបានក្រោមកំរិតដែលបានផ្តល់។