题目描述:
有一根27厘米的细木杆,在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细,不能同时通过一只蚂蚁。开始时,蚂蚁的头朝左还是朝右是任意的,它们只会朝前走或调头,但不会后退。当任意两只蚂蚁碰头时,两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。编写程序,求所有蚂蚁都离开木杆的最小时间和最大时间。
前面发了2篇文章给了递归和非递归的算法,但是那基本是模拟了蚂蚁运动的过程,真实的复现了实验的场景,在此基础上,我又对蚂蚁运动过程进行了简单的分析,发现其运动的问题可以转化成新的更简略的问题
为此,给出了一个简化算法,实现步骤如下,算法思想也在注释里说明,请大家指正.
package com.leochan;
public class AnalysisAntWalker {
public static int totalLength = 27;
public static void main(String[] args) {
analysisTest();
}
/*
* 处理的思想是
* 我们不妨假设,所有的蚂蚁即便是走到了边界也不停下,继续向前走,此外,我们将蚂蚁编号a,b,c,d,e
* 那么对于5只蚂蚁,无论方向如何,只要经历的时间相同,那么它们走过的路程也一定相同
* 所以对于过程中,出现蚂蚁相遇的情况,可以等价看成不变向,让原先的蚂蚁继续向前走,直到它们都达到边界。
* 所以最终的结果是,2种情况下求出的时间相同,只是达成这个时间的蚂蚁编号不同
* 因此,所有的蚂蚁所需的时间只取决于它初始位置和方向,把原始的问题转化为一个新的等价问题,
* 求解得到各种情况下所需的时间,从而得知最大时间和最小时间。
*/
private static void analysisTest() {
int count = 0;
for (int d1 = -1; d1 <= 1; d1 += 2) {
for (int d2 = -1; d2 <= 1; d2 += 2) {
for (int d3 = -1; d3 <= 1; d3 += 2) {
for (int d4 = -1; d4 <= 1; d4 += 2) {
for (int d5 = -1; d5 <= 1; d5 += 2) {
count++;
int dd1 = d1 * 3, dd2 = d2 * 7, dd3 = d3 * 11, dd4 = d4 * 17, dd5 = d5 * 23;
int time = 0;
// d1
if (d1 < 0)
time = -dd1;
else
time = totalLength - dd1;
// d2
if (d2 < 0)
time = time > (-dd2) ? time : (-dd2);
else
time = time > (totalLength - dd2) ? time
: (totalLength - dd2);
// d3
if (d3 < 0)
time = time > (-dd3) ? time : (-dd3);
else
time = time > (totalLength - dd3) ? time
: (totalLength - dd3);
// d4
if (d4 < 0)
time = time > (-dd4) ? time : (-dd4);
else
time = time > (totalLength - dd4) ? time
: (totalLength - dd4);
// d5
if (d5 < 0)
time = time > (-dd5) ? time : (-dd5);
else
time = time > (totalLength - dd5) ? time
: (totalLength - dd5);
System.out.print("count=" + count + " d1=" + d1
+ " d2=" + d2 + " d3=" + d3 + " d4=" + d4
+ " d5=" + d5);
System.out.println(" time=" + time);
}
}
}
}
}
}
}
分享到:
相关推荐
整理了部分面试题包含了各大互联网,百度、阿里、京东、腾讯、蚂蚁金服、中国平安、商汤科技、拼多多、oppo、唯品会等,全部已整理为pdf文档 上海-拼多多-Java高级.pdf 上海-携程-Java高级.pdf 北京-京东-Java中级....
01 java面试——北京-百度-Java中级.pdf 02 java面试——北京-京东-Java中级.pdf 03 java面试——广州-唯品会-Java大数据开发工程师.pdf 04 java面试——杭州-阿里云-Java中级.pdf 05 java面试——杭州-蚂蚁金服-...
2021Java大厂面试题——大厂真题之蚂蚁金服-Java高级.pdf
【Java面试资料】-蚂蚁金服面试题总结
大厂面试真题深圳-蚂蚁金服-Java高级提取方式是百度网盘分享地址
大厂面试真题杭州-蚂蚁金服-Java高级提取方式是百度网盘分享地址
互联网企业面试真题 深圳-OPPO.pdf 深圳-银盛支付-Java中级.pdf 深圳-中国平安-Java中级.pdf 深圳-商汤科技.pdf 深圳-腾讯.pdf 深圳-乐信.pdf 深圳-蚂蚁金服.pdf 上海-携程.pdf 深圳-丰巢科技.pdf 厦门-中软国际-...
2021Java大厂面试题——大厂真题之蚂蚁金服-资深工程师.pdf
2018 年蚂蚁课堂(每特教育) Java工程师面试宝典-V1.0.docx。 Java高级工程师面试宝典 该面试宝典由蚂蚁课堂创始人-余胜军原创整理 内容含括了:JavaSE、JavaEE、微服务、分布式、项目等。 java
2019年蚂蚁课堂-余胜军主编Java工程师面试宝典-V1.0
2019年蚂蚁课堂-余胜军主编Java工程师面试宝典,每特教育培训总结面试,高薪宝典
一根长度为L厘米的木棍上有n只蚂蚁,每只蚂蚁要么朝左爬,要么朝右爬,速度为1厘米/秒。当两只蚂蚁相撞时,二者同时掉头(掉头时间忽略不计)。给出每只蚂蚁的初始位置和朝向,计算T秒之后每只蚂蚁的位置。 程序给出...
前端大厂最新面试题-2019蚂蚁金服前端社招面经.docx
2019蚂蚁金服Java必问面试题及答案2019蚂蚁金服Java必问面试题及答案 2019蚂蚁金服Java必问面试题及答案2019蚂蚁金服Java必问面试题及答案
上海-拼多多-Java高级,杭州-阿里云-Java实习生,北京-京东-Java实习生,深圳-腾讯-Java高级,杭州-蚂蚁金服-Java高级,深圳-丰巢科技,北京-百度-Java中级,04_并发编程_面试专题及答案
Java高级工程师面试宝典 该面试宝典由蚂蚁课堂创始人-余胜军原创整理 内容含括了:JavaSE、JavaEE、微服务、分布式、项目等。
关于java的面试宝典问题,java工程师的福音来啦,里面有很多企业在招收java工程师的面试的时候问到的,去面试的java工程师可要好好的看看咯~
java面试——深圳-蚂蚁金服-Java高级.zip
java面试——杭州-蚂蚁金服-Java高级.zip