2020-06-03 11:24:20     分类: Php
摘要: 算法

有些公司B格高,或者做一些特殊功能,例如搜索、发奖等就需要算法了。 不会点算法,就在笔试链条的末端了。

一、PHP编程实现求最大公约数 function maxDivisor($a, $b) { $n = max([$a, $b]); for($i=$n; $i>1; $i++) { if(is_int($a/$i)&&is_int($a/$i) { return $i; } } return 1; }

//辗转相除法 function maxDivisor2($a, $b) { if($a==0){ return $a; }else{ return maxDivisor2($b, ($a%b)); } }

//加减法求最大公约数 function maxDivisor3($a, $b) { if ($a == $b) { return $a; } elseif($a > $b) { $a = $a-$b; } else { $b = $b-$a; } return maxDivisor3($a, $b); }

二、请用PHP实现递归算法 递归算法就是自己调用自己,重点就是调用前要进行判断,不然会一直持续下去,PHP实现的话可以利用全局变量,静态变量以及参数传引用 //全局变量 $i = 0; function deepLoop(){ global $i; echo $i; $i++; if($i<10) { deepLoop(); } } deepLoop();

//利用静态变量 function deepLoop(){ static $i = 0; echo $i; $i++; if($i<10){ deepLoop(); } } deepLoop();

//利用参数传引用 function deepLoop(&$i=1) { echo $i; $i++; if($i<10){ deepLoop(); } }

三、请用PHP实现直接选择排序法 原理:首先在末排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后再从剩余未排序元素中继续选择最小(大)元素,然后放到已排序薛烈的末尾,以此类推,直到所有元素均排序完毕。

function selectSort($arr) { $temp = 0; for($i=0, $len=count($arr); i<$len-1; $i++) { //先假设序号$i就是最小值 $minValue = $arr[$i]; $minKey = $i; //那么最小值都要和后面的进行比较 for($n=$i+1; $n<$len; $n++) { if($minValue>$arr[$n]) { //和后面的值进行交换 $minValue = $arr[$n]; $minKey = $n; } } //进行交换 $temp = $arr[$i]; $arr[$i] = $arr[$minKey]; $arr[$minKey] = $temp; } return $arr; }

四、请用PHP实现冒泡排序法 原理: 重复地走访过要排序的数列,一次比较两个元素。如果他们的顺序错误就把他们交换过来。 function bubbleSort($arr) { $len = count($arr); for($i=1; $i<$len; $i++) { //该层循环用来控制每轮 冒出一个数 需要比较的次数 for($n=0; $n<$len-$i; $n++){ if($arr[$n]>$arr[$n+1]){ $temp = $arr[n+1]; $arr[$n+1] = $arr[$n]; $arr[$n] = $arr[$n+1]; } } } return $arr; }

五、请用PHP实现快速排序法 原理: 找到当前元素中任意一个元素(一般第一个元素),作为标准,新建两个空数组,遍历整个数组元素。如果遍历的元素比当前的元素要小,那么九放到左边的数组,否组就放到右边的数组,然后在对新数组进行同样的操作。因为符合递归原理,所以用递归实现。 function quickSort($arr) { $len = count($arr) ; //判断是否需要排序 if($len<=1){ return $arr; }

//选择一个标尺
//选择第一个元素
$baseItem = $arr[0];

//遍历除了标尺外的所有元素 按照大小关系分别存放在两个数组中
$leftArr = [];
$rightArr = [];
for($i=1; $i<$len; $i++){
    if($baseItem>$arr[$i]){
        //放入左边的数组
        $leftArr[] = $arr[i];
    }else{
        //放入右边的素组
        $rightArr[] = $arr[$i];
    }
}

//在分别对左边 右边 的数组进行相同的排序处理方式
//递归调用这个函数,并记录解雇
$leftArr = quickSort($leftArr);
$rightArr = quickSort($rightArr);

//合并左边 右边
return array_merge($leftArr, $baseItem, $rightArr);

}

六、请用PHP实现插入排序法 原理:从无序表中获取第一个元素,把它插入有序表的合适位置,使得有序表仍然有序。 function insertSort($arr) { //区分那部分是已经排序好的,那部分是没有排序的 //找到其中一个需要排序的元素 //这个元素就是从第二个元素开始,到最后一个元素都是这个需要排序的元素 //利用循环就可以标志出来 //i循环控制每次需要插入的元素,一旦需要插入元素就控制好了 //间接将数组分为两部分,小标小于当前的,是排序好的序列

$len = count($arr);
for($i=1; $i<$len; $i++) {
    //获得当前需要比较的元素值
    $temp = $arr[$i];

    //内层循环控制 比较并插入
    for($n=$i-1; $n>=0; $n--){
        if($temp<$arr[$n]){
             $arr[$n+1] = $arr[$n];
             $arr[n] = $temp;
        }else{
             break;
        }
    }
}

}

六、请用PHP输出号,使其成等腰三角形排列 等腰三角形的形状是



所以 <?php function draw($n){ //还要检测为是否大于0的正整数 for($i=0; $i<$n; $i++){ echo sprintf('%s%s ', str_repeat(' ', $n-$i-1), str_repeat('', $i2+1)); } } draw(10);

七、请PHP输出号,使其成为菱形排列 菱形的形状是




所以 <?php function draw($n) { //还有检测为是否大于0的正整数 //奇数是绘制不出来菱形的 if($n%2==0){ $n--; } $half = ($n+1)/2; for($i=0; $i<$half; $i++){ echo sprintf('%s%s ', str_repeat(' ', $half-$i-1), str_repeat('', $i2+1)); } for($i=$half-1; $i>0; $i--){ echo sprintf('%s%s ', str_repeat(' ', $half-$i), str_repeat('', $i*2-1)); } } draw(10);

八、请用PHP输出杨辉三角 简单的说杨辉三角就是每行每个数正好等于其上方数之和 function draw($n) { $arr =[]; //首先处理每行的首尾 都是1 for($i=0; $i<$n; $i++){ $arr[$i][0] = 1; $arr[$i][$i] = 1; } //去除第一位和最后一位的值 保留在数组中 for($i=2; $i<$n; $i++){ for($m=1; $m<$i; $m++){ $arr[$i][$m] = $arr[$i-1][$m-1] + $arr[$i-1][$m]; } } //print_r($arr);die(); //打印 for($i=0; $i<$n; $i++){ ksort($arr[$i]); echo sprintf('%s ',($n-$i-1)*30, ''.implode('', $arr[$i]).''); } } draw(22); 好吧,我是个完美主义者,我用了点html进行修饰.

九、用二分法在一个数组中查找你需要的元素 function search($arr, $k, $low=0, $high=0){ //判断数组元素的数量 //判断是否为第一次调用 if(count($arr)!=0 && $hign==0) {
$high = count($arr); }

//如果还存在剩余的数组
if($low<$high) {
    //取中间值
    $mid = intval(($low+$high)/2);
    if($arr[$mid] == $k) {
        return $arr[$mid];
    }elseif($arr[$mid] < $k){
        return search($arr, $k, $low, $mid-1);
    }else{
        return search($arr, $k, $low, $mid+1);
    }
}

return "不存在";

} 前提是你在调用前得给$mid排个升序

while循环二分法 function search($arr, $k){ $low = 0; $high = count($arr); $mid = -1; while( $low <= $high){ $mid = intval(($low+$high)/2); if($arr[$mid] == $search) { break; }elseif($arr[$mid])>$search){ $high = $mid-1; }else{ $high = $mid+1; } }

if($mid!=-1){
    return $arr[$mid];
}else{
    return "没有找到";
}

}

十、牛生牛: 有一头母牛,到4岁可以生育,所生均是一样的母牛,到15岁绝育,请问N年后可以生多少头母牛 用递归算法 function getCow($n){ static num = 1; for($i=1;$<$n;$i++){ //牛生小牛 if($>=4 && $i<15){ $num++; getCow($n-$i); } //牛死了 if($i==20){ $num--; } } }

十一、用顺序法在数组中查找你所需要的元素 顺序查找其实用遍历就好了 function search($arr, $val){ forearch($arr as $k=>$v){ return $v; } return "没找到"; }

十二、使用PHP实现一个双向队列 双向队列是指允许在一端(队尾)进行插入,而在另一端(队头)进行删除的线性表。Rear指针指向队维,front指针指向队头; class Deque{ private $queue = [];

public function addFirst($item){
     return array_unshift($this->queue, $item);
}

public function addLast($item) {
    return array_push($this->queue, $item);
}

public function removeFirst(){ return array_shift($this->queue); }

public function removeLast(){ return array_pop($this->queue); } }

十三、一群猴子排成一圈,按1,2,...,n依次编号。然后从第1只开始数,数到第m只,把它踢出圈,从它后面再开始数,再数到第m只,在把它踢出去...,如此不停的进行下去,直到最后只剩下一只猴子为止,那只猴子就叫做大王。要求编程模拟此过程,输入m、n,输出最后那个大王的编号。 function king($n, $m) { $monkey = range(1, $n); $i = 0; while(count($monkey) >1) { $i++; $head = array_shift($monkey); if($i % $m!=0){ array_push($monkey, $head); } return $monkey[0]; } }

十四、用二分法查找一个长度为10的排好序的线性表,查找不成功时最多需要比较次数是 最多需要4次

十五、从0,1,2,3,4,5,6,7,8,9,这十个数字中任意选出三个不同的数字,“三个数字中不含0和5”的概率是 7/15

十六、一个三角形三个顶点有3只老鼠,一声枪响,3只老鼠开始沿三角形的边匀速运动,请问他们相遇的概率是 75%,每只老鼠都有顺时针、逆时钟两种运动方向,3只老鼠共有8种运动情况,只有当3只老鼠都为顺时针或者逆时钟,它们才不会相遇,剩余的6中情况都会相遇,故相遇的概率为6/8=75%。

十七、我们希望开发一款扑克游戏,请给出一套洗牌算法,公平的洗牌并将洗好的牌存储在一个整形数组里。 $card_num = 54;//牌数 function wash_card($card_num){ $cards = $tmp = array(); for($i = 0;$i < $card_num;$i++){ $tmp[$i] = $i; } for($i = 0;$i < $card_num;$i++){ $index = rand(0,$card_num-$i-1); $cards[$i] = $tmp[$index]; unset($tmp[$index]); $tmp = array_values($tmp); } return $cards; }

十八、请用PHP数组实现栈结构 栈是一种后进先出的线性数据结构,只允许在一端进行插入和删除操作,允许操作的一端称为栈顶,另一端就是栈底; 用PHP数组模拟就需要在数组的尾部进行插入, 并从数组的尾部进行删除,这样数组的尾部就是栈顶, 数组的头部就是栈底,就实现了插入数据会将数据压入栈底,删除就从栈顶删除; class Stack { /**

  • 存放栈的数组
  • @var array */ private $stack; /**
  • 栈的长度
  • @var integer */ private $size; /**
  • 构造方法 - 初始化数据 */ public function __construct() { $this-> stack = []; $this->size = 0; } /**
  • 入栈操作
  • @param mixed $data
  • @return object 返回对象本身 */ public function push($data) { $this->stack[$this->size++] = $data; return $this; } /**
  • 出栈操作
  • @return mixed 空栈返回false , 否则返回顶端元素 */ public function pop() { if(! $this->isEmpty()){ $top = array_splice($this->stack, --$this->size, 1); return $top[0]; } return false; } /**
  • 获取栈
  • @return array @stack */ public function getStack(){ return $this->stack; } /**
  • 获取栈顶元素
  • @return mixed */ public function getTop(){ if($this->isEmpty()){ return $this->stack[$this->size-1]; } return false; } /**
  • 获取栈的长度
  • @return integer $size */ public function getSize(){ return $this->size; } /**
  • 检测栈是否为空
  • @return boolean */ public function isEmpty(){ return 0 === $this->size; } }

十九、请用PHP数组实现队列结构 队列时一种特殊的先进先出的线性表,只能在前端进行删除操作,称为队头,在后端进行插入操作,称为队尾。PHP数组模拟队列的要点就是在数组末尾插入, 在数组头部删除,就能做到先进先出了。 class Queue{ /**

  • 存储队列的数组
  • @var array */ private $queue; /**
  • 队列的长度
  • @var integer */ private $size; /**
  • 构造方法 - 初始化数据 */ public function __construct() { $this->queue = []; $this->size = 0; } /**
  • 入队操作
  • @param mixed $data
  • @return object 返回对象本身 */ public function enqueue($data){ $this->queue[$this->size++] = $data; return $this; } /**
  • 出队操作
  • @return mixed 空队列时返回false 非空返回队头元素 */ public function dequeue(){ if(!$this->isEmpty()){ -- $this->szie; $front = array_splice($this->queue, 0, 1); return $front[0]; } return false; } /**
  • 获取队列
  • @return array $queue */ public function getQueue(){ return $this->queue; } /**
  • 获取队头元素
  • @return mixed 队列为空返回false 否则返回队头元素 */ public function getFront(){ if(!$this->isEmpty()){ return $this->queue[0]; } return false; } /**
  • 获取队列大小
  • @return integer */ public function getSize(){ return $this->size; } /**
  • 检查队列是否为空
  • @return boolean */ public function isEmpty(){ return 0 === $this->size; } }

二十、用PHP实现一个单向链表 单向链表是一个链式数据结构,它有一个表头,所有的节点都是其后继节点; //链表节点类 class node { /**

  • 节点id
  • @var integer */ private $id; /**
  • 节点名称
  • @var string */ private $name; /**
  • 下一节点
  • @var node */ private $next; /**
  • 构造函数 - 初始化数据
  • @param int $id
  • @param string $name */ public function __construct($id, $name, $next) { $this->id = $id; $this->name = $name; $this->next = null; } /**
  • 获取节点id
  • @return integer $id */ public function getId(){ return $this->id; } /**
  • 设置节点id
  • @param int $id */ public function setId($id){ $this->id = $id; } /**
  • 返回节点名称
  • @return string $name */ public function getName(){ return $this->name; } /**
  • 设置节点名称
  • @param string $name */ public function setName($name){ $this->name = $name; } /**
  • 返回下一节点
  • @return node $next */ public function getNext(){ return $this->next; } /**
  • 设置下一节点
  • @param node $next */ public function setNext($next){ $this->next = $next; } } //链表类 class SingleLinkList { /**
  • 链表头节点
  • @var node */ private $header; /**
  • 链表长度
  • @var integer */ private $size; /**
  • 构造方法 - 初始化数据
  • @param null $id
  • @param null $name */ public function __construct($id=null, $name=null) { $this->header = new node($id, $name, null); $this->size = 0; } /**
  • 添加节点
  • @param $node
  • @return bool 是否成功 */ public function addNode($node){ $current = $this->header; $repeat = false; $insertPrev = null; while ($current->getNext() != null){ //判断标识是否重复 if($node->getId() == $current->getId()){ $repeat = true; break; } //如果添加的节点设置了next 且next等于下一节点 则设置插入点 否则继续循环追加 if($node->getNext() != null && $node->getNext()->getId() == $current->getNext()->getId()){ $insertPrev = $current; } $current = $current->getNext(); } if(!$repeat) return false; if($insertPrev != null){ $node->setNext($insertPrev->getNext()); $insertPrev->setNext($node); }else{ $current->setNext($node); } ++$this->size; return true; } /**
  • 删除节点
  • @param $id
  • @return bool 是否成功 */ public function deleteNode($id){ $current = $this->header; $find = false; while ($current->getNext() != null){ if($current->getNext()->getId() == $id){ $find = true; break; } } if($find){ --$this->size; $current->setNext($current->getNext()->getNext()); } return $find; } /**
  • 判断链表是否为空
  • @return bool */ public function isEmpty(){ return 0===$this->size; } /**
  • 清空链表 */ public function clear(){ $this->header = null; } /**
  • 获取表头
  • @return node */ public function getHeader(){ return $this->header; } /**
  • 通过ID获取链表
  • @param $id
  • @return node */ public function getNodeById($id){ $current = $this->header; while($current != null){ if($current->getId() == $id){ break; } $current = $current->getNext(); } return $current; } /**
  • 获取链表长度
  • @return int $size */ public function getSize(){ return $this->size; } }

二十一、用PHP实现双向链表 双向链表和单向链表大同小异,还是从一个表头开始的,只不过双向链表除了有下一节点,还有上一节点, 也就是prev, 实现起来和单向链表差不多,胖子写累了,就不写了。

二十二、用PHP实现固定红包算法 好吧,这不算一个算法题,固定红包吗,有几个人发几个红包,唯一值得注意的是精度问题,如果不能整除怎么办?终究有一个要多拿或少拿钱的。 假设精度为小数后2位, 最后一个人少拿钱 //amount是总金额 //total是总人数 function giveYouMoney($amount, $total){ //已收到的人数 static $receive = 1; //已发出的金额 static $send = 0.00; $amount += 0.00; if($receive > $total) { echo '你来晚了,钱已发完! '; }elseif ($receive == $total){ //把剩余的钱都给最后一个人 $money = $amount - $send; echo sprintf('你是第 %s 个领取红包的人,你领到了 ¥%s元 ', $receive, $money); $receive++; $send += $money; }else{ //不能整除就尽量平均 $money = ($amount - $send)/($total-$receive+1); $money = round($money, 2); echo sprintf('你是第 %s 个领取红包的人,你领到了 ¥%s元 ', $receive, $money); $receive++; $send += $money; } } //10块钱发7份,8个人领取 giveYouMoney(10,7); giveYouMoney(10,7); giveYouMoney(10,7); giveYouMoney(10,7); giveYouMoney(10,7); giveYouMoney(10,7); giveYouMoney(10,7); giveYouMoney(10,7); 前面6个人都是1.43 最后一个是1.42

二十三、用PHP简单实现随机红包算法 /**

  • @param $amount 总金额
  • @param $total 总个数
  • @param $money 剩余的钱
  • @param $size 剩余的个数 / function getRandomMoney($amount, $total, &$money, &$size){ if($size == 0){ echo '你来晚了,所有的钱都发光了! '; }elseif ($size==1){ $money = round($money, 2); echo sprintf('你是第 %s 个领取红包的人, 你领到了 ¥%s元 ', $total-$size+1, $money); $size = 0; $money = 0; }else{ $min = 0.01; $max = $money/$size2; $r = mt_rand()/mt_getrandmax(); $per = $max*$r; $per = $per<$min? $min : $per; $per = round($per,2); echo sprintf('你是第 %s 个领取红包的人, 你领到了 ¥%s元 ', $total-$size+1, $per); $size--; $money -= $per; } } $amount = 10; $total = 7; $money = $amount; $size = $total; getRandomMoney($amount, $total, $money, $size); getRandomMoney($amount, $total, $money, $size); getRandomMoney($amount, $total, $money, $size); getRandomMoney($amount, $total, $money, $size); getRandomMoney($amount, $total, $money, $size); getRandomMoney($amount, $total, $money, $size); getRandomMoney($amount, $total, $money, $size); getRandomMoney($amount, $total, $money, $size);

二十四、发一个随机红包,100块钱给10个人。每个人最多12块钱,最少6块钱。怎么分? <?php function hongbao($money, $people, $min, $max) { $result = []; for ($i=0; $i < $people; $i++) { do { // 1.进行本次分配 $result[$i] = mt_rand($min100, $max100) / 100; // 2.本次分配后,剩余人数 $restPeople = $people - ($i+1);
// 3.本次分配后,剩余金钱 $restMoney = $money - array_sum(array_slice($result, 0, $i+1)); // 4.本次分配后,剩余金钱是否在合理范围? 不在则重新分配 } while ($restMoney > $restPeople $max || $restMoney < $restPeople $min); } return $result; } $result = hongbao(100, 10, 6, 12); // 验证 var_dump($result); var_dump(array_sum($result));


文章标签: