这篇文章主要向大家介绍php算法 php算法,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。
- 一、首先来画个菱形玩玩,不少人学C时在书上都画过,我们用PHP画下,画了一半。
思路:多少行for一次,而后在里面空格和星号for一次。php
<?php
for ( $i =0; $i <=3; $i ++){
echo str_repeat ( " " ,3- $i );
echo str_repeat ( "*" , $i *2+1);
echo '<br/>' ;
}
二、冒泡排序,C里基础算法,从小到大对一组数排序。html 思路:这题从小到大,第一轮排最小,第二轮排第二小,第三轮排第三小,依次类推……算法
- <?php
- $arr = array (1,3,5,32,756,2,6);
- $len = count ( $arr );
- for ( $i =0; $i < $len -1; $i ++){
- for ( $j = $i +1; $j < $len ; $j ++){
- if ( $arr [ $i ]> $arr [ $j ]){ //从小到大
- $p = $arr [ $i ];
- $arr [ $i ] = $arr [ $j ];
- $arr [ $j ]= $p ;
- }
- }
- }
- var_dump( $arr );
复制代码
三、杨辉三角,用PHP写。shell
思路:每一行的第一位和最后一位是1,没有变化,中间是前排一位与左边一排的和,这种算法是用一个二维数组保存, 另外有种算法用一维数组也能够实现,一行 一行的输出,有兴趣去写着玩下。 数组
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1工具
- <?php
- //每行的第一个和最后一个都为1,写了6行
- for ( $i =0; $i <6; $i ++) {
- $a [ $i ][0]=1;
- $a [ $i ][ $i ]=1;
- }
- //出除了第一位和最后一位的值,保存在数组中
- for ( $i =2; $i <6; $i ++) {
- for ( $j =1; $j < $i ; $j ++) {
- $a [ $i ][ $j ] = $a [ $i -1][ $j -1]+ $a [ $i -1][ $j ];
- }
- }
- //打印
- for ( $i =0; $i <6; $i ++){
- for ( $j =0; $j <= $i ; $j ++) {
- echo $a [ $i ][ $j ]. ' ' ;
- }
- echo '<br/>' ;
- }
复制代码
四、在一组数中,要求插入一个数,按其原来顺序插入,维护原来排序方式。post
思路:找到比要插入数大的那个位置,替换,而后把后面的数后移一位。测试
- <?php
- $in = 2;
- $arr = array (1,1,1,3,5,7);
- $n = count ( $arr );
- //若是要插入的数已经最大,直接打印
- if ( $arr [ $n -1] < $in ) {
- $arr [ $n +1] = $in ; print_r( $arr );
- }
- for ( $i =0; $i < $n ; $i ++) {
- //找出要插入的位置
- if ( $arr [ $i ] >= $in ){
- $t1 = $arr [ $i ];
- $arr [ $i ] = $in ;
- //把后面的数据后移一位
- for ( $j = $i +1; $j < $n +1; $j ++) {
- $t2 = $arr [ $j ];
- $arr [ $j ] = $t1 ;
- $t1 = $t2 ;
- }
- //打印
- print_r( $arr );
- die ;
- }
- }
复制代码
五、对一组数进行排序(快速排序算法)。ui
思路:经过一趟排序分红两部分,而后递归对这两部分排序,最后合并。url
- <?php
- function q( $array ) {
- if ( count ( $array ) <= 1) { return $array ;}
- //以$key为界,分红两个子数组
- $key = $array [0];
- $l = array ();
- $r = array ();
- //分别进行递归排序,而后合成一个数组
- for ( $i =1; $i < count ( $array ); $i ++) {
- if ( $array [ $i ] <= $key ) { $l [] = $array [ $i ]; }
- else { $r [] = $array [ $i ]; }
- }
- $l = q( $l );
- $r = q( $r );
- return array_merge ( $l , array ( $key ), $r );
- }
- $arr = array (1,2,44,3,4,33);
- print_r( q( $arr ) );
复制代码
六、在一个数组查找你所需元素(二分查找算法)。
思路:以数组中某个值为界,再递归进行查找,直到结束。
- <?php
- function find( $array , $low , $high , $k ){
- if ( $low <= $high ){
- $mid = intval (( $low + $high )/2);
- if ( $array [ $mid ] == $k ){
- return $mid ;
- } elseif ( $k < $array [ $mid ]){
- return find( $array , $low , $mid -1, $k );
- } else {
- return find( $array , $mid +1, $high , $k );
- }
- }
- die ( 'Not have...' );
- }
- //test
- $array = array (2,4,3,5);
- $n = count ( $array );
- $r = find( $array ,0, $n ,5)
复制代码
七、合并多个数组,不用array_merge(),题目来于论坛。
思路:遍历每一个数组,从新组成一个新数组。
- <?php
- function t(){
- $c = func_num_args()-1;
- $a = func_get_args();
- //print_r($a);
- for ( $i =0; $i <= $c ; $i ++){
- if ( is_array ( $a [ $i ])){
- for ( $j =0; $j < count ( $a [ $i ]); $j ++){
- $r [] = $a [ $i ][ $j ];
- }
- } else {
- die ( 'Not a array!' );
- }
- }
- return $r ;
- }
- //test
- print_r(t(range(1,4),range(1,4),range(1,4)));
- echo '<br/>' ;
- $a = array_merge (range(1,4),range(1,4),range(1,4));
- print_r( $a );
复制代码
八、牛年求牛:有一母牛,到4岁可生育,每一年一头,所生均是同样的母牛,到15岁绝育,再也不能生,20岁死亡,问n年后有多少头牛。(来自论坛)
- <?php
- function t( $n ) {
- static $num = 1
- for ( $j =1; $j <= $n ; $j ++){
- if ( $j >=4 && $j <15) { $num ++;t( $n - $j );}
- if ( $j ==20){ $num --;}
- }
- return $num ;
- }
- //test
- echo t(8);
复制代码
====================其余算法=========================
冒泡排序 (bubble sort) — O(n2)
- $data = array (3,5,9,32,2,1,2,1,8,5);
- dump( $data );
- BubbleSort( $data );
- dump( $data );
- function BubbleSort(& $arr )
- {
- $limit = count ( $arr );
- for ( $i =1; $i < $limit ; $i ++)
- {
- for ( $p = $limit -1; $p >= $i ; $p --)
- {
- if ( $arr [ $p -1] > $arr [ $p ])
- {
- $temp = $arr [ $p -1];
- $arr [ $p -1] = $arr [ $p ];
- $arr [ $p ] = $temp ;
- }
- }
- }
- }
- function dump( $d )
- {
- echo '<pre>' ;
- print_r( $d );
- echo '</pre>' ;
- }
复制代码
插入排序 (insertion sort)— O(n2)
- $data = array (6,13,21,99,18,2,25,33,19,84);
- $nums = count ( $data )-1;
- dump( $data );
- InsertionSort( $data , $nums );
- dump( $data );
- function InsertionSort(& $arr , $n )
- {
- for ( $i =1; $i <= $n ; $i ++ )
- {
- $tmp = $arr [ $i ];
- for ( $j = $i ; $j >0 && $arr [ $j -1]> $tmp ; $j -- )
- {
- $arr [ $j ] = $arr [ $j -1];
- }
- $arr [ $j ] = $tmp ;
- }
- }
- function dump( $d )
- {
- echo '<pre>' ;print_r( $d ); echo '</pre>' ;
复制代码
希 尔排序 (shell sort)— O(n log n)
- $data = array (6,13,21,99,18,2,25,33,19,84);
- $nums = count ( $data );
- dump( $data );
- ShellSort( $data , $nums );
- dump( $data );
- function ShellSort(& $arr , $n )
- {
- for ( $increment = intval ( $n /2); $increment > 0; $increment = intval ( $increment /2) )
- {
- for ( $i = $increment ; $i < $n ; $i ++ )
- {
- $tmp = $arr [ $i ];
- for ( $j = $i ; $j >= $increment ; $j -= $increment )
- if ( $tmp < $arr [ $j - $increment ] )
- $arr [ $j ] = $arr [ $j - $increment ];
- else
- break ;
- $arr [ $j ] = $tmp ;
- }
- }
- }
- function dump( $d )
- {
- echo '<pre>' ;print_r( $d ); echo '</pre>' ;
- }
复制代码
快 速排序 (quicksort)— O(n log n)
- $data = array (6,13,21,99,18,2,25,33,19,84);
- dump( $data );
- quicks( $data ,0, count ( $data )-1);
- dump( $data );
- function dump( $data ){
- echo '<pre>' ;print_r( $data ); echo '</pre>' ;
- }
- function QuickSort(& $arr , $left , $right )
- {
- $l = $left ;
- $r = $right ;
- $pivot = intval (( $r + $l )/2);
- $p = $arr [ $pivot ];
- do
- {
- while (( $arr [ $l ] < $p ) && ( $l < $right ))
- $l ++;
- while (( $arr [ $r ] > $p ) && ( $r > $left ))
- $r --;
- if ( $l <= $r )
- {
- $temp = $arr [ $l ];
- $arr [ $l ] = $arr [ $r ];
- $arr [ $r ] = $temp ;
- $l ++;
- $r --;
- }
- }
- while ( $l <= $r );
- if ( $left < $r )
- QuickSort(& $arr , $left , $r );
- if ( $l < $right )
- QuickSort(& $arr , $l , $right );
- }
复制代码
=================================================
冒泡排序:两两交换数值,最小的值在最左边,就如最轻的气泡在最上边。对整列数两两交换一次,最小的数在最左边,每次都能得一个在剩下的数中的最小 的数,“冒”出来的数组成一个有序区间,剩下的值组成一无序区间,且有序区间中每一元素值都比无序区间的小。
快速排序:基准数,左右二个数组,递归调用,合并。
插入排序:排序区间分红二部分,左边有序,右边无序,从右区间取 第一个元素插入左区间,若此元素比左边区间最右边的元素大,留在原处,若此元素比左 边区间最右边的元素小,则插在最右边元素的原位置,同时最右边元素右移一位,计算器减一,从新和前面的元素比较,直到前面的元素比要插入元素小为止,重复 上述步骤。
注意区间端点值的处理,及数组的第一个元素下标为0.
- <?php
- //PHP经常使用排序算法
- function bubblesort ( $array )
- {
- $n = count ( $array );
- for ( $i = 0; $i < $n ; $i ++)
- {
- for ( $j = $n - 2; $j >= $i ; $j --) //[0,i-1] [i,n-1]
- {
- if ( $array [ $j ] > $array [ $j + 1])
- {
- $temp = $array [ $j ];
- $array [ $j ] = $array [ $j + 1];
- $array [ $j + 1] = $temp ;
- }
- }
- }
- return $array ;
- }
- $array = array (3,6,1,5,9,0,4,6,11);
- print_r (bubblesort ( $array ));
- echo '<hr>' ;
- function quicksort ( $array )
- {
- $n = count ( $array );
- if ( $n <= 1)
- {
- return $array ;
- }
- $key = $array [ '0' ];
- $array_r = array ();
- $array_l = array ();
- for ( $i = 1; $i < $n ; $i ++)
- {
- if ( $array [ $i ] > $key )
- {
- $array_r [] = $array [ $i ];
- }
- else
- {
- $array_l [] = $array [ $i ];
- }
- }
- $array_r = quicksort ( $array_r );
- $array_l = quicksort ( $array_l );
- $array = array_merge ( $array_l , array ( $key ), $array_r );
- return $array ;
- }
- print_r (quicksort ( $array ));
- echo '<hr>' ;
- function insertsort ( $array )
- {
- $n = count ( $array );
- for ( $i = 1; $i < $n ; $i ++) //[0,i-1] [i,n]
- {
- $j = $i - 1;
- $temp = $array [ $i ];
- while ( $array [ $j ] > $temp )
- {
- $array [ $j + 1] = $array [ $j ];
- $array [ $j ] = $temp ;
- $j --;
- }
- }
- return $array ;
- }
- print_r (insertsort ( $array ));
- ?>
复制代码
=======================================
复制代码 ?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
* 排列组合
* 采用二进制方法进行组合的选择,如表示5选3时,只需有3位为1就能够了,因此可获得的组合是 01101 11100 00111 10011 01110等10种组合
*
* @param 须要排列的数组 $arr
* @param 最小个数 $min_size
* @return 知足条件的新数组组合
*/
function pl( $arr , $size =5) {
$len = count ( $arr );
$max = pow(2, $len );
$min = pow(2, $size )-1;
$r_arr = array ();
for ( $i = $min ; $i < $max ; $i ++){
$count = 0;
$t_arr = array ();
for ( $j =0; $j < $len ; $j ++){
$a = pow(2, $j );
$t = $i & $a ;
if ( $t == $a ){
$t_arr [] = $arr [ $j ];
$count ++;
}
}
if ( $count == $size ){
$r_arr [] = $t_arr ;
}
}
return $r_arr ;
}
$pl = pl( array (1,2,3,4,5,6,7),5);
var_dump( $pl );
//递归算法
//阶乘
function f( $n ){
if ( $n == 1 || $n == 0){
return 1;
} else {
return $n *f( $n -1);
}
}
echo f(5);
//遍历目录
function iteral( $path ){
$filearr = array ();
foreach ( glob ( $path . '\*' ) as $file ){
if ( is_dir ( $file )){
$filearr = array_merge ( $filearr ,iteral( $file ));
} else {
$filearr [] = $file ;
}
}
return $filearr ;
}
var_dump(iteral( 'd:\www\test' ));
来源: http://www.cnblogs.com/wuwenshuai/p/6636816.html
|