Swift算法计算到达目的地的可能路径
Swift算法计算到达目的地的可能路径
提问于 2017-02-16 14:53:42
我正在写一个算法来计算到达目的地的可能路数，假设每一步都可以是1到6步的随机数，那么到达目的地的距离是n步。
以下是该算法的概述：
f(1) = 1 // when total number of block is 1, there is 1 way to reach the goal
f(2) = 2 // when total number of block is 2, there is 2 ways to reach the goal, such as 1+1 and 2
f(3) = 5 // when total number of block is 3, there is 5 ways to reach the goal
f(4) = 8 // when total number of block is 3, there is 5 ways to reach the goal
f(5) = 14 // when total number of block is 3, there is 5 ways to reach the goal
f(6) = 25 // when total number of block is 3, there is 5 ways to reach the goal
// when total number of block is 7, you may rolled 1~6 at 1st time
// then you have 7-1 ~ 7-6 block for the rest, thus
f(7) = f(7-1) + f(7-2) + f(7-3) + f(7-4) + f(7-5) + f(7-6)
// With MI, when total number of block is n, then
f(n) = f(n-1) + f(n-2) + f(n-3) + f(n-4) + f(n-5) + f(n-6)我设法得到了函数
func probabilityToGoal(_ n: Int) -> Int {
if n == 1 {return 1}
if n == 2 {return 2}
if n == 3 {return 5}
if n == 4 {return 8}
if n == 5 {return 14}
if n == 6 {return 25}
return probabilityToGoal(n-1)
+ probabilityToGoal(n-2)
+ probabilityToGoal(n-3)
+ probabilityToGoal(n-4)
+ probabilityToGoal(n-5)
+ probabilityToGoal(n-6)
}但问题是，函数只在小值(小于50)时运行，对于大值(例如n= 610)，如何在swift 3中实现上述算法。
回答 1
Stack Overflow用户
回答已采纳
发布于 2017-02-16 15:29:36
您需要使用一种称为动态编程的技术。
这个想法是通过避免对已经计算的值的递归调用来修剪调用树的整个分支。
字典用于存储从输入到输出的映射。每次要完成一个新的递归调用时，首先检查字典，看它是否已经包含所需输入的输出。如果它存在，则使用它，否则使用递归来获得结果。计算后，结果将存储在字典中以供将来使用。
下面是它应该是什么样子的：
var cache = [Int: Int]()
func probabilityToGoal(_ n: Int) -> Int {
if n == 1 { return 1 }
if n == 2 { return 2 }
if n == 3 { return 5 }
if n == 4 { return 8 }
if n == 5 { return 14 }
if n == 6 { return 25 }
if let existingValue = cache[n] {
// result for n is already known, just return it
return existingValue
}
let newValue = probabilityToGoal(n-1)
+ probabilityToGoal(n-2)
+ probabilityToGoal(n-3)
+ probabilityToGoal(n-4)
+ probabilityToGoal(n-5)
+ probabilityToGoal(n-6)
cache[n] = newValue // store result for future result
return newValue
}
print(probabilityToGoal(64))请记住，这在≥64上是行不通的，因为它会溢出64位Int (在64位系统上)。
此外，迭代解决方案的执行速度会快得多，因为它消除了递归开销，并允许您使用数组而不是字典：
var cache = [0, 1, 2, 5, 8, 14,25]
func probabilityToGoal2(_ n: Int) -> Int {
cache.reserveCapacity(n)
for i in stride(from: n, to: 6, by: +1) {
let r1 = cache[i - 1] + cache[i - 2]
let r2 = cache[i - 3] + cache[i - 4]
let r3 = cache[i - 5] + cache[i - 6]
cache.append(r1 + r2 + r3)
}
return cache[n]
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/42266900
复制相关文章
相似问题
腾讯云开发者
