问题
燃油喷射完美
指挥官Lambda请求您帮助改进自动 量子反物质燃料喷射系统为她的 LAMBCHOP 世界末日 装置。这是一个很好的机会，让您仔细看看 羊排 - 也许在你做的时候偷偷溜进一些破坏活动 - 所以你很高兴地接受了这份工作。
量子反物质燃料呈小颗粒状，很方便 由于 LAMBCHOP 的许多运动部件都需要喂食燃料 一次一个颗粒。然而，小黄人将颗粒大量倾倒到 进油口。您需要找出最有效的排序方式和 一次将颗粒向下移动到单个颗粒。
燃料控制机制有三种操作：
添加一个燃料颗粒 删除一个燃料颗粒 将整个组划分为 燃料颗粒减少 2(由于释放的破坏性能量时 量子反物质颗粒被切成两半，安全控制将 仅当有偶数个颗粒时才允许发生这种情况(写入 一个名为 answer(n( 的函数，它将正整数作为字符串 并返回转换 颗粒数为1.进油控制面板只能显示 一个长达 309 位的数字，因此不会有更多的颗粒 比你可以用那么多数字来表达。
例如：答案(4(返回2：4 -> 2 -> 1答案(15(返回5：15 -> 16 -> 8 -> 4 -> 2 -> 1
测试用例
输入：(字符串(n = "4" 输出：(整数(2
输入：(字符串(n = "15" 输出：(整数(5
这是我的解决方案：
import math
import decimal
def answer(n):
n = long(n)
if n <= 1 or n >= long('9' * 309):
return 0
# 1. Find closest power of 2
round_threshold_adjust = math.log(3,2)- (1.5)
log_n = math.log(n, 2)
power = log_n - round_threshold_adjust
# Round power down if X.50000. If n is equally between two powers of 2,
# choose the lower power of 2. E.g. For 6, choose, 4 not 8
power2 = long(decimal.Decimal(power).quantize(0, decimal.ROUND_HALF_DOWN))
# 2. Calculate the difference, add to iterations
# 3. Take log 2 of that, add that to iteration
iters = abs(n - 2**power) + power
return(iters)
我的解决方案目前通过了 10 个测试用例中的 3 个。我相信其他测试用例是边缘情况。你能给我一些关于如何识别我的代码失败的地方的指示吗？(我无权访问测试用例(
以下是我尝试过的一些测试用例：
assert answer(15) == 5
assert answer(4) == 2
assert answer(3) == 2
assert answer(2) == 1
assert answer(6) == 4
assert answer(7) == 4
assert answer(10) == 5
assert answer(1024) == 10
assert answer(1025) == 11
assert answer(1026) == 12
assert answer(1027) == 13
assert answer(768) == 256 + 9
如果我理解正确，给定 768 个颗粒，您需要 256+9 个步骤才能将其转换为 1 个颗粒？
我可以通过 10 个步骤完成：
- 将 768 除以 2
- 再重复 7 次 ->你最终得到 3 个颗粒
- 减去 1
- 减去 1
我认为你的第一步，加/减直到你落在 2 的幂，不是最快的解决方案。
我不确定如何编写更好的解决方案，但也许这为您指明了正确的方向。直观地说，我的下一步是查看数字的二进制表示形式，并将允许的操作转换为该表示形式。这可能会简化正确算法的创建。
这是我的解决方案：
#!/usr/bin/python
#fuel-injection-perfection
#Program to count the naximum number of operations needed to recursively divide a number by 2. Add or subtract 1 where needed.
#V2 - Initial version was done using recursion but failed for large numbers due to python limitation & performance issues.
cnt=0
def divide(x):
global cnt
while(x>1):
if (x & 1==0):
#Dividing even number by two by shifting binary digits one step to the right.
x=x>>1
else:
a=x+1
b=x-1
#counters ac & bc will be used to count trailing 0s
ac=bc=0
#count trailing 0's for x+1
while(a & 1==0):
a=a>>1
ac+=1
#count trailing 0's for x-1
while(b & 1==0):
b=b>>1
bc+=1
#go with x+1 if it has more trailing 0s in binary format. Exception is number 3 as b10 can be divided in less steps than b100.
#edge case 3 identified by manually testing numbers 1-10.
if (ac>bc and x!=3):
x+=1
else:
x-=1
cnt+=1
def solution(n):
global cnt
n=int(n)
divide(n)
return cnt
这是Python3的答案。我创建了拖曳函数，一个加 1，另一个减 1，然后比较哪个以最少的步骤给出最佳答案。
#function for the adding 1 to the odd number
def np(n):
c = 0
while n > 1:
if n%2 == 0:
n = n/2
c += 1
else:
n += 1
c += 1
return c
#function for the subtracting 1 to the odd number
def nn(n):
c = 0
while n > 1:
if n%2 == 0:
n = n/2
c += 1
else:
n -= 1
c += 1
return c
#Solution function
def solution(n):
n = int(n)
if np(n) > nn(n):
return nn(n)
else:
return np(n)
希望这有效，干杯。