მინიმალური ოპერაციები X- ის Y გადასაყვანად  


Რთული ტური საშუალო
ხშირად ეკითხებიან Amazon ფაქტები ფანატიკა ფურკიტები JP Morgan მიტრა Samsung Spotify Square
სიგანე პირველი ძებნა Graph

პრობლემის განცხადება  

პრობლემა "მინიმალური ოპერაციები X- ის Y გადასაყვანად" აცხადებს, რომ გეძლევათ ორი რიცხვი X და Y, საჭიროა X- ის Y გადაკეთება შემდეგი ოპერაციების გამოყენებით:

საწყისი რიცხვი არის 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 დაფუძნებული ალგორითმი. ამის შემდეგ შეგვიძლია შევასრულოთ 2 ოპერაცია ან გავამრავლოთ 2-ზე ან გამოვაკლოთ 1-ზე. ამ გზით ჩვენ შეგვიძლია მივაღწიოთ ყველა რიცხვს, რომელთა გამომუშავებაც შეიძლება დაწყებული X რიცხვის გამოყენებით და მოცემული ორი ოპერაციის შესრულებით. თუ რომელიმე გამომუშავებული რიცხვი ტოლია შეყვანის ნომერი Y მიიღება. ამრიგად, ჩვენ უბრალოდ ვაბრუნებთ ნაბიჯების რაოდენობას Y რიცხვის წარმოსაქმნელად. ციფრების წარმოქმნისას მნიშვნელოვანია გავითვალისწინოთ შემდეგი პუნქტები:

  1. ჩვენ უგულებელყოფთ ნომერს BFS რიგში ჩასმა, თუ გამომუშავებული ნომერი არ აკმაყოფილებს შეზღუდვებს.
  2. თუ ამჟამად გენერირებული ნომერი უკვე გენერირებული იყო. ჩვენ უბრალოდ უგულებელყოფთ რიცხვს და არ ვამატებთ მას BFS რიგში. ჰეშების ნაკრები გამოიყენება აქამდე გენერირებული ციფრების დასაკვირვებლად.
  3. ჩვენ თვალყურს ვადევნებთ ოპერაციების რაოდენობას (დასახელებულ ცვლადში) დონე) შესრულებულია X რიცხვის საწყისი რიცხვის შესაქმნელად საჭირო ოპერაციების შესრულებით.
იხილეთ ასევე
შეამოწმეთ, არის თუ არა ორი კვანძი ერთ გზაზე

X ალგორითმი მინიმალური ოპერაციების მოსაძებნად  

  1. შექმნა მდგომ BFS ტრავერსისთვის და ჩასვით საწყისი რიცხვი X და ის დონის რიგში. საწყისი რიცხვის დონეა 0, რადგან X– ის X–ად გადასაყვანად საჭირო ოპერაციების რაოდენობაა 0.
  2. შექმნა HashSet რომ ინახავს აქამდე წარმოქმნილ რიცხვებს.
  3. შემდეგ დაიწყეთ BFS ტრავერსი.
  4. გამოყავით კვანძი რიგიდან, თუ კვანძის მნიშვნელობა ტოლია შეყვანის ნომრის Y. და ამ კვანძის დაბრუნების დონე (ოპერაციების მინიმალური რაოდენობა X- დან).
  5. სხვაგვარად, დაამატეთ ეს კვანძი ჩვენს ჰეშების ნაკრებში (მონიშნეთ როგორც მონახულებული).
  6. ახლა გამრავლებული popped კვანძის მნიშვნელობა 2-ზე და შეამოწმეთ არის თუ არა იგი ნაკრებში.
  7. თუ ასე გამომუშავებული რიცხვი არ არის ნაკრებში. ამრიგად, ჩასვით ნომერი რიგში მის დონესთან ერთად (ამ კვანძის დონე წარმოქმნილია = გამოჩენილი (მშობლის) კვანძის დონე + 1).
  8. შეამცირეთ ამოსული კვანძის მნიშვნელობა 1-ით და შეამოწმეთ არის თუ არა იგი ნაკრებში.
  9. თუ ასე გამომუშავებული რიცხვი არ არის ნაკრებში. ამრიგად, ჩასვით ნომერი რიგში მის დონესთან ერთად (ამ კვანძის დონე წარმოქმნილია = გამოჩენილი (მშობლის) კვანძის დონე + 1).
  10. გაიმეორეთ 3-9 ნაბიჯები, სანამ არ შეგვხვდება დაბრუნების მდგომარეობა ნაბიჯი 4.

ქვემოთ მოცემულია ალგორითმი:

მინიმალური ოპერაციები X- ის Y გადასაყვანად

კოდი  

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

Java კოდი, რომ იპოვოთ მინიმალური ოპერაციები X- ის Y გადასაყვანად

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 მოცემული შეზღუდვის ქვეშ ყველაზე დიდი რიცხვია.