有N栋楼。蜘蛛侠正在kth楼吃晚饭。他得知X楼发生火灾事故。问题是在任何时候他都可以恰好向前跳 F 建筑物或向后恰好跳 B 建筑物。他想知道是否有可能到达第 X 栋楼，如果有可能，他想知道到达第 X 栋楼的最少跳跃次数。
我尝试使用递归来解决这个问题。但我有某种直觉，它可以通过其他一些逻辑来解决。有人可以推荐一个吗？
最佳答案
一旦掌握了背后的数学知识，解决方案在算法上就很简单。 您需要实现扩展欧几里德算法和其他一些东西。
设M = X - K，你想检查M = H F + K B是否有一些整数H, K。
答案(称为 Bezout 恒等式)是当且仅当 M 可被 F 和 B，我们称之为D。
假设存在一个解，那么你就可以解
H F + K B = D。
调用 (H,K) = (S_H, S_K) 它的任何解，使用扩展欧几里德算法找到它。
那么存在无限解(T_H, T_K)，每个整数L都有一个，这些都是这样的形式
T_H = S_H + L B/D
T_K = S_K - L F/D
您对|T_H| 的最小值的解决方案感兴趣+ |T_K|，这可以再次从理论上计算，或者使用简单的 for 循环检查最小值，它是一个分段线性函数，当 L 接近 +-无限。
对于 Bezout 身份的背景数学，网上有很多资料。
编辑:这似乎包含所有你需要的http://public.csusm.edu/aitken_html/m422/Handout1.pdf
关于arrays - 到达某一点所需的最少步数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/49616465/