常见算法 - PHP

求一个数组中序列连续数的最大值

$maxsum) {$maxsum=$thissum;}elseif ($thissum<0) {$thissum=0;}
}
echo $maxsum;
?>

求一个字符串最长连续不重复的子串

 strlen($max)) {$max = $tmp;}}return $tmp;}

杨辉三角

/*** 第一种代码实现* @param int $n 要求的层数* 理解思路：   $i代表行数; $j代表列数*/public function funYH($n = 1){//初始化数组$arr = [];for($i = 0;$i < $n;$i++){//注意循环条件for($j = 0;$j <= $i;$j++){if($j == 0 || $i == $j){$arr[$i][$j] = 1;}else {$arr[$i][$j] = $arr[$i-1][$j-1]+$arr[$i-1][$j];}echo $arr[$i][$j]."\t";}echo "
";}}

1、一群猴子排成一圈，按1，2，…，n依次编号。然后从第1只开始数，数到第m只,把它踢出圈，从它后面再开始数，再数到第m只，在把它踢出去…，如此不停的进行下去，直到最后只剩下一只猴子为止，那只猴子就叫做大王。要求编程模拟此过程，输入m、n, 输出最后那个大王的编号。

function get_rand($proArr) {  $result = '';//概率数组的总概率精度$proSum = array_sum($proArr);//概率数组循环foreach ($proArr as $key => $proCur) {$randNum = mt_rand(1, $proSum);if ($randNum <= $proCur) {$result = $key;break;} else {$proSum -= $proCur;}}unset ($proArr);return $result;
} /*** 其中id表示中奖等级，prize表示奖品，v表示中奖概率。注意其中的v必须为整数，你可以将对应的奖项的v设置成0，即意味着该奖项抽中的几率是0，数组中v的总和(基数)，基数越大越能体现概率的准确性。本例中v的总和为100，那么平板电脑对应的中奖概率就是1%，如果v的总和是10000，那中奖概率就是万分之一了。*/
$prize_arr = array(  
'0' => array('id'=>1,'prize'=>'平板电脑','v'=>1),  
'1' => array('id'=>2,'prize'=>'数码相机','v'=>5),  
'2' => array('id'=>3,'prize'=>'音箱设备','v'=>10),  
'3' => array('id'=>4,'prize'=>'4G优盘','v'=>12),  
'4' => array('id'=>5,'prize'=>'10Q币','v'=>22),  
'5' => array('id'=>6,'prize'=>'下次没准就能中哦','v'=>50),  
); 

4.冒泡排序

function maopao($arr){$len = count($arr); for($k=0; $k<$len-1; $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.快速排序

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 = quickSort($left_array);$right_array = quickSort($right_array);//合并return array_merge($left_array, array($base_num), $right_array);
}

6.二分查找算法（折半查找算法）

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;} else{return $middle;}}return false;
}

8.字符集合：输入一个字符串，求出该字符串包含的字符集合，并按顺序排序（英文）

function set($str){//转化为数组$arr = str_split($str);//去除重复$arr = array_flip(array_flip($arr));//排序sort($arr);//返回字符串return implode('', $arr);
}

9.遍历一个文件下的所有文件和子文件夹下的文件

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;            //输出文件名}}} }
}

10.从一个标准的Url提取出文件的扩展名

function getExt($url){$arr = parse_url($url);$file = basename($arr['path']);// basename函数返回路径中的文件名部分$ext = explode('.', $file);return $ext[count($ext)-1];}

11.有个人想上一个n级的台阶，每次只能迈1级或者迈2级台阶，问：这个人有多少种方法可以把台阶走完？例如：总共3级台阶，可以先迈1级再迈2级，或者先迈2级再迈1级，或者迈3次1级总共3中方式

/**
* 斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda *Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、*13、21、34、……在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-*1)+F(n-2)（n>=3，n∈N*）
*/
function jieti($num){    //实际上是斐波那契数列return $num < 2 ? 1 : jieti($num-1) + jieti($num-2);
}

12.请写一段PHP代码，确保多个进程同时写入同一个文件成功

13.无限级分类

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;
}

14.获取上个月第一天 和 最后一天

//获取上个月第一天date('Y-m-01',strtotime('-1 month'));//获取上个月最后一天date('Y-m-t',strtotime('-1 month'));

18 用PHP实现一个双向队列

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);}
}
?>

21 洗牌算法

【程序1】   题目：古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第四个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？   

1.程序分析：   兔子的规律为数列1,1,2,3,5,8,13,21....   

2  就是第三个数是前两个数字的和,既是经典的菲波那切数列

    function actionFblist($n){// 1,1,2,3,5,8,13// $n 为第n个月$arr = [1,1];if($n < 2)return false;for ($i=2;$i<=$n+1;$i++){$arr[$i] = $arr[$i-1] + $arr[$i-2];}var_dump($arr);echo $arr[$n+1];}

【程序2】   题目：判断101-200之间有多少个素数，并输出所有素数。   
1.程序分析：判断素数的方法：用一个数分别去除2到n-1，如果能被整除，   
则表明此数不是素数，反之是素数。  

public function actionIsPrimeNumber()
{$arr = [];for ($i=101;$i<=200;$i++){$flag = true;for ($j = 2;$j < $i;$j++){if($i % $j == 0){$flag = false;}}if($flag == true)$arr[] = $i;}var_dump($arr);
}

【程序3】   题目：打印出所有的 "水仙花数 "，所谓 "水仙花数 "是指一个三位数，其各位数字立方和等于该数本身。例如：153是一个 "水仙花数 "，因为153=1的三次方＋5的三次方＋3的三次方。   

1.程序分析：利用for循环控制100-999个数，每个数分解出个位，十位，百位。   

public function actionWaterFlower()
{$re = [];for($i = 100;$i<= 999;$i++){$hundred = floor($i / 100 );     // 获取百位数字$ten = floor(($i %100 ) / 10 );  // 获取十位数字$one = floor($i % 100 % 10);     // 获取各位数字if((pow($hundred,3)  + pow($ten,3) + pow($one,3) ) == $i ){$re[] = $i;}}var_dump($re);}

【程序5】   题目：求s=a+aa+aaa+aaaa+aa...a的值，其中a是一个数字。例如2+22+222+2222+22222(此时共有5个数相加)，几个数相加有键盘控制。   

1.程序分析：关键是循环获得计算出每一项的值。

2. 可以使用php的str_repeat函数  

  public function actionRepeatN(){$a = 8;$n = 8;$sum = 0;for ($i = 0;$i<$n;$i++){$num = 0;for ($j = 0;$j<=$i;$j++){$num += $a* pow(10,$j);}$sum += $num;}var_dump($sum);}

【程序6】题目：一个整数，它加上100后是一个完全平方数，加上168又是一个完全平方数，请问该数是多少？   

1.程序分析：在10万以内判断，先将该数加上100后再开方，再将该数加上168后再开方，如果开方后的结果满足如下条件，即是结果。

public function actionWhitchNum()
{for ($i=1;$i<=100000;$i++){if(pow((int)sqrt($i+100),2) == ($i+100) &&pow((int)sqrt($i+168),2) == ($i+168) ){echo $i;}}echo 'ok';
}

【程序9】 题目：输出9*9口诀。   
1.程序分析：分行与列考虑，共9行9列，i控制行，j控制列。   

public function actionMultiplicationTable()
{for ($i=1;$i<=9;$i++){for ($j=1;$j<=$i;$j++){echo $j . '*' .$i .'=' . $i*$j;echo ' ';}echo "
";}
}

【程序10】   题目：有一分数序列：2/1，3/2，5/3，8/5，13/8，21/13...求出这个数列的前20项之和。   
1.程序分析：请抓住分子与分母的变化规律。  

public function actionAddFraction()
{$sum = 0;$numerator = [2,3];$denominator = [1,2];// 根据规律获得所有的分子和分母for ($i=2;$i<20;$i++){$numerator[$i] = $numerator[$i-2] + $numerator[$i-1];$denominator[$i] = $denominator[$i-2] + $denominator[$i-1];}// 获得分数的前n项和for ($i=0;$i<20;$i++){$sum += $numerator[$i] / $denominator[$i];}var_dump($sum);
}

【程序11】   题目：求1+2!+3!+...+20!的和   
1.程序分析：此程序只是把累加变成了累乘。   

public function actionAddFactorial()
{$n = 20;$sum = 0;for ($i=1;$i<=$n;$i++){$num = 1;for ($j=1;$j<=$i;$j++){$num = $j*$num;}$sum += $num;}var_dump($sum);
}

【程序12】   题目：利用递归方法求5!。   
1.程序分析：递归公式：fn=fn_1*4!   

public function numFactorial($n)
{if($n>1)return $sum = $n * $this->numFactorial($n-1);   // 需要注意这点,若是写成函数要替换成函数形式elsereturn $n;
}
public function actionNumFactorial()
{$n =4;$sum =  $this->numFactorial($n);                   // 调用上面的阶乘方法(函数)
}

【程序13】   题目：有5个人坐在一起，问第五个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第三个人，又说比第2人大两岁。问第2个人，说比第一个人大两岁。最后问第一个人，他说是10岁。请问第五个人多大？   

1.程序分析：利用递归的方法，递归分为回推和递推两个阶段。要想知道第五个人岁数，需知道第四人的岁数，依次类推，推到第一人（10岁），再往回推。   

public function myAge($n)
{if($n == 1)return $age = 10;elsereturn 2 + $this->myAge($n-1);
}public function actionMyAge1()
{$n = 5;echo $this->myAge($n);
}

【程序14】   题目：给一个不多于5位的正整数，要求：一、求它是几位数，二、逆序打印出各位数字。 

public function actionIntLength()
{$num = 1232345;$num = (string) $num;$length = strlen($num);$numstring = '';for ($i=$length-1;$i>=0;$i--){$numstring .= $num[$i];}echo $numstring;
}

【程序15】   题目：一个5位数，判断它是不是回文数。即12321是回文数，个位与万位相同，十位与千位相同。   

public function actionIsPalindromeNumber()
{$num = 12321;$num = (string) $num;if($num[0] == $num[4] && $num[1] == $num[3])var_dump('Is Palindrome Number');elseecho 'false';
}/** 找到所有的5位的回文数* */
public function actionAllPalindromeNumber()
{$result = [];for ($i=10000;$i<99999;$i++){$i = (string) $i;if($i[0] == $i[4] && $i[1] == $i[3])$result[] = $i;}var_dump($result);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！