欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

PHP实现的蚂蚁爬杆路径算法代码

程序员文章站 2022-04-08 14:55:06
本文实例讲述了php实现的蚂蚁爬杆路径算法代码。分享给大家供大家参考,具体如下:

本文实例讲述了php实现的蚂蚁爬杆路径算法代码。分享给大家供大家参考,具体如下:

<?php
/**
 * 有一根27厘米的细木杆,在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。
 * 木杆很细,不能同时通过一只蚂蚁。开始 时,蚂蚁的头朝左还是朝右是任意的,它们只会朝前走或调头,
 * 但不会后退。当任意两只蚂蚁碰头时,两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。
 * 编写程序,求所有蚂蚁都离开木杆 的最小时间和最大时间。
 */
function add2($directionarr, $count, $i) {
 if(0 > $i) { // 超出计算范围
  return $directionarr;
 }
 if(0 == $directionarr[$i]) { // 当前位加1
  $directionarr[$i] = 1;
  return $directionarr;
 }
 $directionarr[$i] = 0;
 return add2($directionarr, $count, $i - 1); // 进位
}
$positionarr = array( // 所在位置
 3,
 7,
 11,
 17,
 23
);
function path($positionarr) { // 生成测试路径
 $pathcalculate = array();
 $count = count($positionarr);
 $directionarr = array_fill(0, $count, 0); // 朝向
 $end = str_repeat('1', $count);
 while (true) {
  $path = implode('', $directionarr);
  $patharray = array_combine($positionarr, $directionarr);
  $total = calculate($positionarr, $directionarr);
  $pathcalculate['p'.$path] = $total;
  if($end == $path) { // 遍历完成
   break;
  }
  $directionarr = add2($directionarr, $count, $count - 1);
 }
 return $pathcalculate;
}
function calculate($positionarr, $directionarr) {
 $total = 0; // 总用时
 $length = 27; // 木杆长度
 while ($positionarr) {
  $total++; // 步增耗时
  $nextarr = array(); // 下一步位置
  foreach ($positionarr as $key => $value) {
   if(0 == $directionarr[$key]) {
    $next = $value - 1; // 向0方向走一步
   } else {
    $next = $value + 1; // 向1方向走一步
   }
   if(0 == $next) { // 在0方向走出
    continue;
   }
   if($length == $next) { // 在1方向走出
    continue;
   }
   $nextarr[$key] = $next;
  }
  $positionarr = $nextarr; // 将$positionarr置为临时被查找数组
  foreach ($nextarr as $key => $value) {
   $findarr = array_keys($positionarr, $value);
   if(count($findarr) < 2) { // 没有重合的位置
    continue ;
   } 
   foreach ($findarr as $findindex) {
    $directionarr[$findindex] = $directionarr[$findindex] ? 0 : 1; // 反向处理
    unset($positionarr[$findindex]); // 防止重复查找计算
   }
  }
  $positionarr = $nextarr; // 将$positionarr置为下一步结果数组
 }
 return $total;
}
$pathcalculate = path($positionarr);
echo '<pre>calculate-';
print_r($pathcalculate);
echo 'sort-';
asort($pathcalculate);
print_r($pathcalculate);

希望本文所述对大家php程序设计有所帮助。