PHP 递归经典算法实例
排列算法
首先明确函数的输入和输出，输入是一个字符串还有排列的个数，输出用数组来表示，所以函数的雏形应该是这样的
function permutation($str, $len)
{
$res = [];
if ($len == 1) {
$res = str_split($str);
} else {
}
return $res;
}
接着进行第二步，假设我们已经知道了len-1的输出，要由这个输出得出len的输出。在这个问题里，如果我已经知道了“abcd”选取2个的输出的集合，现在要“abcd”的选取3个集合，要怎样得出呢？
不难发现“abcd”选取1个的结果(a,b,c,d),与“abcd”选取2个的结果（ab,ac,ad,ba,bc,bd,…）的关系，在(a,b,c,d)后面循环插入单个元素与“abcd”的差集。于是得到如下算法。
function permutation($str, $len)
{
$res = [];
if ($len == 1) {
$res = str_split($str);
} else {
$list = permutation($str, $len - 1);
foreach ($list as $vo) {
$_arr = array_diff(str_split($str), str_split($vo));
foreach ($_arr as $item) {
$res[] = $vo . $item;
}
}
}
return $res;
}
echo PHP_EOL . '<==排列==>' . PHP_EOL;
$res = permutation('abcd', 2);
print_r($res);
组合算法
组合与排列类似，在插入元素时索引必须大于原来集合的任意一个元素的索引
function combination($str, $len)
{
$res = [];
if ($len == 1) {
$res = str_split($str);
} else {
$list = combination($str, $len - 1);
foreach ($list as $vo) {
$_arr = array_diff(str_split($str), str_split($vo));
$index1 = strpos($str, substr($vo, -1, 1));
foreach ($_arr as $item) {
$index2 = strpos($str, $item);
if ($index2 > $index1) $res[] = $vo . $item;
}
}
}
return $res;
}
echo PHP_EOL . '<==组合==>' . PHP_EOL;
$res = combination('abcd', 2);
print_r($res);
function combination($arr,&$res ,$len,$temp_arr=array())
{
$arr_len = count($arr);
if ($len == 0) {
$res[] = $temp_arr;
} else {
for ($i = 0; $i < $arr_len - $len + 1; $i++) {
$tmp = array_shift($arr);
$temp_arr[] = $tmp;
combination($arr, $res,$len - 1, $temp_arr);
array_pop($temp_arr);
}
}
}
echo PHP_EOL . '<==组合算法2==>' . PHP_EOL;
combination(['a','b','c'],$re,2);
print_r([$re]);
最大公约数
function get_GCD($a, $b)
{
if (is_int($a) && is_int($b) && $a > 0 && $b > 0) {
if ($a == $b) {
return $a;
} else if ($a < $b) {
return get_GCD($a, $b - $a);
} else {
return get_GCD($b, $a - $b);
}
}
return NULL;
}
$res = get_GCD(98, 28);
var_dump($res);
function get_GCD_NUM($a, $b)
{
if (is_int($a) && is_int($b) && $a > 0 && $b >= 0) {
if ($b == 0) {
return $a;
} else if ($a > $b) {
return get_GCD_NUM($b, $a % $b);
} else if ($a <= $b) {
return get_GCD_NUM($a, $b % $a);
}
}
return NULL;
}
$a = get_GCD_NUM(98, 28);
var_dump($a);
无限极分类
function toTree($arr, $pid, $deep = 0)
{
$tree = [];
foreach ($arr as $vo) {
if ($vo['pid'] == $pid) {
$temp_str = str_repeat(' ', $deep);
echo $temp_str . ($deep > 0 ? '└─' : '') . $vo['id'] . PHP_EOL;
$temp = toTree($arr, $vo['id'], $deep + 1);
if (count($temp) > 0) $vo['children'] = $temp;
$tree[$vo['id']] = $vo;
}
}
return $tree;
}
function toTreeStr($arr, $pid, $deep = 0)
{
$str = "";
foreach ($arr as $vo) {
if ($vo['pid'] == $pid) {
$temp_str = str_repeat(' ', $deep);
$tmp = $temp_str . ($deep > 0 ? '└─' : '') . $vo['id'] . PHP_EOL;
$str .= $tmp;
$temp = toTreeStr($arr, $vo['id'], $deep + 1);
if ($temp) {
$str .= $temp;
}
}
}
return $str;
}
$arr = [
['id' => 1, 'pid' => 0],
['id' => 9, 'pid' => 2],
['id' => 2, 'pid' => 1],
['id' => 3, 'pid' => 0],
['id' => 4, 'pid' => 2],
['id' => 5, 'pid' => 0],
['id' => 6, 'pid' => 4],
['id' => 7, 'pid' => 5],
['id' => 8, 'pid' => 2],
['id' => 10, 'pid' => 9]
];
$tree = toTree($arr, 0);
var_dump($tree);
$tree = toTreeStr($arr, 0);
var_dump($tree);
正整数划分问题
function splitNum($n,$m){
if($n<=0||$m<=0||!is_int($sn)||!is_int($sn)) return 0;
if($n==1||$m==1) return 1;
else if($n===$m) return splitNum($n,$n-1)+1;
else if($n<$m) return splitNum($n,$n);
else return splitNum($n-$m,$m)+splitNum($n,$m-1);
}
echo splitNum(9,5);
二叉树
class TreeNode
{
private $value;
private $left;
private $right;
public function __construct($value)
{
$this->value = $value;
return $this;
}
public function getValue()
{
return $this->value;
}
public function setValue($value)
{
$this->value = $value;
return $this;
}
public function getLeft()
{
return $this->left;
}
public function setLeft(TreeNode
$left)
{
$this->left = $left;
return $this;
}
public function getRight()
{
return $this->right;
}
public function setRight(TreeNode
$right)
{
$this->right = $right;
return $this;
}
}
class Tree
{
public function echoEachNode(TreeNode
$root, $deep = 0)
{
if ($root != null) {
$temp_str = str_repeat(' ', $deep);
echo $temp_str . ($deep > 0 ? '└─' : '') . $root->getValue() . PHP_EOL;
$_deep = $deep + 1;
if ($root->getLeft() != null) {
$this->echoEachNode($root->getLeft(), $_deep);
}
if ($root->getRight() != null) {
$this->echoEachNode($root->getRight(), $_deep);
}
}
}
}
$a = new TreeNode('A');
$b = new TreeNode("B");
$c = new TreeNode("C");
$d = new TreeNode("D");
$e = new TreeNode("E");
$f = new TreeNode("F");
$a->setLeft($b)->setRight($c);
$b->setRight($c);
$c->setLeft($f);
$bst = new Tree();
$bst->echoEachNode($a);
