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