Joh*_*ena 3 arrays algorithm recursion data-structures
有N栋建筑.蜘蛛侠在第k大楼吃晚餐.他知道Xth大楼发生火灾.问题是,在任何时候他都可以准确地向前跳F建筑物或向后跳回B建筑物.他希望能够到达Xth大楼,如果是的话,他想知道到达Xth大楼的最小跳跃次数.
我尝试使用递归来解决这个问题.但我有某种直觉,可以通过其他逻辑来解决.任何人都可以推荐一个吗？
一旦你掌握了数学算法,解决方案在算法上就很简单了.您需要实现扩展欧几里德算法以及更多内容.
让M = X - K,你想检查是否M = H F + K B有一些整数H, K.
答案(被称为贝祖定理)是方程承认当且仅当一个解决方案M是由除尽GCD(最大公约数)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
| 归档时间： |
|
| 查看次数： |
68 次 |
| 最近记录： |