网站PHP开发岗位应聘的解题思路


      前一阵子在面试阿里云的高级PHP开发岗,其中一次面试留了道算法题,要求用尽可能多的方法实现PHP的阶乘,并对比各种方法的优劣。最近所有面试都结束了,正好抽点时间写写博客,于是打算分享一下我的解题过程,后面抽空再分享WXG的七面面经。解题据本人了解,阶乘的实现方法一般可以分为三种,通常意义下的递归和循环各算一种,还有一大类通过一些巧妙的数学方法减少运算次数(尤其是乘法运算次数),进而优化计算效率。


如果要考虑到高精度、大整数的阶乘,对于PHP语言而言,情况会更复杂一些,比如使用BCMath扩展提供的一些方法时,显式的数字与字符串转换操作比较频繁。本文在只考虑n为整数的情况下,分别尝试实现上述的几种情况,每种情况给出可用的代码示例,并在文末附上几种方法的综合对比情况。普通递归实现首先是普通递归实现,根据递归的通用公式fact(n)=n*fact(n-1)很容易写出阶乘的计算代码。普通递归实现的优点在于代码比较简洁,和通用公式一样的过程使得代码容易理解。缺点则在于由于需要频繁地调用自身,需要大量的入栈出栈操作,整体的计算效率不高。


functionfact(int$n):int

{

if($n==0){

return1;

}

return$n*fact($n-1);

}

普通循环实现有些「动态规划」的味道,但由于中间态变量使用频率低,不需要额外存储空间,所以要比一般的动态规划算法简单。普通递归方法是自顶向下(由n到1)的计算过程,而普通循环是自底向上进行计算。因此相对而言,代码没有上述方法直观,但由于少了频繁的入栈出栈过程,计算效率会高一些。

functionfact(int$n):int

{

$result=1;

$num=1;

while($num<=$n){

$result=$result*$num;

$num=$num+1;

}

return$result;

}

自行实现的大整数阶乘,由于PHP中int类型的范围限制,上述两种方法最多只能精确计算到20的阶乘。如果只是考虑到20的阶乘的情况,那么用查表法实现会更快:事先计算好0-20的阶乘并存储到一个数组中,需要用时查询一次便可。为了能够适应大数的阶乘,得到精确的计算结果,本文基于「普通循环方法」进行改进,使用数组存储计算结果中的每一位(由低到高位),通过相乘进位的方式依次计算每一位的结果。不言而喻,本方法的优点在于可以适用于高精度的大数阶乘场合,缺点就是对于小数阶乘而言,计算过程复杂且速度慢。

分享: