没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示
试读
4页
趣味蚂蚁问题是一个最近在互联网上出现的一个智力问 题。其具体描述如下: 有一根27厘米的细木杆,在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细,不能同时通过两只蚂蚁。开始时,蚂蚁的头朝左还是朝右是任意的,它们只会朝前走或调头,但不会后退。当任意两只蚂蚁碰头时,两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。编写程序,求所有蚂蚁都离开木杆的最小时间和最大时间。
资源推荐
资源详情
资源评论
编程疑难问题解答
2010. 7
怎样以
Java
编程解决趣味蚂蚁问题
!"
问题描述
趣味蚂蚁问题是一个最近在互联网上出现的一个智力问
题! 其具体描述如下"
有一根
#$
厘米的细木杆# 在第
%
厘米$
$
厘米$
!!
厘米$
!$
厘米$
#%
厘米这五个位置上各有一只蚂蚁! 木杆很细% 不
能同时通过两只蚂蚁! 开始时% 蚂蚁的头朝左还是朝右是任意
的% 它们只会朝前走或调头% 但不会后退! 当任意两只蚂蚁碰
头时% 两只蚂蚁会同时调头朝反方向走! 假设蚂蚁们每秒钟可
以走一厘米的距离! 编写程序% 求所有蚂蚁都离开木杆的最小
时间和最大时间!
#"
问题分析
趣味蚂蚁问题首先是一个排列组合问题" 每个位置上的蚂
蚁有
#
个朝向%对
&’&(!
%
#
%
%
%&
)
只蚂蚁的问题%共有
#&
种排
列方式’ 当排列方式确定以后% 该问题转化为一个状态迁移过
程% 即由最初的排列状态% 经过一系列移动步骤% 达到所有蚂
蚁离开木杆的状态(
计算机编程需要模拟出木杆上的蚂蚁排列状态和状态迁移
步骤% 在程序设计中% 将木杆上的蚂蚁排列实现为一个蚂蚁队
列
% 并为蚂蚁队列设计出一个移动方法% 模拟队列中的蚂蚁移
动’ 当蚂蚁移动而离开木杆时% 将其从队列中删除) 蚂蚁队列
的状态由其中的蚂蚁构成% 其初始状态就是起初的蚂蚁排列状
态% 其终止状态就是队列为空! 中间状态将选取发生蚂蚁碰头
的时刻% 并据此来设计移动方法!
每步移动后% 需要对蚂蚁队列的状态进行调整" 发生碰头
的蚂蚁切换朝向% 越界的蚂蚁从队列中删除! 在蚂蚁队列由初
始状态迁移至终止状态的过程中% 程序只要统计出蚂蚁队列的
移动路程% 就可以获得蚂蚁移动的时间"
时间
(
路程
*
速度
对于最小值问题% 也可以精心构造一个排列% 而直接求
得’ 在此% 也将其视作一个一般问题% 而采用一致的方法求
取!
%"
编程解决
通过前面的分析% 现编写程序% 模拟出所有组合方式% 找
到所有蚂蚁都离开木杆的最小时间和最大时间!
*
!
+ 类
+,-
类
+,-
实现问题中的蚂蚁% 其主要代码如下"
!"#$$ %&’
(
)*+,#’- +&’ ).$+’+.&/ 00
位置
)*+,#’- +&’ 1+*-!’+.&/ 00
朝向
)23"+! %&’ 4+&’ ).$+’+.&5 +&’ 1+*-!’+.&6
(
’7+$8).$+’+.& 9 ).$+’+.&/
’7+$81+*-!’+.& 9 1+*-!’+.&/
:
00
切换蚂蚁朝向
)23"+! ,.+1 ;"+)<+*-!’+.& =6
(
1+*-!’+.& >9 ?@/
:
00
蚂蚁移动,
1+$’#&!-
指定移动距离
)23"+! ,.+1 A.,- =+&’ 1+$’#&!-6 (
).$+’+.& B9 1+$’#&!- > 1+*-!’+.& /
:
00
右冲突
C#
是否位于右端, 且方向相对
)23"+! 3.."-#& D+""E.""+1-F+G7’ =%&’ #H
(
*-’2*& ’7+$8).$+’+.& I #8G-’J.$+’+.& =6 KK
’7+$81+*-!’+.& 99 %&’8FLMNO KK
#8G-’<+*-!’+.& =6 99 %&’8PQRO/
:
00
是否碰头
)23"+! 3.."-#& +$E.""+1- =%&’ #6
(
*-’2*& ’7+$8).$+’+.& 99 #8G-’J.$+’+.& =6 /
:
)23"+! ;+&#" $’#’+! +&’ PQRO 9 ?@/ 00
朝向
C
左
)23"+! ;+&#" $’#’+! +&’ FLMNO 9 @/ 00
朝向
C
右
)*+,#’- $’#’+! +&’ $)--1 9 @/ 00
运动速度
…
:
+,-
类的成员
./01-1/,
表示蚂蚁在木杆上的位置%
21345-1/,
表示其朝向) 方法
6/7489
实现蚂蚁移动’ 方法
:;1.<1345-1/,’9
用
来切换其朝向’ 方法
=1;;>/;;124?1@A-89
用来判断蚂蚁是否与位
于其右边的相邻蚂蚁在移动中会发生撞头’ 方法
10>/;;124 89
用
来判断两只蚂蚁是否碰头) 蚂蚁的朝向左和右% 以类静态常量
实现% 即
BCDE
和
?FGHE
) 蚂蚁的运动速度% 以类静态 变量
实现% 即
0.442
)
*
#
+ 类
+,-IJ4J4
类
+,-IJ4J4
表示蚂蚁队列% 一个蚂蚁队列模拟一种排列
方式) 下面分析其主要代码"
!"#$$ %&’S2-2- +A)"-A-&’$ F2&"-T E#""3#!U
(
)*+,#’- +&’ ".G/ 00
木杆长度
)*+,#’- P+$’ "+$’/ 00
蚂蚁队列
)*+,#’- +&’ 1+$’#&!- 9 V/ 00
统计蚂蚁运动路程
87
资源评论
bihaichentian
- 粉丝: 19
- 资源: 197
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 转载使用许可协议范本(互联网行业)模版.doc
- 软件产业运行情况调研问卷模版.doc
- 软件产品发布管理流程.doc
- 软件仿真多机串行通信.doc
- Python大作业:音乐播放软件(爬虫+可视化+数据分析+数据库)
- 课程设计-python爬虫-爬取日报,爬取日报文章后存储到本地,附带源代码+课程设计报告
- 软件和信息技术服务行业投资与前景预测.pptx
- 课程设计-基于SpringBoot + Mybatis+python爬虫NBA球员数据爬取可视化+源代码+文档+sql+效果图
- 软件品质管理系列二项目策划规范.doc
- 基于TensorFlow+PyQt+GUI的酒店评论情感分析,支持分析本地数据文件和网络爬取数据分析+源代码+文档说明+安装教程
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功