php常见算法题

//二分查找 
/**
 * @param $arr string 有序数组
 * @param $start int 起始位置
 * @param $end int 结束位置
 * @param $v int 查找的之
 * @return int
 */
function binarySearch($arr,$start,$end,$v){
    $mid=ceil(($start+$end)/2);
    $m=$arr[$mid];
    if ($v==$m){
        return $mid;
    }
    if ($v>$m){
        $start=$m;

    }

    if ($v<$m){
        $end=$m;
    }
    return binarySearch($arr,$start,$end,$v);

}

//快速排序法
$arr=array(12, 5,33,78,96,16, 8,57,62,33);
function quickSort($arr){
    if (count($arr)<=1){
        return $arr;
    }
    $refer=$arr[0];
    $left=[];
    $right=[];

    for ($i=1;$i<count($arr);$i++){
        if ($refer>$arr[$i]){
            $left[]=$arr[$i];
        }

        if ($refer<=$arr[$i]){
            $right[]=$arr[$i];
        }
    }
    $left=quickSort($left);

    $right=quickSort($right);

    return array_merge($left,[$refer],$right);

}

var_dump(quickSort($arr));
//冒泡排序
function bubbleSort($arr){
    for($i = 0,$length = count($arr);$i < $length;$i++){

        //内存循环
        for($j = 0;$j < ($length - $i - 1);$j++){
            //拿着j变量所对应的数组元素，与后面的元素进行比较
            if($arr[$j] > $arr[$j + 1]){
                //交换位置
                $temp              = $arr[$j];
                $arr[$j]           = $arr[$j+1];
                $arr[$j+1]         = $temp;
            }
        }
    }
return $arr;
}
//选择排序
$a = array(2,13,42,34,56,23,67,365,87665,54,68,3);

function bubbleSort($a){
    for ($i=0;$i<count($a);$i++){
        for ($j=$i+1;$j<count($a);$j++){
            if ($a[$j]>$a[$i]){
                $tmp=$a[$i];
                $a[$i]=$a[$j];
                $a[$j]=$tmp;
            }
        }
    }
    return $a;
}
$res=bubbleSort($a);
var_dump($res);

// 斐波那契数列
function fbnq($n){

    if ($n==1){
        return 1;
    }
    if ($n==2){
        return 1;
    }
    return fbnq($n-1)+fbnq($n-2);
}
echo fbnq(6);

// 斐波那契数列
function fbnq($n){
    $a[1]=1;
    $a[2]=1;
    for ($i=3;$i<=$n;$i++){
        $a[$i]= $a[$i-1]+$a[$i-2];
    }
    return $a;

}
var_dump(fbnq(6));
//猴子称王的问题
//猴子称王的问题 一共m个猴子，第n个被淘汰
function king($m,$n){
    $arr=range(1,$m);
    $i=0;
    while (count($arr)>1){
        if ($i%$n !=0){
            array_push($arr,$arr[$i-1]);
        }
        unset($arr[$i-1]);
        $i++;
    }
    return $arr;
}

var_dump(king(3,2));

//猴子称王的问题 一共m个猴子，第n个被淘汰 从第k个人开始数
function king($m,$n,$k){
    $arr1=range(1,$k-1);
    $arr2=range($k,$m);
    $arr=array_merge($arr2,$arr1);
    $i=0;
    while (count($arr)>1){
        if ($i%$n !=0){
            array_push($arr,$arr[$i-1]);
        }
        unset($arr[$i-1]);
        $i++;
    }
    return $arr;
}

var_dump(king(3,2,1));