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程序设计有所帮助。

赞 (0)

相关推荐

  • php加密算法之实现可逆加密算法和解密分享

    加密算法如下: 复制代码 代码如下: function encrypt($data, $key){ $key = md5($key);    $x  = 0;    $len = strlen($data);    $l  = strlen($key);    for ($i = 0; $i < $len; $i++)    {        if ($x == $l)         {         $x = 0;        }        $char .= $key{$x};   

  • php 大数据量及海量数据处理算法总结

    下面的方法是我对海量数据的处理方法进行了一个一般性的总结,当然这些方法可能并不能完全覆盖所有的问题,但是这样的一些方法也基本可以处理绝大多数遇到的问题.下面的一些问题基本直接来源于公司的面试笔试题目,方法不一定最优,如果你有更好的处理方法,欢迎与我讨论. 1.Bloom filter 适用范围:可以用来实现数据字典,进行数据的判重,或者集合求交集 基本原理及要点: 对于原理来说很简单,位数组+k个独立hash函数.将hash函数对应的值的位数组置1,查找时如果发现所有hash函数对应位都是1说明

  • 一组PHP可逆加密解密算法实例代码

    对于大部分密码加密,我们可以采用md5.sha1等方法.可以有效防止数据泄露,但是这些方法仅适用于无需还原的数据加密. 对于需要还原的信息,则需要采用可逆的加密解密算法. 下面一组PHP函数是实现此加密解密的方法: 加密算法如下: 复制代码 代码如下: function encrypt($data, $key){ $key = md5($key);    $x  = 0;    $len = strlen($data);    $l  = strlen($key);    for ($i = 0

  • PHP常用算法和数据结构示例(必看篇)

    实例如下: </pre><pre name="code" class="php"><?php /** * Created by PhpStorm. * User: qishou * Date: 15-8-2 * Time: 上午9:12 */ header("content-type:text/html;charset=utf-8"); $arr = array(3,5,8,4,9,6,1,7,2); echo im

  • PHP经典算法集锦【经典收藏】

    本文实例总结了PHP经典算法.分享给大家供大家参考,具体如下: 1.首先来画个菱形玩玩,很多人学C时在书上都画过,咱们用PHP画下,画了一半. 思路:多少行for一次,然后在里面空格和星号for一次. <?php for($i=0;$i<=3;$i++){ echo str_repeat(" ",3-$i); echo str_repeat("*",$i*2+1); echo '<br/>'; } 2.冒泡排序,C里基础算法,从小到大对一组数

  • PHP使用栈解决约瑟夫环问题算法示例

    本文实例讲述了PHP使用栈解决约瑟夫环问题算法.分享给大家供大家参考,具体如下: 约瑟夫环问题: 39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓.于是决定了自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀.然后下一个重新报数,直到所有人都自杀身亡为止.然而Josephus 和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏. <?php cla

  • php使用高斯算法实现图片的模糊处理功能示例

    php使用高斯算法实现图片的模糊处理功能示例

    本文实例讲述了php使用高斯算法实现图片的模糊处理功能.分享给大家供大家参考,具体如下: <?php class image_blur{ function gaussian_blur($srcImg,$savepath=null,$savename=null,$blurFactor=3){ $gdImageResource=$this->image_create_from_ext($srcImg); $srcImgObj=$this->blur($gdImageResource,$blu

  • php对称加密算法示例

    php对称加密算法 KEY 是之前定义的常量 复制代码 代码如下: Mcrypt::encrypt();Mcrypt::decrypt(); 复制代码 代码如下: defined('ROOT') or exit('Access Denied'); class Mcrypt{ public static function encrypt($code){  return base64_encode(mcrypt_encrypt(MCRYPT_RIJNDAEL_256, md5(KEY), $code

  • php中最简单的字符串匹配算法

    本文实例讲述了php中最简单的字符串匹配算法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: <?php /* 最简单字符串匹配算法php实现方式   T: ababcabc P: abc   0.          1.          2. ababcabc    ababcabc    ababcabc |||          |||          ||| abc          abc          abc (X)          (X)         

  • 适用于抽奖程序、随机广告的PHP概率算法实例

    那么我们在程序里必然会设计到算法,即按照一定的概率让用户获得奖品.先来看两个概率算法函数. 算法一 复制代码 代码如下: /** * 全概率计算 * * @param array $p array('a'=>0.5,'b'=>0.2,'c'=>0.4) * @return string 返回上面数组的key */function random($ps){    static $arr = array();    $key = md5(serialize($ps)); if (!isset

  • PHP实现的迪科斯彻(Dijkstra)最短路径算法实例

    PHP实现的迪科斯彻(Dijkstra)最短路径算法实例

    本文实例讲述了PHP实现的迪科斯彻(Dijkstra)最短路径算法.分享给大家供大家参考,具体如下: 一.待解决问题 单源最短路径问题,在给定有向图中求一个顶点(单源顶点)到其他所有顶点的最短路径问题.在下图中,每条边上有一个权值,希望求解A到所有其他顶点(B/C/D/E/F/G)的最短路径. 二.问题分析(最短路径的子结构同样最优性) 如果P(A,G)是从顶点A到G的最短路径,假设D和F是这条路径上的中间点,那么P(D,F)一定时从D到F的最短路径.如果P(D,F)不是D到F的最短路径,那必然

  • PHP大转盘中奖概率算法实例

    本文实例讲述了PHP大转盘中奖概率算法的实现方法,分享给大家供大家参考.具体如下: 大转盘是最近很多线上网动中一个比较有意思的东西了,下面我们就来看看这个大转盘中奖概率算法与例子,希望对各位有所帮助. 这是一个APP客户端有大转盘抽奖算法,具体如何抽奖当然在我们服务端实现了.下面和大家简单分享一下实现代码: 复制代码 代码如下: header("Content-type: text/html; charset=utf-8"); $prize_arr = array( '0' =>

随机推荐