博客
关于我
跳蚱蜢(蓝桥杯 )
阅读量:754 次
发布时间:2019-03-21

本文共 771 字,大约阅读时间需要 2 分钟。

跳蚱蜢问题是一个关于寻找最短跳跃次数的填空题目。问题描述如下:

有9个盘子排成一个圆圈,其中8个盘子分别装有编号1到8的蚱蜢,剩下的一个盘子是空的。目标是通过蚱蜢们的跳跃,使得它们的排列顺序按照逆时针方向排列,同时保持空盘的位置不变。初始状态为123456789,目标状态为876543219。每只蚱蜢可以跳到相邻的空盘,也可以跳过一个相邻的蚱蜢到达空盘。问题要求计算使得蚱蜢们达到目标状态的最少跳跃次数。

解决方法:

我们采用广度优先搜索(BFS)算法来寻找最短路径。具体步骤如下:

  • 状态表示:用一个整数表示当前盘子的排列状态。例如,初始状态为123456789,目标状态为876543219。

  • 队列处理:使用队列来进行BFS。每次处理一个状态的队列中的元素,生成所有可能的后继状态,并将未访问过的状态加入队列。

  • 状态生成:对于每个当前状态,计算从中可以跳跃的所有可能的新状态。考虑左右跳跃以及左跳一个、右跳两个的移动方式。

  • 访问检查:使用一个visited数组记录已经访问过的状态,避免重复处理。

  • 终止条件:当生成的新状态与目标状态相同时,返回当前的跳跃次数+1。这将是从初始状态到目标状态的最短跳跃次数。

  • 代码实现步骤如下:

    • 包含必要的头文件和标准库。
    • 初始化队列,将初始状态和跳跃次数0加入队列。
    • 使用visited数组记录访问过的状态。
    • 进入BFS循环,处理队列中的每个状态。
    • 对于每个状态,分解盘子状态为数字列表,确定当前空盘的位置。
    • 对于当前空盘的位置,计算所有可能的跳跃方向。
    • 生成新的盘子状态,如果是新状态,加入队列并标记为已访问。
    • 如果生成的新状态是目标状态,输出跳跃次数+1,并结束程序。

    这个问题通过BFS算法可以快速找到最短路径,因为每次只处理未访问过的状态,确保了找到的是最少跳跃次数。

    答案:最少需要20次跳跃。

    转载地址:http://beagz.baihongyu.com/

    你可能感兴趣的文章
    mysql generic安装_MySQL 5.6 Generic Binary安装与配置_MySQL
    查看>>
    Mysql group by
    查看>>
    MySQL I 有福啦,窗口函数大大提高了取数的效率!
    查看>>
    mysql id自动增长 初始值 Mysql重置auto_increment初始值
    查看>>
    MySQL in 太多过慢的 3 种解决方案
    查看>>
    MySQL InnoDB 三大文件日志,看完秒懂
    查看>>
    Mysql InnoDB 数据更新导致锁表
    查看>>
    Mysql Innodb 锁机制
    查看>>
    MySQL InnoDB中意向锁的作用及原理探
    查看>>
    MySQL InnoDB事务隔离级别与锁机制深入解析
    查看>>
    Mysql InnoDB存储引擎 —— 数据页
    查看>>
    Mysql InnoDB存储引擎中的checkpoint技术
    查看>>
    Mysql InnoDB存储引擎中缓冲池Buffer Pool、Redo Log、Bin Log、Undo Log、Channge Buffer
    查看>>
    MySQL InnoDB引擎的锁机制详解
    查看>>
    Mysql INNODB引擎行锁的3种算法 Record Lock Next-Key Lock Grap Lock
    查看>>
    mysql InnoDB数据存储引擎 的B+树索引原理
    查看>>
    mysql innodb通过使用mvcc来实现可重复读
    查看>>
    mysql insert update 同时执行_MySQL进阶三板斧(三)看清“触发器 (Trigger)”的真实面目...
    查看>>
    mysql interval显示条件值_MySQL INTERVAL关键字可以使用哪些不同的单位值?
    查看>>
    Mysql join原理
    查看>>