蚂蚁爬杆的面试题(PHP解法)
题目如下:
【蚂蚁爬杆的面试题(PHP解法)】有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细，不能同时通过一只蚂蚁。开始时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。编写程序，求所有蚂蚁都离开木杆的最小时间和最大时间。
问题分析:杆就是数轴,蚂蚁就是点,左和右两个状态就是0和1,蚂蚁方向的初始状态有00000到11111一共32 种状态,PHP中使用
decbin($number) 函数将数字转成二进制,由于必须要5位,再用 str_pad($number,5,"0",STR_PAD_LEFT)在$number左方补齐0,总位数5位,在用 str_split($number)将数组拆分成一个个数字的数组,这个数组就是蚂蚁的初始状态
代码如下,两个函数暴力破解
function begin(){
$arr=[];
for($i=0;
$i<32;
$i++){
$arr[str_pad(decbin($i),5,"0",STR_PAD_LEFT)]=move(str_split(str_pad(decbin($i),5,"0",STR_PAD_LEFT)));
}
return $arr;
}function move($arr){
$brr=[3,7,11,17,23];
$n=-1;
while (count($brr)>=1){
//这个for循环每一个大循环完毕,就是所有的蚂蚁都走了一步,若出界,则删除数组元素
for($i=0;
$i还有bug,可能是代码逻辑有问题,当条件为01100和11111的时候,数据是不对的,有空检查一下
文章图片
实际分析问题的时候其实用不着分析碰头的情况,碰头的时候完全可以看做蚂蚁互相穿过,所以很明显的最长时间为最右侧的蚂蚁向左爬用的时间,最短是3,7,11向左爬,17,23向右爬
推荐阅读
- 热闹中的孤独
- JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
- 放屁有这三个特征的，请注意啦！这说明你的身体毒素太多
- 一个人的旅行，三亚
- 布丽吉特，人生绝对的赢家
- 慢慢的美丽
- 尽力
- 一个小故事，我的思考。
- 家乡的那条小河
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量