代码拉取完成，页面将自动刷新
参考资料1：基础算法
参考资料2：啊哈磊的《啊哈！算法》
求两个自然数的最大公约数。
这个是基础的数学问题，最大公约数指两个数字公共的约数中最大的，例如数字6的约数有1、2、3、6，数字9的约数有1、3、9，则数字6和数字9的公共约数有1和3，其中3是最大的公约数。
从1开始循环，每次把符合要求(即同时是两个数字的约数)的值都存储起来，那么最后一个存储起来的就是最大的约数。使用该思路，每次都存储得到的公共约数，那么最后一个存储的就是两个数字的最大公约数。
1_MaxCommonDivisor_v1.php
<?php
/**
* 求两个自然数的最大公约数(暴力枚举法/穷举法)
* @param int $a
* @param int $b
* @return bool|int
*/
function get_max_divisor($a, $b)
{
if (!is_numeric($a) || !is_numeric($b)) {
return false;
}
$min = $a > $b ? $b : $a;
$max = $a > $b ? $a : $b;
if ($max % $min === 0) {
return $min;
}
$result = 1;
for ($i = 1; $i <= $min / sqrt(2); $i++) {
if ($min % $i === 0 && $max % $i === 0) {
$result = $i;
}
}
return $result;
}
$a = 36;
$b = 16;
$c = get_max_divisor($a, $b);
var_dump($c);
从两个数字中最小的数字开始循环，每次减1，那么第一次得到的公共约数就是所求的最大公约数。
相比第一种，第二种的时间复杂度要低，因为一旦找到了之后就会跳出循环了，而第一种则需要完整的遍历一遍循环。
但是，两种方法都是采用了暴力穷举法，时间复杂度都是比较高的。可以采用其他的方法。
时间复杂度是O(min(a, b)))
1_MaxCommonDivisor_v2.php
<?php
/**
* 求两个自然数的最大公约数(暴力枚举法/穷举法——优化)
* 时间复杂度是O(min(a, b)))
* @param int $a
* @param int $b
* @return bool|int
*/
function get_max_divisor($a, $b)
{
if (!is_numeric($a) || !is_numeric($b)) {
return false;
}
$min = $a > $b ? $b : $a;
$result = 1;
for ($i = $min; $i >= 1; $i--) {
if ($a % $i === 0 && $b % $i === 0) {
$result = $i;
break;
}
}
return $result;
}
$a = 55;
$b = 10;
$c = get_max_divisor($a, $b);
var_dump($c);
辗转相除法/欧几里德算法
辗转相除法， 又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。它是已知最古老的算法， 其可追溯至公元前300年前。
原理：两个整数的最大公约数是能够同时整除它们的最大的正整数。
辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约数。 设两数为a、b(a>b)，求a和b最大公约数(a，b)的步骤如下：
用a除以b，得a÷b=q......r1(0≤r1)。若r1=0，则(a，b)=b；若r1≠0，则再用b除以r1，得b÷r1=q......r2 (0≤r2）.若r2=0，则(a，b)=r1，若r2≠0，则继续用r1除以r2，……如此下去，直到能整除为止。其最后一个为被除数的余数的除数即为(a, b)。
例如：a=25,b=15，a/b=1......10,b/10=1......5,10/5=2.......0,最后一个为被除数余数的除数就是5,5就是所求最大公约数。
辗转相除法相比起穷举法效率快很多，不用遍历每个数字。
时间复杂度不太好计算，可以近似为O(log(min(a, b)))，但是取模运算性能较差。
1_MaxCommonDivisor_v3.php
<?php
/**
* 求两个自然数的最大公约数(辗转相除法/欧几里德算法)
* 时间复杂度不太好计算，可以近似为O(log(min(a, b)))，但是取模运算性能较差。
* @param int $a
* @param int $b
* @return bool|int
*/
$a = 550;
$b = 700;
$c = gcd($a, $b);
var_dump($c);
/**
* 递归计算最大的公约数
* @param int $a
* @param int $b
* @return mixed
*/
function gcd($a, $b)
{
if (!is_numeric($a) || !is_numeric($b)) {
return false;
}
$min = $a > $b ? $b : $a;
$max = $a > $b ? $a : $b;
if ($max % $min === 0) {
return $min;
} else {
return gcd($min, $max % $min);
}
}
采用中国国人发明的更相减损法
更相减损术是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。（如果需要对分数进行约分，那么）可以折半的话，就折半（也就是用2来约分）。如果不可以折半的话，那么就比较分母和分子的大小，用大数减去小数，互相减来减去，一直到减数与差相等为止，用这个相等的数字来约分。
步骤：
第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。
比如：用更相减损术求260和104的最大公约数。由于260和104均为偶数，首先用2约简得到130和52，再用2约简得到65和26。此时65是奇数而26不是奇数，故把65和26辗转相减：
65-26=39
39-26=13
26-13=13
所以，260与104的最大公约数等于13乘以第一步中约掉的两个2，即1322=52。
更相减损术和辗转相除法的主要区别在于前者所使用的运算是“减”，后者是“除”。从算法思想上看，两者并没有本质上的区别，但是在计算过程中，如果遇到一个数很大，另一个数比较小的情况，可能要进行很多次减法才能达到一次除法的效果，从而使得算法的时间复杂度退化为O(N)，其中N是原先的两个数中较大的一个。
相比之下，辗转相除法的时间复杂度稳定于O(logN)。但是缺点也很明显，如果两个数相差很大，比如10000和59，做$a % $b取模运算的性能会比较低。
更相减损术：避免了取模运算，但是算法性能不稳定，最坏时间复杂度为O(max(a, b)))
1_MaxCommonDivisor_v4.php
<?php
$a = 44;
$b = 88;
$c = gcd($a, $b);
var_dump($c);
/**
* 求两个自然数的最大公约数(更相减损法)
* 避免了取模运算，但是算法性能不稳定，最坏时间复杂度为O(max(a, b)))
* @param int $a
* @param int $b
* @return mixed
*/
function gcd($a, $b)
{
if (!is_numeric($a) || !is_numeric($b)) {
return false;
}
if ($a === $b) {
return $a;
}
$min = $a > $b ? $b : $a;
$max = $a > $b ? $a : $b;
return gcd($max - $min, $min);
}
结合辗转相除法和更相减损法，在更相减损法的基础上使用移位运算
众所周知，移位运算的性能非常快。对于给定的正整数a和b，不难得到如下的结论。其中gcb(a,b)的意思是a,b的最大公约数函数：
当a和b均为偶数，gcb(a,b) = 2gcb(a/2, b/2) = 2gcb(a>>1, b>>1)
当a为偶数，b为奇数，gcb(a,b) = gcb(a/2, b) = gcb(a>>1, b)
当a为奇数，b为偶数，gcb(a,b) = gcb(a, b/2) = gcb(a, b>>1)
当a和b均为奇数，利用更相减损术运算一次，gcb(a,b) = gcb(b, a-b)， 此时a-b必然是偶数，又可以继续进行移位运算。
比如计算10和25的最大公约数的步骤如下：
整数10通过移位，可以转换成求5和25的最大公约数，利用更相减损法，计算出25-5=20，转换成求5和20的最大公约数
整数20通过移位，可以转换成求5和10的最大公约数
整数10通过移位，可以转换成求5和5的最大公约数，利用更相减损法，因为两数相等，所以最大公约数是5
在两数比较小的时候，暂时看不出计算次数的优势，当两数越大，计算次数的节省就越明显。
这种方法：不但避免了取模运算，而且算法性能稳定，时间复杂度为O(log(max(a, b)))
1_MaxCommonDivisor_v5.php
<?php
$a = 50;
$b = 88;
$c = gcd($a, $b);
var_dump($c);
/**
* 递归计算最大的公约数
* @param int $a
* @param int $b
* @return mixed
*/
function gcd($a, $b)
{
if (!is_numeric($a) || !is_numeric($b)) {
return false;
}
if ($a == $b) {
return $a;
}
//保证参数$a永远大于等于参数$b，为减少代码量
if ($a < $b) {
return gcd($b, $a);
} else {
//和1做按位与运算，判断奇偶
if (is_even($a) && is_even($b)) {
return (gcd($a >> 1, $b >> 1) << 1);
} elseif (is_even($a) && !is_even($b)) {
return gcd($a >> 1, $b);
} elseif (!is_even($a) && is_even($b)) {
return gcd($a, $b >> 1);
} else {
return gcd($b, $a - $b);
}
}
}
/**
* 判断奇偶数，减少迭代次数,奇数为false,偶数为true
* @param int $a
* @return bool
*/
function is_even($a)
{
return !($a & 1);
}
每只母鸡3元，每只公鸡4元，每只小鸡0.5元，如果花100元钱买100只鸡，请问有哪些可能？说明：每种鸡的数量都可以为零
其实这个问题是数学上的组合问题，只需要把所有的情况列举出来，然后来判断是否符合要求即可。这样的重复列举的问题，在程序上可以使用循环进行解决
当母鸡的数量为0时，公鸡的数量从0-100，当公鸡的数量每变化一次，小鸡的数量就从0变化到100
使用如下数值组合来描述这个思路：
上面列举出了所有公鸡、母鸡和小鸡的数量都是0-100时的所有组合，总计是101的三次方种，这样的穷举结构直接存在嵌套，在程序实际实现时，通过循环之间的嵌套就可以实现
2_HundredHen_v1.php
<?php
$x = 0;
for ($i = 0; $i <= 100; $i++) {
for ($j = 0; $j <= 100; $j++) {
for ($k = 0; $k <= 100; $k++) {
if (3 * $i + 4 * $j + 0.5 * $k == 100 && $i + $j + $k == 100) {
echo '第' . ++$x . '种解法为：' . PHP_EOL;
echo $i . PHP_EOL . $j . PHP_EOL . $k . PHP_EOL . PHP_EOL;
}
}
}
}
运行：
第1种解法为：
6
10
84
第2种解法为：
13
5
82
第3种解法为：
20
0
80
按照for语句的执行流程，循环变量变化1，则内部的循环执行一次，而在循环嵌套时，循环体又是一个新的循环，则该循环执行完成的一组循环。这里通过循环的嵌套实现了所有数值的穷举。在循环的内部，只需要按照题目要求判断一下数量和金额是否符合要求即可。
但是这样的代码效率比较差，可以通过简单的优化来提高程序的执行效率
由于母鸡每只的金额是3元，所以100元最多购买的母鸡数量是100/3=33只，同理100元最多购买的公鸡数量是25只，而按照100元100只的要求，小鸡的数量应该为100减去公鸡和母鸡的数量
时间复杂度比第一种好得多
2_HundredHen_v2.php
<?php
$x = 0;
for ($i = 0; $i <= 33; $i++) {
for ($j = 0; $j <= 25; $j++) {
$k = 100 - $i - $j;
if (3 * $i + 4 * $j + 0.5 * $k == 100) {
echo '第' . ++$x . '种解法为：' . PHP_EOL;
echo $i . PHP_EOL . $j . PHP_EOL . $k . PHP_EOL . PHP_EOL;
}
}
}
共有1000瓶汽水，每喝完后一瓶得到的一个空瓶子，每3个空瓶子又能换1瓶汽水，喝掉以后又得到一个空瓶子，问总共能喝多少瓶汽水，最后还剩余多少个空瓶子？
这个问题其实是个比较典型的递推问题，每3个空瓶都可以再换1瓶新的汽水，这样一直递推下去，直到最后不能换到汽水为止
每次喝一瓶，每有三个空瓶子就去换一瓶新的汽水，直到最后没有汽水可以喝为止。在程序中记忆汽水的数量和空瓶子的数量即可
3_DrinkingBottle_v1.php
<?php
// 汽水数量
$num = 1000;
// 喝掉的汽水数量
$drink_num = 0;
// 空瓶子的数量
$empty_num = 0;
// 如果还有汽水可以喝
while ($num > 0) {
// 喝掉一瓶
$num--;
// 空瓶子数量加1
$empty_num++;
// 喝掉的汽水数量加1
$drink_num++;
// 如果有3个空瓶子，就去换一瓶汽水
if ($empty_num === 3) {
// 汽水数量加1
$num++;
// 空瓶子数量清0
$empty_num = 0;
}
}
echo "喝掉的汽水数量为: " . $drink_num . PHP_EOL;
echo "剩余的空瓶子数量为: " . $empty_num . PHP_EOL;
运行：
喝掉的汽水数量为: 1499
剩余的空瓶子数量为: 2
在该代码中，每次循环喝掉一瓶汽水，则汽水数量减少1，空瓶子数增加1，喝掉的总汽水瓶数增加1，每次判断空瓶子的数量是否达到3，如果达到3则换1瓶汽水，同时空瓶子的数量变为零。这种思路比较直观，但是循环的次数比较多，所以就有了下面的逻辑实现
一次把所有的汽水喝完，获得所有的空瓶子，再全部换成汽水，然后再一次全部喝完，再获得所有的空瓶子，依次类推，直到没有汽水可喝为止
3_DrinkingBottle_v2.php
<?php
// 汽水数量
$num = 1000;
// 喝掉的汽水数量
$drink_num = 0;
// 空瓶子的数量
$empty_num = 0;
// 如果还有汽水可以喝
while ($num > 0) {
// 喝掉所有的汽水
$drink_num += $num;
// 空瓶子数量等于上次剩余的加上这次喝掉的数量
$empty_num += $num;
// 兑换的汽水数量
$num = intval(floor($empty_num / 3));
// 本次兑换剩余的空瓶子数量
$empty_num -= $num * 3;
}
echo "喝掉的汽水数量为: " . $drink_num . PHP_EOL;
echo "剩余的空瓶子数量为: " . $empty_num . PHP_EOL;
在该代码中，每次喝掉所有的汽水，也就是num瓶，则喝掉的总瓶数每次增加num，因为每次都可能剩余空瓶子(不足3个的)，则总的空瓶子数量是上次空瓶子数量加上本次喝掉的num瓶。接着是兑换汽水，则每次可以兑换的汽水数量是空瓶子的数量的1/3，注意这里是整数除法，而本次兑换剩余的空瓶子数量是原来的空瓶子数量减去兑换得到汽水数量的3倍，这就是一次循环所完成的功能，依次类推即可解决该问题
3个空瓶子=1瓶饮料=>3个空瓶子=1瓶饮料(不带瓶)+1个空瓶子=>2个空瓶子=1瓶饮料(不带瓶)，那么这样1000个空瓶可以兑换500瓶饮料(不带瓶)，但是最后1瓶饮料你是喝不到的，因为你最后剩下2个空瓶，喝的饮料数=1000+500-1
3_DrinkingBottle_v3.php
<?php
// 汽水数量
$num = 1000;
// 喝掉的汽水数量
$drink_num = 0;
// 空瓶子的数量
$empty_num = 2;
$drink_num = $num + $num / 2 - 1;
echo "喝掉的汽水数量为: " . $drink_num . PHP_EOL;
echo "剩余的空瓶子数量为: " . $empty_num . PHP_EOL;
水仙花数指三位数中，每个数字的立方和和自身相等的数字，例如370，3 × 3 × 3 + 7 × 7 × 7 + 0 × 0 × 0 =370，请输出所有的水仙花数
该问题中体现了一个基本的算法——数字拆分，需要把一个数中每位的数字拆分出来，然后才可以实现该逻辑。
实现思路：循环所有的三位数，拆分出三位数字的个位、十位和百位数字，判断3个数字的立方和是否等于自身。
4_NarcissusNumber.php
<?php
for ($i = 100; $i < 1000; $i++) {
// 个位数字
$a = $i % 10;
// 十位数字
$b = intval(floor($i / 10)) % 10;
// 百位数字
$c = intval(floor($i / 100));
if ($a * $a * $a + $b * $b * $b + $c * $c * $c === $i) {
echo $i . PHP_EOL;
}
}
运行：
153
370
371
407
在该代码中，拆分个位数字使用i和10取余即可，拆分十位数字时首先用i除以十，去掉个位数字，并使原来的十位数字变成个位，然后和10取余即可，因为i是一个三位数，所以i除以100即可得百位数字，因为这里都是整数除法，不存在小数的问题。然后只需要判断立方和是否等于自身即可。
注意：因为i是循环变量，这里不能改变i的值，不然可能造成死循环
求出1000以内的所有素数，素数即质数，只能被1和本身整除的数，最小的质数是2。
通过嵌套循环找出2到1000内所有的符合条件的数
5_PrimeNumbers_v1.php
<?php
for ($i = 2; $i <= 997; $i++) {
$is_prime = true;
for ($j = 2; $j < $i; $j++) {
if ($i !== $j && $i % $j === 0) {
$is_prime = false;
break;
}
}
if ($is_prime === true) {
echo $i . PHP_EOL;
}
}
这样算是想到的最直接的方式，当然也是最笨的方式，
因为每次判断的时候都会从2检查到i，聪明一点的方式是把i变成i/2，因为2/i以上的数肯定不会被i整除
5_PrimeNumbers_v2.php
<?php
for ($i = 2; $i <= 997; $i++) {
$is_prime = true;
for ($j = 2; $j <= $i / 2; $j++) {
if ($i !== $j && $i % $j === 0) {
$is_prime = false;
break;
}
}
if ($is_prime === true) {
echo $i . PHP_EOL;
}
}
i/2变成根号i，因为根号i以上的数肯定不会被i整除
5_PrimeNumbers_v3.php
<?php
for ($i = 2; $i <= 997; $i++) {
$is_prime = true;
for ($j = 2; $j <= sqrt($i); $j++) {
if ($i !== $j && $i % $j === 0) {
$is_prime = false;
break;
}
}
if ($is_prime === true) {
echo $i . PHP_EOL;
}
}
输出1 1 2 3 5 8 13……这样的数列，输出该数列的前20个数字。
该题是一个基本的数字逻辑，在实际解决该问题时，首先要发现该数字的规律，然后按照该规律来设计数组即可。
数字的规律是除了数列里的前两个数字以外，其它的数字都满足该数字等于前两个数字的和，由于题目要求输出前20个数字，所以需要一个长度为20的数组，第一个和第二个数字直接赋值，后续的数字通过前两个数字元素得到
6_GetSeries.php
<?php
$res[0] = 1;
$res[1] = 1;
for ($i = 2; $i < 20; $i++) {
$res[$i] = $res[$i - 1] + $res[$i - 2];
}
var_dump($res);
在该代码中，初始化一个长度为20的数组，首先将数组中的前两个元素赋值成1，然后循环对后续的元素的赋值，如果当前元素的下标是i，则它前一个元素的下标是i-1，再前面一个元素的下标是i-2，只需要将这2个元素的值相加，然后赋值给当前元素即可
在歌唱比赛中，共有10位评委进行打分，在计算歌手得分时，去掉一个最高分，去掉一个最低分，然后剩余的8位评委的分数进行平均，就是该选手的最终得分。如果已知每个评委的评分，求该选手的得分。
该题实际上涉及到求数组的最大值、最小值，以及求数组中所有元素的和，也是数组方便统计的用途体现。
求出数组元素的最大值、最小值以及和，然后使用和减去最大值和最小值，然后除以8获得得分
7_GetAvtScore.php
<?php
$score = array(90, 78, 90, 96, 67, 86, 78, 92, 79, 85);
$avg = (array_sum($score) - max($score) - min($score)) / 8;
echo $avg;
给定一个数组，数组内的数两两相同，只有一个数是孤立的，用最快的方式找出这个数。
循环数组，判断第i个元素的值和其它位置的值是否相等，如果不存在相等的，那么这个数就是孤立数据。
8_FindSingleNum_v1.php
<?php
$array = [1, 2, 3, 2, 3, 1, 4, 7, 6, 4, 7];
$res = find_single_num($array);
echo $res;
/**
* 从数组(数组内的数两两相同，只有一个数是孤立的)中寻找孤立的数字
* @param array $array 数组
* @return bool|int|mixed
*/
function find_single_num($array)
{
if (!is_array($array)) {
return false;
}
$single = 0;
foreach ($array as $key1 => $value1) {
$is_single = true;
foreach ($array as $key2 => $value2) {
if ($key2 !== $key1 && $value2 === $value1) {
$is_single = false;
break;
}
}
if ($is_single === true) {
$single = $value1;
break;
}
}
return $single;
}
显然这样的嵌套循环判断复杂度是很高的，达到n的平方，所以使用异或(^)
8_FindSingleNum_v2.php
<?php
$array = [1, 2, 3, 2, 3, 1, 4, 7, 6, 4, 7];
$res = find_single_num($array);
echo $res;
/**
* 从数组(数组内的数两两相同，只有一个数是孤立的)中寻找孤立的数字
* @param array $array 数组
* @return bool|int|mixed
*/
function find_single_num($array)
{
if (!is_array($array)) {
return false;
}
$single = 0;
foreach ($array as $value) {
$single = $single ^ $value;
}
return $single;
}
八皇后问题是一个古老的问题，于1848年由一位国际象棋棋手提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，如何求解？
八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当 n = 1 或 n ≥ 4 时问题有解。
使用递归回溯来解决
所谓递归回溯，本质上是一种枚举法。这种方法从棋盘的第一行开始尝试摆放第一个皇后，摆放成功后，递归一层，再遵循规则在棋盘第二行来摆放第二个皇后。如果当前位置无法摆放，则向右移动一格再次尝试，如果摆放成功，则继续递归一层，摆放第三个皇后......
如果某一层看遍了所有格子，都无法成功摆放，则回溯到上一个皇后，让上一个皇后右移一格，再进行递归。如果八个皇后都摆放完毕且符合规则，那么就得到了其中一种正确的解法，保存起来，继续下一种解法的寻找。
解决八皇后问题，可以分为两个层面：
具体的推导步骤可以参见：
9_EightQueen_v1.php
<?php
$obj = new EightQueen(8);
// 输出所有棋盘的格子
$obj->printOut();
/**
* 八皇后问题
*/
class EightQueen
{
// 棋盘格子的范围/皇后的数量
private $MAX_NUM;
// 二维数组作为棋盘，二维数组的第一个维度代表横坐标，第二个维度代表纵坐标，并且从0开始。比如chessBoard[3][4]代表的是棋盘第四行第五列格子的状态
private $ChessBoard;
// 所有的正确棋牌解法
private $result = [];
public function __construct($max_num)
{
// 初始化棋盘的格子范围/皇后的数量
$this->MAX_NUM = $max_num;
// 小于3x3的棋盘是无解的
if ($max_num >= 4) {
// 初始化棋盘，所有的格子(MAX_NUM x MAX_NUM)都为0，表示格子未放置
$this->ChessBoard = array_fill(0, $this->MAX_NUM, array_fill(0, $this->MAX_NUM, 0));
// 从第一层开始递归摆放皇后
$this->settleQueen();
}
}
/**
* 检查落点是否符合规则（未放置棋子即符合规则）
* @param $x int 横坐标
* @param $y int 纵坐标
* @return bool
*/
private function check($x, $y)
{
// 从第一层开始检查，从上到下进行每一层检查
for ($i = 0; $i < $y; $i++) {
// 纵向检查，对每一层的$x位置进行检查，如果每一层的$x位置已经有放置棋子的话则返回false，比如检查(5,3)这个格子的话，则这里是检查(5,0)(5,1)(5,2)这三个点
if ($this->ChessBoard[$x][$i] == 1) {
return false;
}
// 检测左侧斜向，比如检查(5,3)这个格子的话，则这里是检查(4,2)(3,1)(2,0)
if ($x - 1 - $i >= 0 && $this->ChessBoard[$x - 1 - $i][$y - 1 - $i] == 1) {
return false;
}
// 检测右侧斜向比如检查(5,3)这个格子的话，则这里是检查(6,2)(7,1)
if ($x + 1 + $i < $this->MAX_NUM && $this->ChessBoard[$x + 1 + $i][$y - 1 - $i] == 1) {
return false;
}
}
return true;
}
/**
* 从$y层（纵层）开始往下每一层递归摆放皇后，一旦找到一种解法就保存到result中去，然后继续找下一种解法
* @param $y int 纵坐标
*/
private function settleQueen($y = 0)
{
// 行数超过棋盘的范围，说明已经找到一种解法了，保存到result里面去
if ($y == $this->MAX_NUM) {
// 保存正确的棋牌解法
$this->result[] = $this->ChessBoard;
}
// 遍历当前行，从左到右逐一格子进行验证
for ($i = 0; $i < $this->MAX_NUM; $i++) {
// 为当前行的每个格子清零，以免在回溯的时候出现脏数据
for ($x = 0; $x < $this->MAX_NUM; $x++) {
$this->ChessBoard[$x][$y] = 0;
}
// 检查是否符合规则（未放置棋子即符合规则），如果符合，更改元素值并进一步递归
if ($this->check($i, $y)) {
$this->ChessBoard[$i][$y] = 1;
// 递归下层
$this->settleQueen($y + 1);
}
}
}
/**
* 输出所有正确棋盘解法
*/
public function printOut()
{
// 小于3x3的棋盘是无解的
if ($this->MAX_NUM < 4) {
echo '小于3x3的棋盘是无解的';
} else {
echo '一共有' . count($this->result) . '种解法：<br />';
foreach ($this->result as $k=>$v) {
echo "<br />输出第" . ++$k . "个结果 :<br />";
for ($i = 0; $i < $this->MAX_NUM; $i++) {
for ($j = 0; $j < $this->MAX_NUM; $j++) {
echo $v[$i][$j] . " ";
}
echo "<br />";
}
}
}
}
}
对上面的代码可以再进一步优化，比如对角线的判断都可以进行优化，$result也可以进行优化等
9_EightQueen_v2.php
<?php
$obj = new EightQueen(8);
// 获取所有解法的皇后位置
$result = $obj->getResult();
// 输出所有解法的棋盘格子
PrintChessBoard($result);
/**
* 按照0和1来输出棋盘的格式
* @param $array
*/
function PrintChessBoard($array)
{
$k = 0;
echo '一共有' . count($array) . '种解法：<br /><br />';
foreach ($array as $v) {
echo "输出第" . ++$k . "个结果：<br />";
foreach ($v as $row) {
for ($i = 0; $i < count($v); $i++) {
if ($row == $i) {
echo "1 ";
} else {
echo "0 ";
}
}
echo "<br />";
}
echo "<br />";
}
}
/**
* 八皇后问题
*/
class EightQueen
{
// 棋盘格子的范围/皇后的数量
private $MAX_NUM;
// 二维数组作为棋盘，二维数组的第一个维度代表横坐标，第二个维度代表纵坐标，并且从0开始。比如chessBoard[3][4]代表的是棋盘第四行第五列格子的状态
private $ChessBoard;
// 所有的正确棋牌解法
private $result = [];
public function __construct($max_num)
{
// 初始化棋盘的格子范围/皇后的数量
$this->MAX_NUM = $max_num;
// 小于3x3的棋盘是无解的
if ($max_num >= 4) {
// 从第一层开始递归摆放皇后
$this->settleQueen();
}
}
/**
* 检查落点是否符合规则（未放置棋子即符合规则）
* @param $n int 纵坐标即行数
* @return bool
*/
private function check($n)
{
// 从第一层开始检查，从上到下进行每一层检查
for ($i = 0; $i < $n; $i++) {
// 纵向检查、对角线检查
if ($this->ChessBoard[$i] == $this->ChessBoard[$n] || abs($this->ChessBoard[$i] - $this->ChessBoard[$n]) == ($n - $i)) {
return false;
}
}
return true;
}
/**
* 从$y层（纵层）开始往下每一层递归摆放皇后，一旦找到一种解法就保存到result中去，然后继续找下一种解法
* @param $y int 纵坐标
*/
private function settleQueen($y = 0)
{
// 行数超过棋盘的范围，说明已经找到一种解法了，保存到result里面去
if ($y == $this->MAX_NUM) {
// 保存正确的棋牌解法
$this->result[] = $this->ChessBoard;
}
// 遍历当前行，从左到右逐一格子进行验证
for ($i = 0; $i < $this->MAX_NUM; $i++) {
$this->ChessBoard[$y] = $i;
// 检查是否符合规则（未放置棋子即符合规则），如果符合，更改元素值并进一步递归
if ($this->check($y)) {
// 递归下层
$this->settleQueen($y + 1);
}
}
}
/**
* 输出所有正确棋盘解法
*/
public function getResult()
{
return $this->result;
}
}
对数组去重并从大到小排序，要求运行时间不超过1秒
先将数组去重，再从小到大进行排序，排序的话如果数组里面的数字并不大的话，可以使用桶排序
10_RemoveRepeatition_v1.php
<?php
// 需排序去重的数组
$array = [20, 40, 32, 67, 40, 20, 89, 300, 400, 15];
// 最终的结果数组
$result = [];
// 数组的最大值
$max = max($array);
// 设置一个桶数组，长度为需要排序数组的最大值，并且初始化都为0
$bucket = array_fill(0, $max + 1, 0);
// 遍历需排序的数组，对桶数组的值赋值为1
foreach ($array as $value) {
$bucket[$value] = 1;
}
// 从小到大输出桶数组的值
foreach ($bucket as $key => $value) {
if ($value == 1) {
$result[] = $key;
}
}
print_r($result);
由于桶排序的时间复杂度很小，所以基本可以满足1秒内完成，但是呢，如果数组里面的最大值非常大的话，那么需要占用极大的内存，而且也会影响效率，所以可以考虑使用其他的排序
先从小到大进行排序然后去重，排序的话可以使用冒泡，另外，由于排序之后相同的数会紧挨在一起，所以只需要在输出的时候判断一下当前的数a[i]与前面的数a[i-1]是否相同，相同的话则说明这个数已经输出了不用再次输出
10_RemoveRepeatition_v2.php
<?php
// 需排序去重的数组
$array = [20, 40, 32, 67, 40, 20, 89, 300, 400, 15];
// 进行冒泡排序
$array = BubbleSort($array);
// 先存第一个数
$result[] = $array[0];
$count = count($array);
// 如果和前一个数相同的话则不输出，否则输出
for ($i = 1; $i < $count; $i++) {
if ($array[$i] != $array[$i - 1]) {
$result[] = $array[$i];
}
}
print_r($result);
/**
* 冒泡排序
* @param $array array
* @return array
*/
function BubbleSort($array)
{
$num = count($array);
for ($i = 1; $i < $num; $i++) {
for ($j = 0; $j < $num - $i; $j++) {
if ($array[$j] > $array[$j + 1]) {
$temp = $array[$j];
$array[$j] = $array[$j + 1];
$array[$j + 1] = $temp;
}
}
}
return $array;
}
由于冒泡排序的时间复杂度很高，一旦数组中的元素数量是十万级别甚至更高的话，那么冒泡排序的话会消耗数十秒，因此也无法达到1秒内完成
第三种思路和第二种思路一样，只是把冒泡排序换成快速排序，这是因为冒泡排序的时间复杂度太高了，使用快速排序的话会比较快
由于排序之后相同的数会紧挨在一起，所以只需要在输出的时候判断一下当前的数a[i]与前面的数a[i-1]是否相同，相同的话则说明这个数已经输出了不用再次输出
10_RemoveRepeatition_v3.php
<?php
// 需排序去重的数组
$array = [20, 40, 32, 67, 40, 20, 89, 300, 400, 15];
// 最终的结果数组
$result = [];
// 进行快速排序
QuickSort($array);
// 先存第一个数
$result[] = $array[0];
$count = count($array);
// 如果和前一个数相同的话则不输出，否则输出
for ($i = 1; $i < $count; $i++) {
if ($array[$i] != $array[$i - 1]) {
$result[] = $array[$i];
}
}
print_r($result);
/**
* 快速排序
* @param array $arr
*/
function QuickSort(array &$arr)
{
$left = 0;
$right = count($arr) - 1;
QSort($arr, $left, $right);
}
/**
* @param $array
* @param $left
* @param $right
*/
function QSort(array &$array, $left, $right)
{
if ($left >= $right) {
return;
}
// 将$array一分为二，获取基准数的位置并回归
$pivot = Partition($array, $left, $right);
// 对基准数的左边进行递归排序
QSort($array, $left, $pivot - 1);
// 对基准数的右边进行递归排序
QSort($array, $pivot + 1, $right);
}
/**
* 选取数组当中的一个关键字作为基准数，使得它处于数组某个位置时，左边的值比它小，右边的值比它大，该关键字叫做枢轴/基准数，使枢轴/基准数记录到位，并返回其所在位置
* @param array $array
* @param $left int 左边第一个元素下标
* @param $right int 右边（最后）第一个元素下标
* @return int
*/
function Partition(array &$array, $left, $right)
{
// 选取子数组第一个元素作为枢轴/基准数
$pivot = $array[$left];
// 记录第一个元素的下标
$first = $left;
while ($left < $right) {
// $j从最右边往左边开始找，大于基准数$temp的话则继续往左边走
while ($left < $right && $array[$right] >= $pivot) {
$right--;
}
// $i从左边往右边找，小于基准数$temp的话则继续往右边走
while ($left < $right && $array[$left] <= $pivot) {
$left++;
}
// 当$i和$j没有相遇的时候则交换两者的位置
if ($left < $right) {
$t = $array[$left];
$array[$left] = $array[$right];
$array[$right] = $t;
}
}
// 将基准数归位
$array[$first] = $array[$left];
$array[$left] = $pivot;
// 返回$right也行，毕竟最后$left和$right都是停留在pivot下标处
return $left;
}
使用PHP内置的数组去重函数和排序函数来做
PHP内置的去重函数有：
array_unique函数 移除数组中重复的元素，可以用来实现对数组里的元素去重，但是由于删掉数组中重复的元素会导致key不按顺序，所以还需要使用array_values来对key重新排序
array_flip函数(推荐) 将数组中的键值和值进行反转，如果出现同一值，则最后一个键名将作为它的值，可以利用双重array_flip函数来去重，因为键值互换，原来重复的值会变为相同的键。然后再进行一次键值互换，把键和值换回来则可以完成去重，且效率要比array_unique函数高
PHP内置的排序函数有：sort、rsort、asort、ksort、arsort、krsort等
10_RemoveRepeatition_v4.php
<?php
// 需排序去重的数组
$array = [20, 40, 32, 67, 40, 20, 89, 300, 400, 15];
// 最终的结果数组
$result = [];
// 数组去重 array_flip()函数：将数组中的键值和值进行反转，如果出现同一值，则最后一个键名将作为它的值 利用双重array_flip可以实现数组去重，且效率要比PHP另一个数组去重函数array_unique要高得多
$result = array_flip(array_flip($array));
// 排序
sort($result);
print_r($result);
需要对一串数字进行解密
将第一个数删除，然后将第二个数放到末尾，接着第三个数删除并将第四个数放到末尾，再将第五个数删除，......，以此类推，直到剩下最后一个数，将最后一个数删除。按照刚才删除的顺序，将删除的数连起来就是解密后的数字了
使用队列来模拟解密
队列：一种特殊的线性结构，只允许在列队的首部(head)进行删除操作，称为出队，而在队列的尾部(tail)进行插入操作，称为入队，当队列中没有元素时(即head=tail),称为空队列
队列遵循先进先出(First In First Out，FIFO)原则
如果要删除一个数的话，只需要head++即可，把需要增加的数放到队尾即array[tail]，然后tail++
11_Decrypt.php
<?php
// 需解密的数字
$array = [6, 3, 1, 7, 5, 8, 9, 2, 4];
// 进行解密
$res = Decrypt($array);
var_dump($res);
/**
* 解密
* @param $array
* @return array
*/
function Decrypt($array)
{
$res = [];
// 队首
$head = 0;
// 队尾的下一个位置
$end = count($array);
// 当队列不为空(当队首和队尾重合的时候即为空)的时候执行循环
while ($head < $end) {
// 把队首放到新数组里面
$res[] = $array[$head];
// 将队首出队
$head++;
// 如果队首和队尾的下一个位置重合的话，则说明队列为空了，则退出
if ($head >= $end) {
break;
}
// 将新队首的数添加到队尾
$array[$end] = $array[$head];
$end++;
// 再将队首出队
$head++;
}
return $res;
}
判断一个字符是否是回文符，回文符即字符串从前往后读和从后往前读字符顺序是一致的
利用栈来判断，由于回文符是中间对称的，将回文符的前面一半入栈，然后出栈和后面一半一一对比匹配，都是一样的话表示是回文符
注意：该程序没法判断中文回文符，即一二一这样的字符
12_Palindrome.php
<?php
/**
* 判断一个字符是否是回文符，回文符即字符串从前往后读和从后往前读字符顺序是一致的
*
* 利用栈来判断，由于回文符是中间对称的，将回文符的前面一半入栈，然后出栈和后面一半一一对比匹配，都是一样的话表示是回文符
*/
$str = '12321';
$res = IsPalindrome($str);
var_dump($res);
/**
* 判断是否是回文字符
* @param $str
* @return bool
*/
function IsPalindrome($str)
{
// 读取字符的长度
$len = strlen($str);
// 计算中点位置
$mid = intval($len / 2) - 1;
// 栈的初始化
$top = 0;
$arr = [];
// 先将中点之前的字符全部入栈
for ($i = 0; $i <= $mid; $i++) {
$arr[++$top] = $str[$i];
}
// 判断字符串的长度是奇数还是偶数，并找出需要进行字符匹配的起始下标
if ($len % 2 === 0) {
$next = $mid + 1;
} else {
$next = $mid + 2;
}
// 开始匹配，对比中点之前的字符和中点之后的字符是否一致
for ($i = $next; $i <= $len - 1; $i++) {
if ($str[$i] != $arr[$top]) {
break;
}
$top--;
}
// 如果top为0，则表示栈内的所有字符都一一匹配，说明是回文符
if ($top === 0) {
return true;
}
return false;
}
斐波那契数列：1 1 2 3 5 8 13 21 34 55 …
概念：前两个值都为1，该数列从第三位开始，每一位都是前两位的和
规律公式为：Fn = F(n-1) + F(n+1)
求斐波那契数列有两种思路，比较简单的是使用递归去求，另外一种是通过循环去求
很容易联想到使用递归去求，使用递归去求的话虽然能达到目的，但是性能较慢
代码
13_Fib_v1.php
<?php
// 记录开始时间
$start_time = microtime(true);
$n = 30;
$res = Fibonacci($n);
print_r($res);
// 记录结束时间
$end_time = microtime(true);
// 记录耗时时间
echo round($end_time - $start_time, 3) . ' 秒';
/**
* 实现斐波那契数列
* @param $n
* @return array|bool
*/
function Fibonacci($n)
{
if ($n < 1) {
return false;
}
$res = [];
for ($i = 1; $i <= $n; $i++) {
$res[] = Fib($i);
}
return $res;
}
/**
* 获得斐波那契数列，第N位的数字
* @param $n
* @return int
*/
function Fib($n)
{
// 如果是第一位和第二位的话，则返回1
if ($n == 1 | $n == 2) {
return 1;
}
return Fib($n - 1) + Fib($n - 2);
}
运行，发现是需要5.759秒的，所以是比较慢的，但是上面的代码是可以进行优化的，由于在递归过程中，比如求Fibonacci(6)的时候呢，由于之前的递归已经求出了Fibonacci(5)和Fibonacci(4)了，所以可以没必要再重复计算了
所以优化后的代码为：
13_Fib_v2.php
<?php
// 记录开始时间
$start_time = microtime(true);
$n = 30;
$array = [];
Fibonacci($n);
print_r($array);
// 记录结束时间
$end_time = microtime(true);
// 记录耗时时间
echo round($end_time - $start_time, 3) . ' 秒';
/**
* 实现斐波那契数列
* @param $n
* @return bool
*/
function Fibonacci($n)
{
global $array;
if ($n < 1) {
return false;
}
for ($i = 0; $i < $n; $i++) {
$array[$i] = Fib($i);
}
return true;
}
/**
* 获得斐波那契数列，第N位的数字
* @param $n
* @return int
*/
function Fib($n)
{
global $array;
// 如果已经获得第N位的数字的话，则返回
if (isset($array[$n])) {
return $array[$n];
}
// 如果是第一位和第二位的话，则返回1
if ($n == 0 | $n == 1) {
return 1;
}
return Fib($n - 1) + Fib($n - 2);
}
运行发现只需要0.005秒
使用循环去求，相比使用递归去实现，效率要高得多，一般来说，非递归的效率高于递归
代码
13_Fib_v3.php
<?php
// 记录开始时间
$start_time = microtime(true);
$n = 30;
$res = Fibonacci($n);
print_r($res);
// 记录结束时间
$end_time = microtime(true);
// 记录耗时时间
echo round($end_time - $start_time, 3) . ' 秒';
/**
* 实现斐波那契数列
* @param $n
* @return array|bool
*/
function Fibonacci($n)
{
if ($n < 1) {
return false;
}
$res = [1, 1];
for ($i = 2; $i < $n; $i++) {
$res[$i] = $res[$i - 1] + $res[$i - 2];
}
return $res;
}
运行只需要0.004秒
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。
马建仓 AI 助手
