将数字x转换为y所需的最小操作数-yiteyi-C++库

给定一个初始数x和两个操作，如下所示：

null

把这个数乘以2。
从数字中减去1。

任务是找出仅使用上述两种操作将数字x转换为y所需的最小操作数。我们可以多次应用这些操作。限制条件： 1<=x，y<=1000 例子：

Input : x = 4, y = 7Output : 2We can transform x into y using followingtwo operations.1. 4*2  = 82. 8-1  = 7Input  : x = 2, y = 5Output : 4We can transform x into y using followingfour operations.1. 2*2  = 42. 4-1   = 33. 3*2  = 64. 6-1   = 5Answer = 4Note that other sequences of two operations would take more operations.

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

这个想法是使用 BFS 为了这个。我们运行一个BFS，通过乘以2减去1来创建节点，这样我们就可以得到所有可能的从起始数到达的数。要点： 1）当我们从一个数字中减去1，如果它变为<0，即负，则没有理由从中创建下一个节点（根据输入约束，数字x和y为正）。 2）此外，如果我们已经创建了一个数字，那么就没有理由再创建一次。i、 e.我们维持一个访问阵列。

C++

                         // C++ program to find minimum number of steps needed                       
                         // to convert a number x into y with two operations                       
                         // allowed : (1) multiplication with 2 (2) subtraction                       
                         // with 1.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // A node of BFS traversal                       
                         struct                                     node {                       
                                                 int                                     val;                       
                                                 int                                     level;                       
                         };                       
           
                         // Returns minimum number of operations                       
                         // needed to convert x into y using BFS                       
                         int                                     minOperations(                                     int                                     x,                                     int                                     y)                       
                         {                       
                                                 // To keep track of visited numbers                       
                                                 // in BFS.                       
                                                 set<                                     int                                     > visit;                       
           
                                                 // Create a queue and enqueue x into it.                       
                                                 queue<node> q;                       
                                                 node n = { x, 0 };                       
                                                 q.push(n);                       
           
                                                 // Do BFS starting from x                       
                                                 while                                     (!q.empty()) {                       
                                                 // Remove an item from queue                       
                                                 node t = q.front();                       
                                                 q.pop();                       
           
                                                 // If the removed item is target                       
                                                 // number y, return its level                       
                                                 if                                     (t.val == y)                       
                                                 return                                     t.level;                       
           
                                                 // Mark dequeued number as visited                       
                                                 visit.insert(t.val);                       
           
                                                 // If we can reach y in one more step                       
                                                 if                                     (t.val * 2 == y || t.val - 1 == y)                       
                                                 return                                     t.level + 1;                       
           
                                                 // Insert children of t if not visited                       
                                                 // already                       
                                                 if                                     (visit.find(t.val * 2) == visit.end()) {                       
                                                 n.val = t.val * 2;                       
                                                 n.level = t.level + 1;                       
                                                 q.push(n);                       
                                                 }                       
                                                 if                                     (t.val - 1 >= 0                       
                                                 && visit.find(t.val - 1) == visit.end()) {                       
                                                 n.val = t.val - 1;                       
                                                 n.level = t.level + 1;                       
                                                 q.push(n);                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     x = 4, y = 7;                       
                                                 cout << minOperations(x, y);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find minimum                       
                         // number of steps needed to                       
                         // convert a number x into y                       
                         // with two operations allowed :                       
                         // (1) multiplication with 2                       
                         // (2) subtraction with 1.                       
           
                         import                                     java.util.HashSet;                       
                         import                                     java.util.LinkedList;                       
                         import                                     java.util.Set;                       
           
                         class                                     GFG {                       
                                                 int                                     val;                       
                                                 int                                     steps;                       
           
                                                 public                                     GFG(                                     int                                     val,                                     int                                     steps)                       
                                                 {                       
                                                 this                                     .val = val;                       
                                                 this                                     .steps = steps;                       
                                                 }                       
                         }                       
           
                         public                                     class                                     GeeksForGeeks {                       
                                                 private                                     static                                     int                                     minOperations(                                     int                                     src,                                     int                                     target)                       
                                                 {                       
           
                                                 Set<GFG> visited =                                     new                                     HashSet<>(                                     1000                                     );                       
                                                 LinkedList<GFG> queue =                                     new                                     LinkedList<GFG>();                       
           
                                                 GFG node =                                     new                                     GFG(src,                                     0                                     );                       
           
                                                 queue.offer(node);                       
                                                 visited.add(node);                       
           
                                                 while                                     (!queue.isEmpty()) {                       
                                                 GFG temp = queue.poll();                       
                                                 visited.add(temp);                       
           
                                                 if                                     (temp.val == target) {                       
                                                 return                                     temp.steps;                       
                                                 }                       
           
                                                 int                                     mul = temp.val *                                     2                                     ;                       
                                                 int                                     sub = temp.val -                                     1                                     ;                       
           
                                                 // given constraints                       
                                                 if                                     (mul >                                     0                                     && mul <                                     1000                                     ) {                       
                                                 GFG nodeMul =                                     new                                     GFG(mul, temp.steps +                                     1                                     );                       
                                                 queue.offer(nodeMul);                       
                                                 }                       
                                                 if                                     (sub >                                     0                                     && sub <                                     1000                                     ) {                       
                                                 GFG nodeSub =                                     new                                     GFG(sub, temp.steps +                                     1                                     );                       
                                                 queue.offer(nodeSub);                       
                                                 }                       
                                                 }                       
                                                 return                                     -                                     1                                     ;                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 // int x = 2, y = 5;                       
                                                 int                                     x =                                     4                                     , y =                                     7                                     ;                       
                                                 GFG src =                                     new                                     GFG(x, y);                       
                                                 System.out.println(minOperations(x, y));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Rahul                       

Python3

                         # Python3 program to find minimum number of                       
                         # steps needed to convert a number x into y                       
                         # with two operations allowed :                       
                         # (1) multiplication with 2                       
                         # (2) subtraction with 1.                       
                         import                                     queue                       
           
                         # A node of BFS traversal                       
           
           
                         class                                     node:                       
                                                 def                                     __init__(                                     self                                     , val, level):                       
                                                 self                                     .val                                     =                                     val                       
                                                 self                                     .level                                     =                                     level                       
           
                         # Returns minimum number of operations                       
                         # needed to convert x into y using BFS                       
           
           
                         def                                     minOperations(x, y):                       
           
                                                 # To keep track of visited numbers                       
                                                 # in BFS.                       
                                                 visit                                     =                                     set                                     ()                       
           
                                                 # Create a queue and enqueue x into it.                       
                                                 q                                     =                                     queue.Queue()                       
                                                 n                                     =                                     node(x,                                     0                                     )                       
                                                 q.put(n)                       
           
                                                 # Do BFS starting from x                       
                                                 while                                     (                                     not                                     q.empty()):                       
           
                                                 # Remove an item from queue                       
                                                 t                                     =                                     q.get()                       
           
                                                 # If the removed item is target                       
                                                 # number y, return its level                       
                                                 if                                     (t.val                                     =                                     =                                     y):                       
                                                 return                                     t.level                       
           
                                                 # Mark dequeued number as visited                       
                                                 visit.add(t.val)                       
           
                                                 # If we can reach y in one more step                       
                                                 if                                     (t.val                                     *                                     2                                     =                                     =                                     y                                     or                                     t.val                                     -                                     1                                     =                                     =                                     y):                       
                                                 return                                     t.level                                     +                                     1                       
           
                                                 # Insert children of t if not visited                       
                                                 # already                       
                                                 if                                     (t.val                                     *                                     2                                     not                                     in                                     visit):                       
                                                 n.val                                     =                                     t.val                                     *                                     2                       
                                                 n.level                                     =                                     t.level                                     +                                     1                       
                                                 q.put(n)                       
                                                 if                                     (t.val                                     -                                     1                                     >                                     =                                     0                                     and                                     t.val                                     -                                     1                                     not                                     in                                     visit):                       
                                                 n.val                                     =                                     t.val                                     -                                     1                       
                                                 n.level                                     =                                     t.level                                     +                                     1                       
                                                 q.put(n)                       
           
           
                         # Driver code                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
           
                                                 x                                     =                                     4                       
                                                 y                                     =                                     7                       
                                                 print                                     (minOperations(x, y))                       
           
                         # This code is contributed by PranchalK                       

C#

                         // C# program to find minimum                       
                         // number of steps needed to                       
                         // convert a number x into y                       
                         // with two operations allowed :                       
                         // (1) multiplication with 2                       
                         // (2) subtraction with 1.                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
           
                         public                                     class                                     GFG {                       
                                                 public                                     int                                     val;                       
                                                 public                                     int                                     steps;                       
           
                                                 public                                     GFG(                                     int                                     val,                                     int                                     steps)                       
                                                 {                       
                                                 this                                     .val = val;                       
                                                 this                                     .steps = steps;                       
                                                 }                       
                         }                       
           
                         public                                     class                                     GeeksForGeeks {                       
                                                 private                                     static                                     int                                     minOperations(                                     int                                     src,                                     int                                     target)                       
                                                 {                       
           
                                                 HashSet<GFG> visited =                                     new                                     HashSet<GFG>(1000);                       
                                                 List<GFG> queue =                                     new                                     List<GFG>();                       
           
                                                 GFG node =                                     new                                     GFG(src, 0);                       
           
                                                 queue.Add(node);                       
                                                 visited.Add(node);                       
           
                                                 while                                     (queue.Count != 0) {                       
                                                 GFG temp = queue[0];                       
                                                 queue.RemoveAt(0);                       
                                                 visited.Add(temp);                       
           
                                                 if                                     (temp.val == target) {                       
                                                 return                                     temp.steps;                       
                                                 }                       
           
                                                 int                                     mul = temp.val * 2;                       
                                                 int                                     sub = temp.val - 1;                       
           
                                                 // given constraints                       
                                                 if                                     (mul > 0 && mul < 1000) {                       
                                                 GFG nodeMul =                                     new                                     GFG(mul, temp.steps + 1);                       
                                                 queue.Add(nodeMul);                       
                                                 }                       
                                                 if                                     (sub > 0 && sub < 1000) {                       
                                                 GFG nodeSub =                                     new                                     GFG(sub, temp.steps + 1);                       
                                                 queue.Add(nodeSub);                       
                                                 }                       
                                                 }                       
                                                 return                                     -1;                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main(String[] args)                       
                                                 {                       
           
                                                 // int x = 2, y = 5;                       
                                                 int                                     x = 4, y = 7;                       
                                                 GFG src =                                     new                                     GFG(x, y);                       
                                                 Console.WriteLine(minOperations(x, y));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by aashish1995                       

输出：

本文由 Vipin Khushu .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以写一篇文章，然后将文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

优化方案

在第二种方法中，我们将检查数字的最低位，并根据该位的值做出决定。

我们将把y转换成x，而不是将x转换成y，并将反转操作，这些操作的次数与将x转换成y的次数相同。

因此，y的反向操作将是：

将数字除以2
将数字增加1

C++14

                         #include <iostream>                       
                         using                                     namespace                                     std;                       
           
                         int                                     min_operations(                                     int                                     x,                                     int                                     y) {                       
           
                                                 // If both are equal then return 0                       
                                                 if                                     (x == y)                       
                                                 return                                     0;                       
           
                                                 // Check if conversion is possible or not                       
                                                 if                                     (x <= 0 && y > 0)                       
                                                 return                                     -1;                       
           
                                                 // If x > y then we can just increase y by 1                       
                                                 // Therefore return the number of increments required                       
                                                 if                                     (x > y)                       
                                                 return                                     x - y;                       
           
                                                 // If last bit is odd                       
                                                 // then increment y so that we can make it even                       
                                                 if                                     (y & 1)                       
                                                 return                                     1 + min_operations(x, y + 1);                       
           
                                                 // If y is even then divide it by 2 to make it closer to                       
                                                 // x                       
                                                 else                       
                                                 return                                     1 + min_operations(x, y / 2);                       
                         }                       
           
                         // Driver code                       
                         signed                                     main() {                       
                                                 cout << min_operations(4, 7) << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         /*package whatever //do not write package name here */                       
                         import                                     java.io.*;                       
           
                         class                                     GFG                       
                         {                       
                                                 static                                     int                                     minOperations(                                     int                                     x,                                     int                                     y)                       
                                                 {                       
                                   
                                                 // If both are equal then return 0                       
                                                 if                                     (x == y)                       
                                                 return                                     0                                     ;                       
           
                                                 // Check if conversion is possible or not                       
                                                 if                                     (x <=                                     0                                     && y >                                     0                                     )                       
                                                 return                                     -                                     1                                     ;                       
           
                                                 // If x > y then we can just increase y by 1                       
                                                 // Therefore return the number of increments                       
                                                 // required                       
                                                 if                                     (x > y)                       
                                                 return                                     x - y;                       
           
                                                 // If last bit is odd                       
                                                 // then increment y so that we can make it even                       
                                                 if                                     (y %                                     2                                     !=                                     0                                     )                       
                                                 return                                     1                                     + minOperations(x, y +                                     1                                     );                       
           
                                                 // If y is even then divide it by 2 to make it                       
                                                 // closer to x                       
                                                 else                       
                                                 return                                     1                                     + minOperations(x, y /                                     2                                     );                       
                                                 }                       
           
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 System.out.println(minOperations(                                     4                                     ,                                     7                                     ));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Shobhit Yadav                       

Python3

                         def                                     min_operations(x, y):                       
                                                 # If both are equal then return 0                       
                                                 if                                     x                                     =                                     =                                     y:                       
                                                 return                                     0                       
           
                                                 # Check if conversion is possible or not                       
                                                 if                                     x <                                     =                                     0                                     and                                     y >                                     0                                     :                       
                                                 return                                     -                                     1                       
           
                                                 # If x > y then we can just increase y by 1                       
                                                 # Therefore return the number of increments required                       
                                                 if                                     x > y:                       
                                                 return                                     a                                     -                                     b                       
           
                                                 # If last bit is odd                       
                                                 # then increment y so that we can make it even                       
                                                 if                                     y &                                     1                                     =                                     =                                     1                                     :                       
                                                 return                                     1                                     +                                     min_operations(x, y                                     +                                     1                                     )                       
           
                                                 # If y is even then divide it by 2 to make it closer to x                       
                                                 else                                     :                       
                                                 return                                     1                                     +                                     min_operations(x, y                                     /                                     /                                     2                                     )                       
           
           
                         # Driver code                       
                         print                                     (min_operations(                                     4                                     ,                                     7                                     ))                       

C#

                         using                                     System;                       
                         class                                     GFG {                       
           
                                                 static                                     int                                     min_operations(                                     int                                     x,                                     int                                     y)                       
                                                 {                       
           
                                                 // If both are equal then return 0                       
                                                 if                                     (x == y)                       
                                                 return                                     0;                       
           
                                                 // Check if conversion is possible or not                       
                                                 if                                     (x <= 0 && y > 0)                       
                                                 return                                     -1;                       
           
                                                 // If x > y then we can just increase y by 1                       
                                                 // Therefore return the number of increments                       
                                                 // required                       
                                                 if                                     (x > y)                       
                                                 return                                     x - y;                       
           
                                                 // If last bit is odd                       
                                                 // then increment y so that we can make it even                       
                                                 if                                     (y % 2 == 1)                       
                                                 return                                     1 + min_operations(x, y + 1);                       
           
                                                 // If y is even then divide it by 2 to make it                       
                                                 // closer to                       
                                                 // x                       
                                                 else                       
                                                 return                                     1 + min_operations(x, y / 2);                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     int                                     Main()                       
                                                 {                       
                                                 Console.WriteLine(min_operations(4, 7));                       
                                                 return                                     0;                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Taranpreet                       

输出

优化的解决方案由 燃烧炸药。 如果你喜欢GeekSforgeks，并且想贡献自己的力量，你也可以写一篇文章，然后把你的文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章