这篇文章主要介绍了PHP实现的蚂蚁爬杆路径算法代码,以完整实例形式分析了蚂蚁爬杆路径算法的原理与实现方法,涉及php数值计算与数组操作的相关技巧,需要的朋友可以参考下。

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

1. <?php 
2. /** 
3.  * 有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。 
4.  * 木杆很细，不能同时通过一只蚂蚁。开始 时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头， 
5.  * 但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。 
6.  * 编写程序，求所有蚂蚁都离开木杆 的最小时间和最大时间。 
7.  */ 
8. function add2($directionArr, $count, $i) { 
9.  if(0 > $i) { // 超出计算范围 
10.   return $directionArr; 
11.  } 
12.  if(0 == $directionArr[$i]) { // 当前位加1 
13.   $directionArr[$i] = 1; 
14.   return $directionArr; 
15.  } 
16.  $directionArr[$i] = 0; 
17.  return add2($directionArr, $count, $i - 1); // 进位 
18. } 
19. $positionArr = array( // 所在位置 
20.  3, 
21.  7, 
22.  11, 
23.  17, 
24.  23 
25. ); 
26. function path($positionArr) { // 生成测试路径 
27.  $pathCalculate = array(); 
28.  $count = count($positionArr); 
29.  $directionArr = array_fill(0, $count, 0); // 朝向 
30.  $end = str_repeat('1', $count); 
31.  while (true) { 
32.   $path = implode('', $directionArr); 
33.   $pathArray = array_combine($positionArr, $directionArr); 
34.   $total = calculate($positionArr, $directionArr); 
35.   $pathCalculate['P'.$path] = $total; 
36.   if($end == $path) { // 遍历完成 
37.    break; 
38.   } 
39.   $directionArr = add2($directionArr, $count, $count - 1); 
40.  } 
41.  return $pathCalculate; 
42. } 
43. function calculate($positionArr, $directionArr) { 
44.  $total = 0; // 总用时 
45.  $length = 27; // 木杆长度 
46.  while ($positionArr) { 
47.   $total++; // 步增耗时 
48.   $nextArr = array(); // 下一步位置 
49.   foreach ($positionArr as $key => $value) { 
50.    if(0 == $directionArr[$key]) { 
51.     $next = $value - 1; // 向0方向走一步 
52.    } else { 
53.     $next = $value + 1; // 向1方向走一步 
54.    } 
55.    if(0 == $next) { // 在0方向走出 
56.     continue; 
57.    } 
58.    if($length == $next) { // 在1方向走出 
59.     continue; 
60.    } 
61.    $nextArr[$key] = $next; 
62.   } 
63.   $positionArr = $nextArr; // 将$positionArr置为临时被查找数组 
64.   foreach ($nextArr as $key => $value) { 
65.    $findArr = array_keys($positionArr, $value); 
66.    if(count($findArr) < 2) { // 没有重合的位置 
67.     continue ; 
68.    }  
69.    foreach ($findArr as $findIndex) { 
70.     $directionArr[$findIndex] = $directionArr[$findIndex] ? 0 : 1; // 反向处理 
71.     unset($positionArr[$findIndex]); // 防止重复查找计算 
72.    } 
73.   } 
74.   $positionArr = $nextArr; // 将$positionArr置为下一步结果数组 
75.  } 
76.  return $total; 
77. } 
78. $pathCalculate = path($positionArr); 
79. echo '<pre>calculate-'; 
80. print_r($pathCalculate); 
81. echo 'sort-'; 
82. asort($pathCalculate); 
83. print_r($pathCalculate); 

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

Tags: PHP蚂蚁爬杆路径算法

分享到：