题目:
n个猴子围坐一圈,从第一个猴子开始数,到第m个出列,求最后一个猴子的编号.
分析:
首先想到循环,然后队列,然后堆,所以用数组模拟一个循环的列表,下标为[0-(n-1)],下标+1整除m干掉元素,否则加入队尾,干掉原来的元素,
实现:
1 <?php 2 echo getLastOne(6,2); 3 4 function getLastOne($n,$m){ 5 $arr=range(1,$n); 6 $i= 0; 7 while(count($arr)!=1){ 8 9 if(($i+1)%$m==0){ 10 unset($arr[$i]); 11 }else{ 12 $arr[]=$arr[$i]; //array_push()也是调用这个 13 unset($arr[$i]); 14 } 15 $i++; 16 } 17 return $arr[$i]; 18 }
引申:
(-)指定从第x个开始数.
1 $arr1 = array_slice($arr,0,$x); 2 $arr2 = array_slice($arr,$x); 3 foreach($arr1 as $k){ 4 $arr2[] = $k; 5 } 6 7 $arr=$arr2;
(=)递推优化
1 $i=0; 2 for($i=2;$i<=$m;$i++){ 3 $res=0; 4 $res=($i+$m)%$n; 5 } 6 return $res+1;
//反向递推
这玩意装b有用,最主要是会这种计算和优化的思想.像大量的算法主要是c和c++的底层实现,相对于php扁平化的敏捷开发,数据库才是瓶颈.
原文：http://www.cnblogs.com/liuyuxing/p/5003298.html