检查是否有办法在任意范围 F 内从 S 点到 G 点

Question

给定 1 到 F 的任意范围和起点 S 以及终点 G 这样我们唯一可以走的方向是 L 左步和 R 右步（也是任意的），创建一个通用解决方案，它将 return 从 S 到 R 所需的步数如果可能 否则return not possible.

您被限制在 [1, F] 范围内，这意味着您不能移动 L 或 R 步，如果下一步移动将大于 F 或小于1

示例：

F = 100
S = 2
G = 1
L = 0
R = 1

Output: not possible

F = 10
S = 1
G = 10
L = 1
R = 2

Output: 6 
Explanation: [1 -> 3(R) -> 5(R) -> 7(R) -> 9(R) -> 8(L) -> 10(R)]

我在 class 中遇到过这个问题，我们当前的主题是 二分搜索 和 分而治之 .这是我的方法，但这并没有解决一个隐藏的案例。

F = int(input())
S = int(input())
G = int(input())
L = int(input())
R = int(input())
count = 0

while S != G:
    dist = abs(S - G)          # Takes the current distance from S to G
    
    if S > G:
        if S-L > 0:
            S -= L
            count += 1
        else:
            S += R
            count += 1

    else:
        if S+R <= F:
            S += R
            count += 1
        else:
            S -= L
            count += 1

    if dist == abs(S - G):     # If distance doesn't change after trying
        print("not possible")  # a move, conclude that it is not possible.
        break                  

if S == G: print(count)

Answer 1

如果距离没有改变并不意味着它不可能，你可以直接跳过这个点并以相同的距离到达另一边，想象一下 L=2，R=1，S =3，G=2，你从距离目标1开始，向左跳（仍然是距离1）然后向右跳并获胜。您需要检查的是您是否进入了一个循环并最终到达了您之前已经尝试过的位置。您可以跟踪这些位置（比如在一个集合中）或提前做一些数学运算并计算出在您确定循环之前需要多少 Ls 和 Rs（可能不打算计算出来）。

Answer 2

F=int(input())
S=int(input())
G=int(input())
L=int(input())
R=int(input())


L*=-1
Fl=1-L
Fr=F-R
h0=set()
n=0
while True:
    if   S<G:
        S+= R if S<=Fr else L
    elif G<S:
        S+= L if Fl<=S else R
    else:
        print(n)
        break
    if S in h0:
        print('not possible')
        break

    h0.add(S)
    n+=1

Answer 3

数学上这个问题意味着我们正在寻找以下方程的整数解（对于 x 和 y）：

x * R - y * L = G - S

我们可以先创建一个函数来快速检查是否有解决方案：

def path(S, G, F, L, R):
    x=0
    while True:
        y = (x * R - G + S) / L
        if y>=0 and int(y)==y:
            return(x,y)
        else:
            x+=1

如果有解决方案，这将起作用，但如果没有，则无效。从数学上可以证明，当L除R而不除G-S时无解。证明如下：

如果 R mod L =0 (L 除 R) (G - S)/L != 0 (L不除G-S)

然后将整个方程 (x * R - y * L = G - S) 除以 L，我们得到：

x * R/L - y = (G - S)/L <=>

y= (x * R/L) - (G - S)/L

现在，对于 x mod 1 =0（x 整数），我们需要 y mod 1 = 0（意味着 y 是整数）。使用常见的 modulo 操作，我们采取：

y mod 1 = [(x * R/L) - (G - S)/L] mod 1 =

[(x * R/L) mod 1 - ((G - S)/L) mod 1] mod 1 =

[(x mod 1 * (R/L) mod 1) mod 1 - ((G - S)/L) mod 1] mod 1 =

[(x mod 1 * 0) mod 1 - ((G - S)/L) mod 1] mod 1 =

[((G - S)/L) mod 1] mod 1

如果L不除G-S这就不能为0，这最终意味着没有一对整数x，y可以满足原始条件。

从程序上讲，这意味着我们的代码需要添加以下内容：

def path(S, G, F, L, R):
        if R%L==0 and (G-S)%L != 0 :
            return 'No solutions'
        x=0
        while True:
            y = (x * R - G + S) / L
            if y>=0 and int(y)==y:
                return(x,y)
            else:
                x+=1

我不知道在数学上我们是否可以证明上面的 if 是唯一的例外，它可能可以通过更多的 modulo 操作来证明。我们可以通过编程方式在我们的代码中添加一些时钟，这样如果没有解决方案，这意味着它将进入无限循环，我们可以在一段时间后 return False 。以下是我们如何做到这一点：

How would I stop a while loop after n amount of time?

检查是否有办法在任意范围 F 内从 S 点到 G 点

Check if there is a Way to get from Point S to Point G in an Arbitrary Range F

python

search

integer

binary-search

divide-and-conquer