PHP 与 算法设计

来自PHP百科全书
跳转至: 导航搜索

php版的快速排序

快速排序原理:从数组中选择一个数作为基准,大于它的数放到他后面,小于它的数放到他前面,把数组分成两部分,然后对这两部分分别按前面的原则进行递归,直到分出来的数组长度为1,即可完成排序。

实现方式1

<?php
/**
* fast sort 1
*/

$array = array(8,3,5,7,9,2,4,6,13,10,14,12,11);

function fsort(& $array, $low, $high){
    if($low < $high){
        $k=$low;//记住排序开始位置
        $h=$high;//记住排序结束位置
        $pivotkey=$array[$low];
        for($i=$k; $i<$high; $i++){
            //小数往前靠
            if($array[$i] < $pivotkey){
                array_splice($array, $low, 0, $array[$i]);
                array_splice($array, $i+1, 1);
                $low++;
            }
        }

        for($i=$k; $i<$high; $i++){
            //大数往后靠
            if($array[$i] > $pivotkey){
                array_splice($array, $high, 0, $array[$i]);
                array_splice($array, $i, 1);
                $high--;
            }
        }

        fsort($array, $k, $low);//对小数递归
        fsort($array, $low+1, $h);//对大数递归
    }
}

fsort($array, 0, count($array));

print_r($array);echo '<br>';

实现方式2

/**
* fast sort 2
*/

$array = array(8,3,5,7,9,2,4,6,13,10,14,12,11);

//对数组按照基准划分为大数和小数两部分
function partition(& $array, $low, $high){
	$pivotkey = $array[$low];
	if($low < $high){
		for($i=$low; $i<$high; $i++){
			if($array[$i] < $pivotkey && $i > $low){
				array_splice($array, $low, 0, $array[$i]);
				array_splice($array, $i+1, 1);
				$low++;
				//print_r($array);
			}else if($array[$i] > $pivotkey && $i < $low){
				array_splice($array, $high, 0, $array[$i]);
				array_splice($array, $i, 1);
			}
			//print_r($array);
		}
		//print_r($array);exit();
	}
	return $low;
}

function fsort2(& $array, $low, $high){
	if($low < $high){
		$pivotloc = partition($array, $low, $high);
		//print_r($array);
		fsort2($array, $low, $pivotloc);//对小数递归
		fsort2($array, $pivotloc+1, $high);//对大数递归
	}
}

fsort2($array, 0, count($array));

print_r($array);

//end

卡塔兰数计算n对小括号的有几种呢

<?php
/**
* 设计思想,问题可以看作是初始字符串为'',每次插入的最小单元为(),然后每次往当前的字符串里面里面插入(),3对()的话就是插入三次(),总共有多少种不一样的字符串
* ()
* (()) ()()
* (())() ((())) ()()() (())() ()(())
*/

function combination($n){
    $char = '()';//定义初始字符串
    $result = array('');
    $k=0;
    for($i=1; $i<=$n; $i++){//需要插入的总次数
        $result = insert($result, $char);
    }
    return $result;
}

//每次插入产生的结果数组
function insert($arr, $char){
    $result = array();
    foreach($arr as $val){
        for($i=0; $i<strlen($val)+1; $i++){
            $str = substr($val,0,$i).$char.substr($val,$i,strlen($val)-$i);
            if(!in_array($str, $result)){
                $result[] = $str;
            }
        }
    }
    return $result;
}

print_r(combination($_GET['n']));
//end


用数组中的所有数字组合出最大的数,每个数字使用一次

/**
 *
 * 题目:用数组中的所有数字组合出最大的数,每个数字使用一次
 * 分析:排列组合遍历所有组合出来的数,始终维护一个最大数
 *
 */
$array = array(4, 91, 9, 8, 3, 11);

function get_max_num($array, & $max=0, $n){
	foreach($array as $key => $value){
		$a = $array;
		$num = $a[$key];
		$k = $n;
		$k .= $num;
		array_splice($a, $key, 1);
		//print_r($a);exit();
		if(count($a) > 0)
			get_max_num($a, $max, $k);
		else{
			$max =  $k > $max ? $k : $max;
		}
	}

	return $num;
}

get_max_num($array, $max, '');

echo $max; //99184311

商人卖萝卜问题

<?php 
/**
 * 一个商人骑一头驴要穿越1000公里长的沙漠,去卖3000根胡萝卜。
 * 已知驴一次性可驮1000根胡萝卜,但每走1公里又要吃掉1根胡萝卜。问:商人最多可卖出多少胡萝卜?
 * 设计思路:驴一次可驮1000跟,所以3000跟得驮三次
 * 随着萝卜越来越少,会变成驮两次,1次,驮多次时需要往返来驮,往返总次数为2n-1,n为需要驮的次数
 * 只要计算每根萝卜能让驴驮所有萝卜走多远,然后
 */
$t=3000;//总萝卜
$s=0;//走过的总路程

for($i=0; $i<3000; $i++){
	$k = 2*ceil($t/1000)-1;//往返次数2乘以需要驮的次数减一
	$s += 1/($k);//累加每跟萝卜可行驶最远距离
	if($s > 1000)
		break;
	$t--;
}

echo $t;

二分查找

<?php
/**
*  二分查找:在一个有序的序列里查找某个数的位置,每次把查找范围缩小一半
*/

function tow_part_find($array, $value, $x, $y){
    $idx = intval(($x+$y)/2);
    if($array[$idx] > $value){
        tow_part_find($array, $value, $x, $idx);
    }elseif($array[$idx] < $value){
        tow_part_find($array, $value, $idx, $y);
    }else{
        echo $idx;
    }
}

tow_part_find(range(0, 100), 30, 0, 100);
//输出30

redis服务器模拟加权轮循算法

<?php 

/**
 * redis服务器加权轮循算法设计
 * 这段代码的作用是运行在后台来维护连接数的负载均衡与一个可连接的服务器列表
 */

class Balancer{
	
	//定义三台server
	private static $server = array(
			array(
					'host'=>'127.0.0.1',
					'port'=>6379,
					'status'=>'run',//运行状态:run表示允许,stop表示停止
					'weight'=>3,//权重
			),
			array(
					'host'=>'127.0.0.2',
					'port'=>6379,
					'status'=>'run',
					'weight'=>2,
			),
			array(
					'host'=>'127.0.0.3',
					'port'=>6379,
					'status'=>'run',
					'weight'=>1,
			),
	);
	
	//需要生成的服务器轮询列表
	private static $list = array();
	
	//保存redis服务器列表的list
	const redis_list = 'redis_list';
	
	/**
	 * 生成加权轮训的服务器列表
	 */
	public static function RoundRobin(){
		foreach(self::$server as $k => $v){
			if($v['status'] == 'run'){
				//服务器状态自动检测
				$redis = new redis();
				$ret = @$redis->connect($v['host'], $v['port'], 3);
				if($ret){
					for($i=0;$i<$v['weight'];$i++){
						array_push(self::$list,$v);
					}
				}
			}
		}
		
		return self::$list;
	}
	
	/**
	 * 保存到redis,然后在你需要连接redis的时候就可以每次从队列获取一个ip来进行连接
	 */
	public static function save2redis(){
		//连接本地redis
		$redis = new redis();
		$redis->connect('127.0.0.1', 6379);
		
		$llen = $redis->lLen(self::redis_list);
		$result = $redis->lrange(self::redis_list, 0 , $llen-1);
		
		//检查是否有更新
		$list = array();
		foreach(self::$list as $k => $v){
		    $list[$k] = json_encode($v);
		}
		//print_r($list);
		//print_r($result);
		$tmp1 = array_diff($result, $list);//检查待更新的数组比原数组少的配置项
		$tmp2 = array_diff($list, $result);//检查待更新的数组比原数组多的配置项
		
		if(!$tmp1 && !$tmp2) return true;//无更新返回
		
		$redis->multi();
		$redis->del(self::redis_list);
		
		//服务器列表入队
		foreach(self::$list as $k => $v){
			$redis->lpush(self::redis_list, json_encode($v));
		}
		$redis->exec();
	}
}

Balancer::RoundRobin();//生成服务器列表
Balancer::save2redis();//存入redis

//end
查看本地redis:
127.0.0.1:6379> lrange redis_list 0 100 
1) "{\"host\":\"127.0.0.3\",\"port\":6379,\"status\":\"run\",\"weight\":1}"
2) "{\"host\":\"127.0.0.2\",\"port\":6379,\"status\":\"run\",\"weight\":2}"
3) "{\"host\":\"127.0.0.2\",\"port\":6379,\"status\":\"run\",\"weight\":2}"
4) "{\"host\":\"127.0.0.1\",\"port\":6379,\"status\":\"run\",\"weight\":3}"
5) "{\"host\":\"127.0.0.1\",\"port\":6379,\"status\":\"run\",\"weight\":3}"
6) "{\"host\":\"127.0.0.1\",\"port\":6379,\"status\":\"run\",\"weight\":3}"
这就是我们生成的队列,在获取的时候采用以下方式,即可获取到需要连接的一台redis的服务器信息,队列中的数据会按顺序一直循环
127.0.0.1:6379> rpoplpush redis_list redis_list
1) "{\"host\":\"127.0.0.3\",\"port\":6379,\"status\":\"run\",\"weight\":1}"