我正在应对这个挑战:

A bot can do either of the 2 instructions:

• [F]orward: move ahead by +1 and double its speed
• [B]ack: Stop, change direction and reset its speed.

The initial speed is 1.

Given a distance, return a sequence that will satisfy it. The sequence can only have a maximum of 3 'B's. If a solution is not possible with 3 'B's then return empty string.

For example,

findSeq(2) -> FFBF (1+2-1)
findSeq(3) -> FF (1+2)
findSeq(4) -> FFFBFF (1+2+4 - (1+2))

这是我目前所拥有的:

def findSeq(dist):
    curr = 0
    seq = ""
    speed = 1
    mul = 1
    
    while (curr != dist):
        seq += 'F'
        curr += (speed*mul)
        speed *= 2
        
        if curr > dist and mul != -1:
            seq += 'B'
            mul = -1
            speed = 1

        elif curr < dist:
            mul = 1
        
        if curr == dist:
            return seq

        
        if seq.count('B') == 3 and curr != dist:
            return ''
    
    return seq

这适用于 findSeq(2)、findSeq(3) 和 findSeq(4)。但是，它开始中断 findSeq(5) ->(它给出 FFFBFFFBFF)

我不确定我错过了什么。

最佳答案

一些观察:一系列 n F 命令，使火车沿当前方向移动 2^n - 1。不失一般性，所有解的形式都是 F^k1 B F^k2 B F^k3 B F^k4，其中 k1, k2, k3, k4 >= 0 因为如果我们不移动火车，我们可以简单地设置一些 k 为 0。

这给出了问题的重述:给定 n，找到非负 k1、k2、k3、k4，使得 (2^k1 - 1) - (2^k2 - 1) + (2^k3 - 1) - (2^k4 - 1) = n。

1 在和中消去，所以你需要找到 2^k1 + 2^k3 - 2^k2 - 2^k4 = n。

如果n有N位，那么不失一般性，四个数中的每一个至多可以是N+1。

我确信有更聪明的方法，但只需搜索 (N+2)^4 种可能性就会产生 O((log n)^4) 的解决方案。

import itertools

def findSeq(n):
    N = max(1, n.bit_length())
    for k1, k2, k3, k4 in itertools.product(tuple(range(N+2)), repeat=4):
        if (1<<k1) - (1<<k2) + (1<<k3) - (1<<k4) == n:
            return 'B'.join('F' * x for x in (k1, k2, k3, k4))
    return ''

for i in range(100):
    print(i, findSeq(i))

@MattTimmermans 建议改进 O((logn)^2):枚举所有形式为 q = 2^k1 + 2^k3 的数字，然后查看 q-n 是否具有相同形式。

def findSeq2(n):
    N = max(1, n.bit_length())
    b2 = {(1<<k1)+(1<<k2): (k1, k2) for k1, k2 in itertools.product(tuple(range(N+2)), repeat=2)}
    for k1, k3 in b2.values():
        r = (1 << k1) + (1 << k3) - n
        if r in b2:
            k2, k4 = b2[r]
            return 'B'.join('F' * x for x in (k1, k2, k3, k4))      
    return ''

https://stackoverflow.com/questions/71532887/