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

Question

给定1到F的任意范围，以及一个起点S和一个终点G，这样我们可以走的唯一方向是L左步和R右步（也是任意的），创建一个通用解决方案，返回从S到R所需的步数如果可能否则返回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)]

我在课堂上遇到过这个问题，我们当前的主题是二进制搜索和分而治之。这是我的方法，但这并不能解决一个隐藏的案例

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

从数学上讲，这个问题意味着我们正在寻找 以下等式的整数解（对于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模块L=0（左设备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

现在，我们想要y mod 1=0（意味着y是整数）表示x mod 1=0（x整数）。使用常见的模运算，我们采用：

y模式1=[（x*R/L）-（G-S）/L]模式1=

[（x*R/L）模式1-（（G-S）/L）模式1]模式1=

[（x模式1*（R/L）模式1）模式1-（（G-S）/L）模式1]模式1=

[（x模块1*0）模块1-（（G-S）/L）模块1]模块1=

[（（G-S）/L）模式1]模式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

我不知道；I don’我不知道我们是否能从数学上证明上述假设是唯一的例外，它可能可以用更多的模运算来证明。通过编程，我们可以在代码中添加一些时钟，这样，如果没有解决方案，这意味着它将进入Infive循环，我们可以在一段时间后返回False。以下是我们如何做到这一点：

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

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

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