Мінімальныя аперацыі для пераўтварэння X у Y


Узровень складанасці серада
Часта пытаюцца ў амазонка Факты Фанатыкі Фуркайты JP Morgan Мынтра Samsung Spotify Плошча
Шырыня Першы пошук Графік

Пастаноўка праблемы

Праблема «Мінімальныя аперацыі для пераўтварэння 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 у Y

  1. Стварыць чаргу для развароту BFS і ўстаўце пачатковы нумар X, і ён узроўню ў чаргу. Узровень зыходнага нумара роўны 0, паколькі колькасць аперацый, неабходных для пераўтварэння X у X, роўна 0.
  2. Стварыць HashSet у якім захоўваюцца атрыманыя да гэтага часу лічбы.
  3. Затым пачніце развод BFS.
  4. Вывядзіце вузел з чаргі, калі значэнне вузла роўна ўваходнаму нумару Y. І ўзровень вяртання (мінімальная колькасць аперацый з X) гэтага вузла.
  5. У іншым выпадку дадайце гэты вузел у наш хэш-набор (пазначыўшы яго як наведзены).
  6. Цяпер памножце выскоквае значэнне вузла на 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 - найбольшая колькасць, магчымае пры дадзеным абмежаванні.