BFS用于算术运算 [英] BFS for arithmetic operations
问题描述
以最少的操作将数字m转换为n。允许的操作为1减去2。
Convert a number m to n with minimum operations. The operations allowed were subtraction by 1 and multiplication by 2.
对于例如：4和6。答案为2。
第一个操作：-1-> 4 -1 =3。
第二个操作：*-> 3 * 2 = 6。
For Eg : 4 and 6. Answer is 2. 1st operation : -1 -> 4-1 = 3. 2nd operation : * -> 3 * 2 =6.
我正在为特定输入使用BFS方法（src = 26， dst = 5）需要很长时间。我是在做错什么吗？
I am using BFS approach for a particular input (src=26, dst= 5) it is taking long time. Am I doing something wrong?
from queue_class import queue
class node:
def __init__(self, value, level, parent):
self.level = level
self.value = value
self.parent = parent
def get_minimum_distance(src, target, q):
if src == target:
return 0
seen_list = []
data = node(src, 0, -1)
q.enqueue(data)
while not q.isempty():
data = q.dequeue()
if data == "sentinel":
break
if data.value == target:
# let's print what has got me here
while data.parent != -1:
print(data.value)
data = data.parent
return "finally reached"
if data.value in seen_list:
continue
seen_list.append(data.value)
# two operations are allowed i.e. -1 and multiplication by 2
# check if two numbers have opposite sign and if they have
# then check if the current number being subtracted from is a negative
# number. If it is, then there is no point subtracting 1 from that
if ((data.value ^ target) < 0 and data.value > 0) or (data.value ^ target >= 0):
q.enqueue(node(data.value - 1, data.level + 1, data))
q.enqueue(node(data.value * 2, data.level + 1, data))
return -1
q = queue(1 << 20)
print(get_minimum_distance(26, 5, q))
队列实现已完成此处。
感谢Paul：
下面是我在python中使用以下代码编写的代码，它可以完美地工作。
Thanks to Paul: Below is the code I came up with below code in python and it works perfectly.
def get_minimum_operations(src, dst):
step = 0
operations = []
if src == dst:
return 0
if dst < src:
return src-dst
while dst > src:
if dst & 0x01:
step += 1
operations.append("-1")
dst = (dst+1) >> 1
operations.append("*2")
step += 1
for i in range(0, src-dst):
operations.append("-1")
return (((src - dst) + step), operations)
src = 38
dst = 100
output = ""
(steps, operations) = get_minimum_operations(src, dst)
print(steps)
try:
while operations:
i = operations.pop()
if i == "*2":
if output == "":
output += "(" + str(src) + "*2" + ")"
else:
output = "(" + output + "*2" + ")"
if i == "-1":
if output == "":
output += "(" + str(src) + "-1" + ")"
else:
output = "(" + output + "-1" + ")"
except IndexError:
pass
print(output)
推荐答案
BFS由于指数增长（ 2 ^（n-1）到2 ^ n 进行尝试，其中n是所需步骤数）。而是尝试查找用于生成所需数字的逻辑规则。
BFS is not exactly an option here, due to the exponential growth (2 ^ (n - 1) to 2^n trys are performed, where n is the number of required steps). Instead try to find logic rules for generating the required number.
让 a 作为输入数字，而 b 应该产生的数字。
Let a be the input-number and b the number that should be produced.
有三种情况：
-
a == b，这种情况是微不足道的，只是为了完整性而列出 -
a> b，解决方案是a-b乘以-1 -
a< b：这是比较棘手的部分
a == b, this case is trivial and just listed for completenessa > b, the solution isa - btimes substracting by-1a < b: This is the more tricky part
最小的运算数需要最小的乘法数，并且减法。由于以下事实，减法可以轻松地最小化：（a-1）* 2 = a * 2 -2 。因此，通过在乘法之前简单地进行减法运算，就可以轻松地将减法运算的数目减少为2的幂。
由于我们只能进行减法运算和乘法运算，因此最小乘法数为 min n => a * 2 ^ n> = b 。
使用此事实，我们可以确定要减去的金额： s = b-2 ^ n * a 。
The smallest number of operations requires the minimum number of multiplications and substractions. Substractions can easily be minimized due to the following fact: (a - 1) * 2 = a * 2 - 2. Thus we can easily reduce the number of substractions by any number that is a power of 2 by simply substracting before multiplying.
Since we can only substract and multiply, the minimum number of multiplications is min n => a * 2 ^ n >= b.
Using this fact we can determine the amount to substract: s = b - 2 ^ n * a.
该实现在伪代码中如下所示（无法提供python代码）：
The implementation would look like this in pseudocode (can't provide python code):
//using the same variable-names as above in the description
minOp(int a , int b)
//find minimum number of multiplications
int n
for(n = 0 ; a << n < b ; n++)
noop
//find amount to substract
int s = (a << n) - b
for(int i = 0 ; i < n ; i++)
print("(")
print(a)
//calculate operations
while(n > 0)
//calculate number of times we need to substract here (minimization of substractions)
while(s >= 1 << n)
print(" - 1")
s -= 1 << n
print(")")
//divide by two
print(" * 2")
n -= 1
while(s >= 1 << n)
print(" - 1")
s -= 1 << n
print(" = ")
print(b)
此实现还涵盖了 a == b 的情况- n = 0 和 s = 0 -和 a> b -其中 n = 0 和 s = a-b 。
This implementation aswell covers the cases a == b - with n = 0 and s = 0 - and a > b - with n = 0 and s = a - b.
在上述Java实现中进行测试运行将产生以下输出：
A test-run in a java-implementation of the above would produce this output:
（（（4）* 2-1）* 2-1）* 2 = 26
(((4) * 2 - 1) * 2 - 1) * 2 = 26
上面计算的简化显示该算法背后的想法：
The simplification of the above calculation shows the idea behind this algorithm:
((4 * 2 - 1) * 2 - 1) * 2 = 26
(4 * 2 * 2 - 2 - 1) * 2 = 26
4 * 2 * 2 * 2 - 3 * 2 = 26
32 - 6 = 26
感谢@ user3386109的解释：
假定起始值为A，目标值为B。第一步是创建一个从B开始的目标值列表，然后除以2（如有必要，向上舍入）。例如，如果B为26，则目标值列表将为26、13、7、4、2、1。如果起始值A是这些目标值中的任何一个，则可以轻松地爬升至目标B（乘以2并在必要时减去1）。如果A不是这些值之一，则从A减去1开始，直到达到这些目标值之一。例如，如果A为6，则需要两个减法才能达到4，然后从4爬到26。如果A为12，则需要五个减法才能达到7，依此类推。显然，如果A大于B，那么您要做的就是减去1直到达到B
Thanks to @user3386109 for this explanation:
Assume that the start value is A, and the goal value is B. The first step is to create a list of target values starting at B, and proceeding by dividing by 2 (rounding up if necessary). For example, if B is 26, then the list of target values would be 26, 13, 7, 4, 2, 1. If the start value A is any of those target values, then you can easily climb to the goal B (by multiplying by 2 and subtracting 1 if necessary). If A is not one of those values, then you begin by subtracting 1 from A until you reach one of those target values. For example, if A is 6, then two subtractions are needed to reach 4, and then you climb from 4 to 26. If A is 12, five subtractions are needed to reach 7, and so on. Obviously, if A is larger than B, then all you do is subtract one until you reach B
这篇关于BFS用于算术运算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
