当前位置: 首页 > Scala, 程序代码, 算法 > 正文

深度优先算法解两个题

深度优先算法解两个题

最近读了<啊哈算法>看到里面使用深度优先算法解出了下面两个题,自己用Scala实现下,记录下来.

  1. 深度优先搜索 解决全排列问题
  2. 从 1~9共9个数字中选择正确数字填入_,使得等式 _ _ _ + _ _ _ = _ _ _ 成立

对于第二个题竟然由3百多个解,而自己想一个解想了半天…

先看dfs执行流程图

PlantUML Syntax:
@startuml
digraph dfs {
graph[colorscheme = "gnbu9",bgcolor=1,fontname="AR PL UMing CN",compound=False,showboxes = 2]
node[shape=box,colorscheme = "set312",fontsize = 12,fontname="AR PL UMing CN"];
edge[colorscheme = "paired12",arrowsize=0.8,labelfontname="AR PL UMing CN",fontname="AR PL UMing CN"]
step_0[label = "step = 0 \n (以3个元素[0,1,2]的全排列为例)", color = 4, fontcolor = 4, fontsize = 11 ];
rec_0[shape = "record",color =4 ,fontcolor = 4,label = "<f0>Foreach(0,1,2可用)|<f1>0|<f2>1|<f3>2"];
step_1[label = "step = 1 \n 0已用", color = 5, fontcolor = 5, fontsize = 11 ];
rec_1[shape = "record",color =5 ,fontcolor = 5,label = "<f0>Foreach(1,2可用)|<f1>0|<f2>1|<f3>2"];
step_2[label = "step = 2 \n 0,1已用", color = 6, fontcolor = 6, fontsize = 11 ];
rec_2[shape = "record",color = 6 ,fontcolor = 6,label = "<f0>Foreach(2可用)|<f1>0|<f2>1|<f3>2"];
step_3[label = "step = 3 \n 0,1,2已用,找到一个组合(0,1,2),返回", color = 10, fontcolor = 10, fontsize = 11 ];
step_0 -> rec_0:f1[color = 5];
rec_0:f1 -> step_1[color = 5]
step_1 -> rec_1:f2 [color = 5]
rec_1:f2 -> step_2[color = 5]
step_2 -> rec_2:f3[color = 5]
rec_2:f3 -> step_3[color = 5]
step_3 -> step_2[color = 2,fontcolor = 2,label="返回dfs(3)的调用 \n 后面再执行 \n  eleUsedFlags(2) = 0", fontsize = 11]
step_2 -> step_1[color = 2,fontcolor = 2,label="返回dfs(2)的调用 \n 后面再执行 \n  eleUsedFlags(1) = 0", fontsize = 11]
rec_12[shape = "record",color =5 ,fontcolor = 5,label = "<f0>Foreach(1,2可用)|<f1>0|<f2>1|<f3>2"];
step_1 -> rec_12:f3[color = 5];
step_22[label = "step = 2 \n 0,2已用", color = 6, fontcolor = 6, fontsize = 11 ];
rec_22[shape = "record",color = 6 ,fontcolor = 6,label = "<f0>Foreach(1可用)|<f1>0|<f2>1|<f3>2"];
rec_12:f3 -> step_22[color = 5];
step_22  -> rec_22:f2[color = 5];
step_32[label = "step = 3 \n 0,2,1已用,找到一个组合(0,2,1),返回", color = 10, fontcolor = 10, fontsize = 11];
rec_22:f2 -> step_32[color = 5];
step_22 -> step_1[color = 2,fontcolor = 2,label="返回dfs(2)的调用  \n  后面再执行  \n  eleUsedFlags(2) = 0", fontsize = 11];
step_32 -> step_22[color = 2,fontcolor = 2,label="返回dfs(3)的调用  \n  后面再执行  \n  eleUsedFlags(1) = 0", fontsize = 11];
step_1 -> step_0[color = 2,fontcolor = 2,label="返回dfs(1)的调用  \n  后面再执行  \n  eleUsedFlags(2) = 0,后面继续Foreach调用1,2", fontsize = 11];
}
@enduml

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
        }
      })
    }
  }
}
赞 赏

   微信赞赏  支付宝赞赏


本文固定链接: https://www.jack-yin.com/coding/3234.html | 边城网事

该日志由 边城网事 于2020年08月20日发表在 Scala, 程序代码, 算法 分类下, 你可以发表评论,并在保留原文地址及作者的情况下引用到你的网站或博客。
原创文章转载请注明: 深度优先算法解两个题 | 边城网事
【上一篇】
【下一篇】

深度优先算法解两个题 暂无评论

发表评论

快捷键:Ctrl+Enter