1.猴王算法
一群猴子排成一圈，按1，2，…，n依次编号。然后从第1只开始数，数到第m只,把它踢出圈，从它后面再开始数，再数到第m只，在把它踢出去…，如此不停的进行下去，直到最后只剩下一只猴子为止，那只猴子就叫做大王。要求编程模拟此过程，输入m、n, 输出最后那个大王的编号。
/**
* @param $m
* @param $n
* @return mixed
*
*/
private function monkeysKing($m, $n)
{
//创建猴群 - 1到n数组
$monkeys = range(1, $m);
//循环条件 - 猴子数量大于1
$i = 0;//数组下标
while (count($monkeys) > 1) {
//$i为数组下标;$i+1为猴子标号
//余数等于0表示正好第m个，删除，用unset删除保持下标关系
if (($i + 1) % $n == 0) {
unset($monkeys[$i]);
} else {
//如果余数不等于0，则把数组下标为$i的放最后，形成一个圆形结构,
array_push($monkeys, $monkeys[$i]);
//圆形结构，添加一个，就要去掉一个
unset($monkeys[$i]);
}
//$i 循环+1，不断把猴子删除，或 push到数组
$i++;
}
//猴子数量等于1时输出猴子标号，得出猴王
return current($monkeys);
}
2.牛群算法
有一头母牛，4岁可生育，每年生一头，所生均是母牛，到15岁绝育不再能生，20岁死亡。问n年后有多少头牛？
/**
* @param $y
* @return int
*/
function niu($y){
static $num= 1; //定义静态变量;初始化牛的数量为1
for ($i=1; $i <=$y ; $i++) {
if($i>=4 && $i<15){ //每年递增来算，4岁开始+1，15岁不能生育
$num++;
niu($y-$i); //递归方法计算小牛$num，小牛生长年数为$y-$i
}else if($i==20){
$num--; //20岁死亡减一
}
}
return $num;
}
3.杨辉三角
private function Triangle($n)
{
$arr = array();
$arr[1] = array_fill(0, 3, 0);
$arr[1][1] = 1;
echo str_pad(" ", $n * 12, " ");
printf("%3d", $arr[1][1]);
echo "<br/>";
for ($i = 2; $i <= $n; $i++) {
$arr[$i] = array_fill(0, ($i + 2), 0);
for ($j = 1; $j <= $i; $j++) {
if ($j == 1)
echo str_pad(" ", ($n + 1 - $i) * 12, " ");
printf("%3d", $arr[$i][$j] = $arr[$i - 1][$j - 1] + $arr[$i - 1][$j]);
echo " ";
}
echo "<br/>";
}
}
4.冒泡排序
/**
* @param $arr
* @return mixed
*
* 冒泡排序算法的原理如下：
* 1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
* 2.对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
* 3.针对所有的元素重复以上的步骤，除了最后一个。
* 4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
*/
private function bubbleSort($arr)
{
//获取 长度
$len = count($arr);
//循环比较（相邻的两个元素，比较，交换）
for ($k = 0; $k <= $len; $k++) {
for ($j = $len - 1; $j > $k; $j--) {
//比较
if ($arr[$j] < $arr[$j - 1]) {
//交换
$temp = $arr[$j];
$arr[$j] = $arr[$j - 1];
$arr[$j - 1] = $temp;
}
}
}
return $arr;
}
5.快速排序
/**
* @param $arr
* @return array
*
* 快速排序算法原理如下：
* 1.通过设置一个初始中间值，来将需要排序的数组分成3部分：小于中间值的左边，中间值，大于中间值的右边
* 2.继续递归用相同的方式来排序左边和右边
* 3.最后合并数组
*/
private function quickSort($arr)
{
//先判断要排序的数据是否符合要求
$length = count($arr);
if ($length <= 1) {
return $arr;
}
//选择一个数作为参照
$base_num = $arr[0];
//遍历除了参照外的所有元素，按照大小关系放入两个数组内
//初始化两个数组
$left_array = array();//存放大于参照的
$right_array = array();//存放小于参照的
//遍历分组
for ($i = 1; $i < $length; $i++) {
if ($base_num > $arr[$i]) {
$left_array[] = $arr[$i];
} else {
$right_array[] = $arr[$i];
}
}
//在分别对这两个数组进行递归处理
$left_array = $this->quickSort($left_array);
$right_array = $this->quickSort($right_array);
//合并数组并输出
return array_merge($left_array, array($base_num), $right_array);
}
6.二分查找算法（折半查找算法）
/**
* @param $x
* @param $a
* @return bool|int
*
* 二分查找,需要数组是一个有序数组
* 循环实现
*/
private function binLoop($x, $a)
{
$c = count($a);
$lower = 0;
$high = $c - 1;
while ($lower <= $high) {
//取中间值
$middle = intval(($lower + $high) / 2);//intval() 函数用于获取变量的整数值
//比较（一半一半的比）,必须是有序数组
if ($a[$middle] > $x) {
$high = $middle - 1;//在前一半里查
} elseif ($a[$middle] < $x) {
$lower = $middle + 1;//在后一半里查
} else {
return $middle;
}
}
return false;
}
/**
* @param $x
* @param $a
* @param $lower
* @param $high
* @return bool|int
*
* 二分查找,需要数组是一个有序数组
* 递归实现
*/
private function binRecursive($x, &$a, $lower = 0, $high = 11)
{
//$lower开始位置 $high结束位置
//采用二分法查找
$c = count($a);
if ($high > $c) {
return false;
}
if ($lower <= $high) {
$middle = intval(($lower + $high) / 2);
if ($a[$middle] == $x) {
return $middle;
} elseif ($a[$middle] < $x) {//在后半段里查
return $this->binSearchRecursive($x, $a, $middle + 1, $high);
} else {//在前半段里查
return $this->binSearchRecursive($x, $a, $lower, $middle - 1);
}
} else {
return false;
}
}
7.遍历一个文件下的所有文件和子文件夹下的文件
function AllFile($dir){
if($dh = opendir($dir)){
while (($file = readdir($dh)) !== false){
if($file !='..' && $file !='.'){
if(is_dir($dir.'/'.$file)){
AllFile($dir.'/'.$file); //如果判断还是文件，则递归
}else{
echo $file; //输出文件名
}
}
}
}
}
8.请写一段PHP代码，确保多个进程同时写入同一个文件成功
<?php
$fp = fopen("lock.txt","w+");
if (flock($fp,LOCK_EX)) {
//获得写锁，写数据
fwrite($fp, "write something");
// 解除锁定
flock($fp, LOCK_UN);
} else {
echo "file is locking...";
}
fclose($fp);
?>
9.无限级分类
function tree($arr,$pid=0,$level=0){
static $list = array();
foreach ($arr as $v) {
//如果是顶级分类，则将其存到$list中，并以此节点为根节点，遍历其子节点
if ($v['pid'] == $pid) {
$v['level'] = $level;
$list[] = $v;
tree($arr,$v['id'],$level+1);
}
}
return $list;
}
10.随机输入一个数字能查询到对应的数据区间
//把区间换成数组写法，用二分法查找区间
function binsearch($x,$a){
$c=count($a);
$lower=0;
$high=$c-1;
while($lower<=$high){
$middle=intval(($lower+$high)/2);
if($a[$middle]>=$x){
$high=$middle-1;
}elseif($a[$middle]<=$x ){
$lower=$middle+1;
}
}
return '在区间'.$a[$high].'到'.$a[$lower];
}
$array = ['1','50','100','150','200','250','300'];
$a = '120';
echo binsearch($a,$array);
网友评论