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程序設計有所幫助。