X ကို Y ပြောင်းရန်အနည်းဆုံးစစ်ဆင်ရေးများ


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် အမေဇုံ အချက်အလက် ဝါသနာရှင်များ လေးကစ် JP Morgan Myntra Samsung Spotify ရင်ပြင်
အနံပထမရှာဖွေရေး သရုပ်ပြဇယား

ပြProbleနာဖော်ပြချက်

ပြXနာက“ အနိမ့်ဆုံး X မှ Y သို့ပြောင်းရန်” ဟူသောပြstatesနာကသင့်အား X နှင့် Y နှစ်ခုပေးထားပြီး၊ X ကို Y သို့ပြောင်းလဲရန်အောက်ပါလုပ်ဆောင်မှုများကိုဖော်ပြသည်။

Starting နံပါတ်သည် X ဖြစ်သည်။ အောက်ဖော်ပြပါစစ်ဆင်ရေးများကို X နှင့်အလယ်အလတ်ရလဒ်အဖြစ်ထုတ်လုပ်ထားသောနံပါတ်များပေါ်တွင်လုပ်ဆောင်နိုင်သည်။

  1. နံပါတ်ကို 2 နဲ့မြှောက်ပါ။
  2. 1 အားဖြင့်အရေအတွက်ကလျော့နည်းသွားသည်။

အထက်တွင်ဖော်ပြခဲ့သောစစ်ဆင်ရေးများကို အသုံးပြု၍ X ကို Y အဖြစ်ပြောင်းလဲရန်လိုအပ်သောအနည်းဆုံးအဆင့်များကိုရှာပါ။

ကန့်သတ်ချက်များ: 0 င် <X ကို, Y ကို <1000

နမူနာ

X = 3, Y = 11
3

ရှင်းလင်းချက်: 3 * 2 = 6, 6 * 2 = 12, 12-1 = 11 3 ခြေလှမ်းများ

X = 2, Y = 10
5

ရှင်းလင်းချက်: 2 * 2 = 4, 4-1 = 3, 3 * 2 = 6, 6-1 = 5, 5 * 2 = 10 -> 5 အဆင့်

ချဉ်းကပ်နည်း

ကျွန်ုပ်တို့လျှောက်ထားသည် BFS အခြေခံ algorithm ကို။ သို့ဖြစ်လျှင်ကျွန်ုပ်တို့သည် ၂ ခုကိုမြှောက်ခြင်းသို့မဟုတ် ၁ ဖြင့်နုတ်ခြင်းနှစ်ခုကိုလုပ်ဆောင်နိုင်သည်။ ဤနည်းအားဖြင့်ကျွန်ုပ်တို့သည်နံပါတ် X ကို အသုံးပြု၍ ထုတ်လုပ်နိုင်သောနံပါတ်များကိုရောက်ရှိပြီးပေးထားသောစစ်ဆင်ရေးနှစ်ခုကိုလုပ်ဆောင်နိုင်သည်။ မဆိုထုတ်လုပ်ပြီးနံပါတ် input ကိုအရေအတွက်က Y နှင့်ညီမျှသည်ဆိုပါက။ ထို့ကြောင့်ကျွန်ုပ်တို့သည် Y နံပါတ်ကိုထုတ်လုပ်ရန်အတွက်ပြုလုပ်သောအဆင့်များကိုပြန်ပို့ခြင်းသာဖြစ်သည်။ နံပါတ်များကိုထုတ်လုပ်နေစဉ်အောက်ပါအချက်များကိုစိတ်စွဲမှတ်ထားရန်အရေးကြီးသည်။

  1. ထုတ်လုပ်ထားသောနံပါတ်သည်ကန့်သတ်ချက်များကိုမကျေနပ်လျှင် BFS တန်းထဲသို့ထည့်ခြင်းမှနံပါတ်ကိုကျွန်ုပ်တို့လျစ်လျူရှုထားသည်။
  2. လက်ရှိထုတ်ပေးနံပါတ်ပြီးသားမတိုင်မီထုတ်လုပ်ပြီးခဲ့လျှင်။ ကျွန်ုပ်တို့သည်နံပါတ်ကိုလျစ်လျူရှုရုံဖြင့် BFS တန်းထဲသို့ထပ်မထည့်ပါ။ ယခုအချိန်အထိထုတ်ပေးသောနံပါတ်များကိုခြေရာခံရန် hash set ကိုအသုံးပြုသည်။
  3. ကျွန်ုပ်တို့သည်လုပ်ငန်းဆောင်ရွက်မှုအရေအတွက်ကိုအမည်ပေးသည် အဆင့်) လိုအပ်သောစစ်ဆင်ရေးဖျော်ဖြေခြင်းအားဖြင့်အရေအတွက်က X ကနေနံပါတ် generate မှဖျော်ဖြေခဲ့ပါတယ်။

X ကို Y သို့ပြောင်းလဲရန်အနည်းဆုံးသော Operations ကိုရှာဖွေရန် Algorithm ကို

  1. တစ်ဦး Create ဆံပင်ကြိုး BFS ဖြတ်သန်းခြင်းနှင့်စတင်နံပါတ် X ကိုထည့်သွင်းခြင်းနှင့်၎င်းသည်တန်းစီထဲသို့အဆင့်ဆင့်ခြင်း X သို့ X သို့ပြောင်းလဲရန်လိုအပ်သောစစ်ဆင်ရေးအရေအတွက်သည် ၀ ဖြစ်သည်။
  2. တစ်ဦး Create HashSet ကြောင်းယခုအချိန်အထိထုတ်ပေးနံပါတ်များကိုသိုလှောင်ပါသည်။
  3. ထိုအခါ BFS ဖြတ်သန်းစတင်ပါ။
  4. အကယ်၍ node တန်ဖိုးသည် input နံပါတ် Y နှင့်ညီမျှပါကဤ node ၏အနိမ့်ဆုံးအဆင့် (X မှလုပ်ဆောင်မှုအနည်းဆုံး) ထပ်မံပါကတန်းစီမှ node တစ်ခုပေါ်လာပါ။
  5. အခြားအရာများ၊ ဤ node ကိုကျွန်ုပ်တို့၏ hash အစုထဲထည့်ပါ။
  6. ပြီးရင် popped node value ကို 2 နဲ့မြှောက်ပြီး set ထဲမှာရှိသလားဆိုတာစစ်ဆေးပါ။
  7. ထုတ်လုပ်လိုက်တဲ့နံပါတ်အစု၌ပစ္စုပ္ပန်မဟုတ်ပါဘူးလျှင်။ ထို့ကြောင့်ကိန်းဂဏန်းအား၎င်းအဆင့်နှင့်၎င်းအဆင့် (ဒီ node ထုတ်လုပ်မှုအဆင့် = popped (parent) node + 1) နှင့်အတူတန်းထဲသို့ထည့်ပါ။
  8. popped node တန်ဖိုးကို 1 ဖြင့်လျှော့ချပြီး၎င်းသည်အစုထဲရှိသလားဆိုတာစစ်ဆေးပါ။
  9. ထုတ်လုပ်လိုက်တဲ့နံပါတ်အစု၌ပစ္စုပ္ပန်မဟုတ်ပါဘူးလျှင်။ ထို့ကြောင့်ကိန်းဂဏန်းအား၎င်းအဆင့်နှင့်၎င်းအဆင့် (ဒီ node ထုတ်လုပ်မှုအဆင့် = popped (parent) node + 1) နှင့်အတူတန်းထဲသို့ထည့်ပါ။
  10. ကျနော်တို့ပြန်လာခွအေနအေတှေ့ဆုံသည်အထိအဆင့်ဆင့် 3-9 ကြားမှာထပ်လုပ်ပါ အဆင့် -၄ ။

Algorithm ကိုအောက်တွင်ဖော်ပြထားသည်။

X ကို Y ပြောင်းရန်အနည်းဆုံးစစ်ဆင်ရေးများ

ကုဒ်

X ကို Y သို့ပြောင်းလဲရန်အနည်းဆုံးသော Operations များကိုရှာရန် C ++ ကုဒ်

#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 သို့ Y သို့ပြောင်းလဲရန်အနည်းဆုံးသော Operations ကိုရှာဖွေရန် Java Code ရှိသည်

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

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အထက်ပါချဉ်းကပ်နည်းကို အသုံးပြု၍ နံပါတ်တစ်ခုရှာဖွေရန်အချိန်ရှုပ်ထွေးမှုနှင့် ပတ်သက်၍ မှတ်ချက်ပေးရန်ခဲယဉ်းသည်။ ဒါပေမယ့်ကျနော်တို့အဆိုးဆုံးအချိန်ရှုပ်ထွေးအပေါ်မှတ်ချက်ပေးရန်နိုင်ပါတယ်။ အဆိုးဆုံးအခြေအနေမှာဘာဖြစ်နိုင်တယ်ဆိုတာကန့်သတ်ချက်အောက်မှာရှိနေတဲ့ကိန်းဂဏန်းအားလုံးကိုကျွန်တော်တို့ဖြတ်သန်းသွားတယ်။ ကိန်းဂဏန်းအားလုံးကိုဖြတ်ပြီးတောင်မှကျွန်ုပ်တို့လိုအပ်သောနံပါတ်ကိုမတွေ့ပါ။ ထို့ကြောင့်အချိန်ရှုပ်ထွေးသည် အို (N), ဘယ်မှာ N ကိုပေးထားသောသတ်အောက်မှာဖြစ်နိုင်သမျှအကြီးဆုံးဒြပ်စင်သည်။

အာကာသရှုပ်ထွေးမှု

အာကာသရှုပ်ထွေးမှုကိုမှတ်ချက်ပေးရန်လည်းခက်ခဲသည်။ ဒါပေမယ့်ကျနော်တို့အချိန်ရှုပ်ထွေးနှင့်အတူလုပ်ခဲ့တယ်ဆင်တူ။ ဒီတော့အာကာသရှုပ်ထွေးမှုအတွက်လည်းအတူတူပဲ။ အဆိုးဆုံးအခြေအနေမှာ element အားလုံးကိုအားလုံးအားတန်းထဲသို့ထည့်ပါလိမ့်မည်။ ဒါကယူ algorithm ကိုမှန်ကန်စေသည် အို (N) ပေးထားသောကန့်သတ်ချက်အောက်တွင် N သည်အကြီးဆုံးအရေအတွက်ရှိသည့်နေရာ။