深度优先算法解两个题
Aug202020
深度优先算法解两个题
最近读了<啊哈算法>看到里面使用深度优先算法解出了下面两个题,自己用Scala实现下,记录下来.
- 深度优先搜索 解决全排列问题
- 从 1~9共9个数字中选择正确数字填入_,使得等式 _ _ _ + _ _ _ = _ _ _ 成立
对于第二个题竟然由3百多个解,而自己想一个解想了半天…
先看dfs执行流程图
package com.jack.yin.algorithm
object DFS{
def main(args: Array[String]): Unit = {
//dfs(3)
dfsExample()
}
/**
* 深度优先搜索 解决全排列问题
* @param eleCount 需要进行全排列的元素个数
* 深度优先搜索的关键在于"解决当下如何做",而"下一步如何做"和"当下如何做"是一样的
* eleCount 个元素做全排列,相当于 面前放 eleCount个盒子(container),每一次从全排列元素中拿一个放到盒子里
* 使用eleUsedFlags保存对应的元素是否已经被放到盒子里了
* 深度优先搜索的模型为:
* void dfs(step){
* 判断边界
* 尝试每一种可能(每次都尝试 Range(0, eleCount).foreach)
* {
* 继续下一步 dfs(step + 1)
* }
* }
*/
def dfs(eleCount:Int):Unit = {
val container = Array.fill(eleCount)(0) // 容器,一个位置可以对应一个element
val eleUsedFlags = Array.fill(eleCount)(0) // 当前element 是否被使用的标志
doDfs(0)
def doDfs(step:Int):Unit = {
if (step == eleCount) {
println(container.mkString(", "))
return
}
Range(0, eleCount).foreach(i => {
if (eleUsedFlags(i) == 0) {
container(step) = i
eleUsedFlags(i) = 1
doDfs(step + 1)
eleUsedFlags(i) = 0
}
})
}
}
/**
* 利用 dfs算法的一道题
* 从 1~9 9个数字中选择正确数字填入下面的_,使得下面的等式 成立
* _ _ _ + _ _ _ = _ _ _
*/
def dfsExample():Unit = {
val eleCount = 9
val container = Array.fill(eleCount)(0)
val eleUsedFlags = Array.fill(eleCount)(0)
val numbers = Range(1,eleCount + 1).toArray
var answerCount = 0
doDfsExample(0)
println(s"total answerCount = ${answerCount}")
def doDfsExample(step:Int):Unit = {
if (step == eleCount) {
val ansFound = numbers(container(0)) * 100 + numbers(container(1)) * 10 + numbers(container(2)) +
numbers(container(3)) * 100 + numbers(container(4)) * 10 + numbers(container(5)) ==
numbers(container(6)) * 100 + numbers(container(7)) * 10 + numbers(container(8))
if(ansFound) {
answerCount += 1
println(s"${numbers(container(0))}${numbers(container(1))}${numbers(container(2))}+${numbers(container(3))}${numbers(container(4))}${numbers(container(5))}=${numbers(container(6))}${numbers(container(7))}${numbers(container(8))}")
}
//println(container.mkString(", "))
return
}
Range(0, eleCount).foreach(i => {
if (eleUsedFlags(i) == 0) {
container(step) = i
eleUsedFlags(i) = 1
doDfsExample(step + 1)
eleUsedFlags(i) = 0
}
})
}
}
}
赞 赏 微信赞赏
支付宝赞赏