Минималне операције за претварање Кс у И  


Ниво тешкоће Средњи
Често питани у амазонка Фацтсет Фанатици Фоуркитес ЈП Морган Минтра самсунг Спотифи Квадрат
Претрага у ширину Графикон

Изјава о проблему  

Проблем „Минималне операције за претварање Кс у И“ наводи да су вам дата два броја Кс и И, потребно је претворити Кс у И помоћу следећих операција:

Почетни број је Кс. Следеће операције могу се извршити на Кс-у и бројевима који се генеришу као средњи резултат.

  1. помножи број са 2.
  2. смањите број за 1.

Откријте минимални број корака потребних за претварање Кс у И помоћу горе поменутих операција.

Ограничења: 0 <Кс, И <1000

Пример  

X = 3, Y = 11
3

Објашњење: 3 * 2 = 6, 6 * 2 = 12, 12-1 = 11 3 корака

X = 2, Y = 10
5

objašnjenje: 2 * 2 = 4, 4-1 = 3, 3 * 2 = 6, 6-1 = 5, 5 * 2 = 10 -> 5 корака

Приступ  

Примењујемо а БФС заснован алгоритам. Тада можемо да изведемо 2 операције или помножимо са 2 или одузмемо са 1. На тај начин можемо доћи до свих бројева који се могу генерисати помоћу почетног броја Кс и извршавања задатих двеју операција. Ако је било који генерисани број једнак улазном броју И, добија се. Стога једноставно враћамо број корака предузетих за генерисање броја И. Током генерисања бројева важно је имати на уму следеће тачке:

  1. Занемарујемо уметање броја у БФС ред ако генерисани број не задовољава ограничења.
  2. Ако је тренутно генерисани број већ генерисан раније. Једноставно игноришемо број не додајући га у БФС ред. Хасх сет се користи за праћење бројева који су до сада генерисани.
  3. Пратимо број операција (у променљивој названој ниво) изведено за генерисање броја од почетног броја Кс извођењем потребних операција.
Види такође
Проверите да ли су два чвора на истој путањи у дрвету

Алгоритам за проналажење минималних операција за претварање Кс у И  

  1. Креирање ред за БФС обилажење и убаците почетни број Кс и он је ниво у ред. Ниво почетног броја је 0 јер је број операција потребних за претварање Кс у Кс 0.
  2. Креирање ХасхСет која чува до сада генерисане бројеве.
  3. Затим започните БФС прелазак.
  4. Ископчајте чвор из реда ако је вредност чвора једнака улазном броју И. И ниво поврата (минимални број операција из Кс) овог чвора.
  5. Иначе, додајте овај чвор у наш хеш сет (означавајући га као посећен).
  6. Сада помножите вредност искоченог чвора са 2 и проверите да ли је присутна у скупу.
  7. Ако тако генерисани број није присутан у скупу. Стога уметните број у ред заједно са његовим нивоом (ниво генерисаног чвора = ниво искоченог (родитељског) чвора + 1).
  8. Смањите вредност искаченог чвора за 1 и проверите да ли је присутна у скупу.
  9. Ако тако генерисани број није присутан у скупу. Стога уметните број у ред заједно са његовим нивоом (ниво генерисаног чвора = ниво искоченог (родитељског) чвора + 1).
  10. Понављајте кораке 3-9 док не наиђемо на стање враћања у корак-4.

Алгоритам је приказан доле:

Минималне операције за претварање Кс у И

код  

Ц ++ код за проналажење минималних операција за претварање Кс у И

#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

Јава код за проналажење минималних операција за претварање Кс у И

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

Анализа сложености  

Сложеност времена

Тешко је коментарисати временску сложеност проналажења броја користећи горњи приступ. Али и даље можемо коментарисати најгору временску сложеност. У најгорем случају оно што се може догодити је да прођемо кроз све бројеве присутне под ограничењем. Иако пролазимо кроз све бројеве, не налазимо тражени број. Стога је временска сложеност НА), где је Н највећи могући елемент под задатим ограничењима.

Види такође
Преброј подређаје са истим парним и непарним елементима

Сложеност простора

Тешко је коментарисати и свемирску сложеност. Али слично ономе што смо радили са временском сложеношћу. Дакле, исто важи и за сложеност свемира. У најгорем случају, убацићемо све елементе у ред. Ово чини алгоритам који треба узети НА) простора, где је Н највећи број могућих под датим ограничењем.