《PHP程序员面试算法宝典》读书笔记01——经典算法题- PHP

文章目录

- 第1章经典算法题

第1章经典算法题

1.1 有多少苹果用来分赃

题目描述：

有5个人偷了一堆苹果，他们准备在第二天进行分赃。晚上，有个人溜出来，把苹果分成5份，将多余的一个扔给了树上的猴子，自己先将1/5藏了起来。其他4个人也都像第一个人那样，将苹果分成5份，将多余的一个扔给树上的猴子，偷走了1/5。第二天，大家分赃，也是分成5份，将多余的一个扔给猴子，最后一人分了一份。问：共有多少个苹果？

分析与解答：

假设总的苹果数量为s，上一个人对苹果划分时剩余的苹果数量为y，则有y=s-s/5-1。从这个公式开始，第一个人分的苹果总数s为最初的苹果总数，第二个人开始分赃直到结束分赃时，这个s都为上一个人分完剩余的苹果数量。以此类推。

<?php
/**
 * 1.有多少苹果用来分赃
 * 5人偷了一堆苹果，准备第二天分赃。晚上，一人偷偷将苹果分成5份，多的一个给了猴，自己藏了1/5。
 * 剩下的其他4个人，也同样这么想的，都像第一个人那样，将剩下的苹果分成5份，多的一个给猴，藏1/5。
 * 最后一人分了一份。问：苹果几何？
 */
for($s = 5; ; $s++) {
    if($s % 5 == 1 ) {
        $m = $s - round($s/5) - 1; // round()函数对浮点数进行四舍五入
        if($m % 5 == 1) {
            $n = $m - round($m/5) - 1;
            if($n % 5 == 1) {
                $k = $n - round($n/5) - 1;
                if($k % 5 == 1) {
                    $x = $k - round($k/5) - 1;
                    if($x % 5 == 1) {
                        $y = $x - round($x/5) - 1;
                        if($y % 5 == 1) {
                            echo $s;
                            exit();
                        }
                    }
                }
            }
        }
    }
}
?>
// 15621

1.2 选猴王

题目描述：

群猴排成圈，按1~n依次编号。从第1只开始数，数到第m只，第m只猴出圈。从第m+1只开始，数到第m只，该猴出圈。以此类推，最后剩下一只猴，即可成为新任猴王。编程模拟此过程，输入m、n，输出猴王编号。

分析与解答：

首先将猴从1~n编号存放到数组中，对猴子的总个数进行循环，循环时将数到编号的猴子从数组删除，将未数到的猴子从原位置移到数组末尾，移动后需将原位置的编号删除。只要判断该编号数组个数大于1都继续循环，直到数组最后只剩下一个编号，这个编号则为猴王。

<?php
header("Content-type:text/html;charset=utf-8");
function monkeyKing($n, $m) {
    $monkeys = range(1, $n);
    $i = 0;
    $k = $n;
    while(count($monkeys) > 1) {
        if(($i+1) % $m == 0) {
            unset($monkeys[$i]);
        } else {
            array_push($monkeys, $monkeys[$i]);
            unset($monkeys[$i]);
        }
        $i++;
    }
    return current($monkeys);
}
$monkey = monkeyKing(5, 2);
echo "最后当猴王的猴子编号为：",$monkey; // 最后当猴王的猴子编号为：3
?>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1.3 移动多少盘子才能完成汉诺塔游戏（递归）

题目描述：

汉诺塔游戏规则如下：

1）有三根柱子A、B、C，A柱上有若干盘子；

2）每次移动一只盘子，只能把小的盘子叠在大的盘子上面；

3）把所有盘子从A柱移到C柱上；

4）经研究发现，汉诺塔的破解很简单，就是按照移动规则向一个方向移动盘子。

5）例如3阶汉诺塔的移动：A→C，A→B，C→B，A→C，B→A，B→C，A→C。共移动7次。

实现代码：

<?php
function hanou($n, $x, $y, $z) {
    if($n == 1) {
        echo '移动盘子 1 从 '.$x. ' 到 '.$z."\n";
    } else {
        hanou($n-1, $x, $z, $y);
        echo "移动盘子 $n 从 $x 到 $z\n";
        hanou($n-1, $y, $x, $z);
    }
}
hanou(3, 'A', 'B', 'C');
?>
1
2
3
4
5
6
7
8
9
10
11
12

控制台输出：

移动盘子 1 从 A 到 C
移动盘子 2 从 A 到 B
移动盘子 1 从 C 到 B
移动盘子 3 从 A 到 C
移动盘子 1 从 B 到 A
移动盘子 2 从 B 到 C
移动盘子 1 从 A 到 C
1
2
3
4
5
6
7

1.4 约瑟夫环

题目描述：

Josephus和他的朋友及另外39个犹太人共41个人排成一圈，从第一个人开始报数，每报道第三个人该人就必须自杀，然后由下一个人从1重新开始报数，直到所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵守规则，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

分析与解答：

使用程序来求解的话，只要将阵列当作环状来处理，在阵列中由计数1开始，每3个数得到一个计数，直到计数到41为止；然后将阵列由索引1开始列出，就可以得知每个位置的自杀顺序，这就是约瑟夫排列。41个人报数的约瑟夫排列（自杀顺序）如下表所示：

排列顺序	1	2	3	4	5	6	7	8	9	10
自杀顺序	14	36	1	38	15	2	24	30	3	16
排列顺序	11	12	13	14	15	16	17	18	19	20
自杀顺序	34	4	25	17	5	40	31	6	18	26
排列顺序	21	22	23	24	25	26	27	28	29	30
自杀顺序	7	37	19	8	35	27	9	20	32	10
排列顺序	31	32	33	34	35	36	37	38	39	40
自杀顺序	41	21	11	28	39	12	22	33	13	29
排列顺序	41
自杀顺序	23

实现代码：

<?php
header("content-type:text/html;charset=utf-8");
define("N",41); // 参与总人数
define("M",3); // 每到3自杀一人

$man = array(0);
$count = 1;
$i = 0;
$pos = -1;
$alive = 2; // 想救的人数
while($count <= N) {
    do{
        $pos = ($pos+1)%N; // 环状处理
        if(@$man[$pos] == 0) {
            $i++;
        }
        if($i == M) {
            $i = 0; // $i重置
            break;
        }
    } while(1);
    $man[$pos] = $count;
    $count++;
}
// 截取出对应最大键值对应的键名
arsort($man);
$arr = array_slice($man, 0, $alive, true);
echo "约瑟夫排列： ";
for($i=0;$i<N;$i++) {
    echo " ".$man[$i];
}
echo "\nL表示要救的 $alive 个人要放到位置：";
for($i=0;$i<N;$i++) {
    if(isset($arr[$i]) && $man[$i] == $arr[$i]) {
        echo "L";
    } else {
        echo "D";
    }
    if(($i+1) % 5 == 0) {
        echo " ";
    }
}
?>
3132
33
34
35
36
37
38
39
40
41
42
43

输出：

约瑟夫排列：  14 36 1 38 15 2 24 30 3 16 34 4 25 17 5 40 31 6 18 26 7 37 19 8 35 27 9 20 32 10 41 21 11 28 39 12 22 33 13 29 23
L表示要救的 2 个人要放到位置：DDDDD DDDDD DDDDD LDDDD DDDDD DDDDD LDDDD DDDDD D
1
2

1.5 如何得到阿姆斯壮数

题目描述：

在三位整数中，如153可以满足13+53+33=153，这样的数被称为Armstrong（阿姆斯壮）数，试写出一程序找出所有的三位数Armstrong数。

分析与解答：

方法一：遍历三位数求解

阿姆斯壮数的寻找，其实是将一个数字分解为个位数、十位数、百位数。。。只要使用除法与余数运算即可求解出个十百位的数，例如，输入一个数字为abc，则：

百位：a=floor(input/100)

十位：b=floor((input%100)/10)

个位：c=input%10

实现代码如下：

<?php
header("content-type:text/html;charset=utf-8");
echo "阿姆斯壮数：";
for($num=100;$num<=999;$num++) {
    $a = floor($num/100);
    $b = floor(($num%100)/10);
    $c = $num%10;
    $x = $a*$a*$a+$b*$b*$b+$c*$c*$c;
    $y = $num;
    if($x==$num) {
        echo $num." ";
    }
}
?>
// 阿姆斯壮数：153 370 371 407 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

方法二：穷举数求解

利用for循环控制100~ 999个数，每个数分解出个位、十位、百位。利用循环，分别用i代表百位，j代表十位，m代表个位，且百位的初始数值是1~ 9，而十位和个位初始数值是0~9，然后按百位、十位、个位的顺序嵌套循环，找出符合阿姆斯壮数公式的数，找出符合条件的阿姆斯壮数。

实现代码如下：

<?php
    
for($i=1;$i<9;$i++) {
    for($j=0;$j<=9;$j++) {
        for($m=0;$m<=9;$m++) {
            if(pow($i,3)+pow($j,3)+pow($m,3) == 100*$i+10*$j+$m) {
                echo $i.$j.$m." ";
            }
        }
    }
}
?>
// 153 370 371 407 
1
2
3
4
5
6
7
8
9
10
11
12
13

1.6 获取规定的排列组合

题目描述：

将一组数字、字母或符号进行排列，以得到不同的组合顺序，如1、2、3这三个数的排列组合有：123、132、213、231、312和321。

分析与解答：

可以使用递归的方法将问题分解为较小的单元进行排列组合，如1、2、3、4的排列可以分为1[234]、2[134]、3[124]、4[123]进行排列，这个过程可以使用旋转法来实现：即先将旋转间隔设为0，再将最右边的数字旋转至最左边，并逐步增加旋转的间隔。然后对后面的子数组使用递归的方式进行求解。

例如：

1234 -> 旋转1 -> 继续将右边234进行递归处理；

2134 -> 旋转12变为21 -> 继续将右边123进行递归处理；

3124 -> 旋转123变为312 -> 继续将右边124进行递归处理；

4123 -> 旋转1234变为4123 -> 继续将右边123进行递归处理。

实现代码如下：

<?php
define("N",4);
$num = array();
for($i = 1; $i < N; $i++)
    $num[$i] = $i;
perm($num,1);

function perm($num,$i) {
    if($i < N) {
        for($j = $i; $j <= N; $j++) {
            $tmp = $num[$j];
            // 旋转该区段最右边数字至最左边
            for($k = $j; $k > $i; $k--)
                $num[$k] = $num[$k-1];
            $num[$i] = $tmp;
            perm($num,$i+1);
            // 还原
            for($k = $i; $k < $j; $k++)
                $num[$k] = $num[$k+1];
            $num[$j] = $tmp;
        }
    } else {
        // 显示此次排列
        for($j = 1; $j <= N; $j++)
            printf("%d ",$num[$j]);
        printf("\n");
    }
}
?>
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

1.7 如何实现洗牌算法

题目描述：

要求开发一款扑克游戏，编写一套洗牌算法，而公平地洗牌是将洗好的牌存储在一个整型数组里。

分析与解答：

定义一个洗牌函数，函数内用 $t m p 数组存储 154 表示 54 张牌。然后对这 54 张牌进行循环，每次循环时，通过随机函数随机从 0 到剩余牌数中生成一个数返回做索引，从$ tmp数组中取出这个索引对应的牌，存到洗牌后的数组 $c a r d s 。取出这张牌后同时要删除该牌在$ tmp数组内的位置，最后还要通过array_values()函数对 $t m p 数组的值重新排序，保证数组从 0 到当前剩余的牌数中可以根据随机生成的索引取出剩余的牌。最后得到洗好的牌都存在数组$ cards中。

实现代码如下：

<?php
$card_num = 54;
function wash_card($card_num) {
    // 新建数组
    $cards = $tmp = array();
    /**
     * 0~53表示54张牌，使用$tmp数组存储
     */
    for($i = 0; $i < $card_num; $i++) {
        $tmp[$i] = $i;
    }
    for($i = 0; $i < $card_num; $i++) {
        /**
         * rand(min,max)：返回介于min（默认为0）与max之间的随机整数
         * 这里用于随机从0到剩余牌数中生成一个随机整数作为索引
         */
        $index = rand(0,$card_num-$i-1);
        $cards[$i] = $tmp[$index];
        // 删除第i张牌在$tmp数组中的位置
        unset($tmp[$index]);
        /**
         * array_values()函数：返回数组中所有的值（不保留键名），
         * 被返回的数组将使用数值键，从0开始以1为步长递增
         */
        $tmp = array_values($tmp);
    }
    return $cards;
}
print_r(wash_card($card_num));
?>

示例：

Array
(
    [0] => 35
    [1] => 28
    [2] => 36
    [3] => 18
    [4] => 5
    [5] => 45
    [6] => 6
    [7] => 29
    [8] => 19
    [9] => 24
    [10] => 41
    [11] => 4
    [12] => 49
    [13] => 46
    [14] => 10
    [15] => 42
    [16] => 20
    [17] => 9
    [18] => 40
    [19] => 50
    [20] => 38
    [21] => 14
    [22] => 48
    [23] => 52
    [24] => 2
    [25] => 3
    [26] => 30
    [27] => 15
    [28] => 31
    [29] => 51
    [30] => 7
    [31] => 53
    [32] => 0
    [33] => 8
    [34] => 12
    [35] => 44
    [36] => 17
    [37] => 37
    [38] => 47
    [39] => 27
    [40] => 21
    [41] => 16
    [42] => 33
    [43] => 11
    [44] => 39
    [45] => 25
    [46] => 34
    [47] => 13
    [48] => 32
    [49] => 43
    [50] => 26
    [51] => 22
    [52] => 23
    [53] => 1
)
3132
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

1.8 求解斐波那契数列

题目描述：

有一只兔子，每个月生一只小兔子，小兔子一个月后也可以生兔子。开始有1只兔子，一个月后有2只兔子，两个月后有3只兔子，三个月后有5只兔子，以此类推，12个月后兔子有多少只（假设兔子存活率为100%）？

分析与解答：

兔子的出生规律数列为：1,1,2,3,5,8,13,21…，实际是求解斐波那契数列，即S(n)=S(n-1)+S(n-2)，其中，n表示月份，S(n)表示n个月后的兔子总数。

首先，以 $k 表示要求解多少个月，$ k1表示该月的上一个月的兔子总数， $k 2 表示上上个月的兔子总数，$ sum表示要求的月对应的兔子总数。然后从1月开始循环，通过斐波那契数列公式得到 $s u m =$ k1+ $k 2 ，求和后，把$ k1（上个月的兔子数量）赋值给 $k 2 （上上个月的兔子数量），再把$ sum（当月的兔子总数）赋值给 $k 1 。循环结束得到的$ sum即为要求的那个月对应的兔子总数。

实现代码如下：

<?php
$k = 12; // 总共12个月
$k1 = 1; // 记录上个月的兔子数量（从1月开始数）
$k2 = 0; // 记录上上个月兔子数量
$sum = 0; // 兔子总和
for($i = 1;$i < $k;$i++) {
    $sum = $k1 +$k2; // 当月兔子总和
    $k2 = $k1; // 上个月的兔子数量赋值给上上个月记录
    $k1 = $sum; // 当月的兔子数量赋值给上个月的兔子数量
}
echo $sum; // 144
?>
1
2
3
4
5
6
7
8
9
10
11
12

20200826

1.9 如何实现杨辉三角

题目描述：

请根据杨辉三角的规律，用编程实现杨辉三角。

分析与解答：

杨辉三角是二项式系数在三角形中的一种几何排列，1654年欧洲的帕斯卡也发现了这个规律，所以也叫“帕斯卡三角形”。杨辉三角具有以下规律：

1）第n行的数字有n项；
2）第n行的数字和为2^n-1;
3）每行数字左右对称，由1开始逐渐增大；
4）第n行的第m个数可表示为C(n-1,m-1)，即为从n-1个不同元素中取m-1个元素的组合数；
5）每个数字等于其上一行的左右两个数之和，即第n+1行的第i个数等于第n行的第i-1个数和第i个数的和，这也是组合数的性质之一，即C(n+1,i)=C(n,i)+C(n,i-1)；
根据杨辉三角的规律，可以通过一个二维数组，把第一位和最后一位的值存入数组，然后通过公式C(n+1,i)=C(n,i)+C(n,i-1)遍历二维数组求出每行的其他值。

实现代码如下：

<?php

function YangHuiTriangle($n) {
// 将第一位和最后一位的值保存在数组中
// 每行的第一个数和最后一个数都是1
    for($i=0; $i<$n; $i++) {
        $a[$i][0] = 1;
        $a[$i][$i] = 1;
    }
    for($i=2; $i<$n;$i++) {
        for($j=1; $j<$i; $j++) {
            // 第i行的第j个数等于第i-1行的第j-1个数与第j个数之和
            $a[$i][$j] = $a[$i-1][$j-1] + $a[$i-1][$j];
        }
    }
// 打印
    echo "$n 行的杨辉三角： \n";
    for($i=0; $i<$n; $i++) {
        for($j=0; $j<=$i; $j++) {
            echo $a[$i][$j]." ";
        }
        echo "\n";
    }
}
YangHuiTriangle(2);
YangHuiTriangle(3);
YangHuiTriangle(4);
YangHuiTriangle(5);
YangHuiTriangle(6);
?>

控制台打印：

2 行的杨辉三角： 
1 
1 1 
3 行的杨辉三角： 
1 
1 1 
1 2 1 
4 行的杨辉三角： 
1 
1 1 
1 2 1 
1 3 3 1 
5 行的杨辉三角： 
1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
6 行的杨辉三角： 
1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1 5 10 10 5 1 
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

关于杨辉三角的其他语言实现可参考百度百科：
https://baike.baidu.com/item/%E6%9D%A8%E8%BE%89%E4%B8%89%E8%A7%92https://cdn.jxasp.com:9143/image/215098

20200827

1.10 牛的数量有多少

题目描述：

有一头母牛，到4岁时可生育，每年可生育一头小牛。假设所生的均为母牛，到15岁绝育，不能再生，20岁自然死亡。问：n年后，有多少头牛？

分析与解答：

根据条件定义一个函数，参数 $n 代表多少年，定义牛的初始数量为 1 ；在循环中，当母牛年龄大于等于 4 ，且小于 15 时，每年可生一头小牛（即牛的数量加 1 ）；递归调用该函数，而函数的参数为$ n减去已过去的年数；函数内还要判断牛的年龄是否等于20，如果是的话，牛的数量需减1。

实现代码如下：

<?php
function countBull($n) {
    // 设置牛的初始数量为1
    static $num = 1;
    for($i=1; $i<=$n; $i++) {
        if($i>=4 && $i<15) { // 若母牛的年龄区间为[4,15)，则牛的数量加1
            $num++;
            countBull($n-$i);
        }
        // 如果牛的年龄为20，则牛的数量相应减1
        if($i == 20) {
            $num--;
        }
    }
    return $num;
}
echo countBull(4),"\n"; // 2
echo countBull(8),"\n"; // 8
echo countBull(12),"\n"; // 33
echo countBull(15),"\n"; // 100
echo countBull(20); // 431
?>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

1.11 百钱买百鸡

题目描述：

公鸡5文钱一只，母鸡3文钱1只，小鸡1文钱3只。现在要用100文钱买100只鸡，假设每种鸡至少买一只，问：这100只鸡中，公鸡、母鸡和小鸡各占多少只？

分析与解答：

假设公鸡、母鸡、小鸡的数量分别为x、y、z，则有：

x+y+z=100
5x+3y+z/3=100(z必须是3的倍数)

依次对公鸡、母鸡、小鸡的总数循环，进而求解出满足这两个条件的答案。

实现代码如下：

<?php
function handreddollarsforhandredchickens() {
    for($x=1; $x<100; $x++) {
        for($y=1; $y<100; $y++) {
            for($z=3; $z<100; $z=$z+3) {
                if(($x+$y+$z == 100) && ($x*5+$y*3+$z/3 == 100)) {
                    echo "公鸡： $x 只， 母鸡： $y 只， 小鸡： $z 只\n";
                }
            }
        }
    }
}
handreddollarsforhandredchickens();
?>
1
2
3
4
5
6
7
8
9
10
11
12
13
14

运行结果：

公鸡： 4 只， 母鸡： 18 只， 小鸡： 78 只
公鸡： 8 只， 母鸡： 11 只， 小鸡： 81 只
公鸡： 12 只， 母鸡： 4 只， 小鸡： 84 只
1
2
3

1.12 经过这个路口多少次

题目描述：

假设某人有100000现金，每次经过路口都需要付费。交费规则如下：当现金总额大于50000时，每次需交现金的5%；当现金小于等于50000时，每次需要交5000。问：此人可以经过这个路口多少次？

分析与解答：

由题可知，此人拥有初始现金总数为100000，通过路口次数的初始值为0，当金额不足5000时，不能再通过路口。因此，可通过循环求解通过路口次数，当现金大于50000时，剩余金额为：总金额x(1-5%)；当现金小于等于50000时，剩余金额为：总金额-5000，依次循环累加通过路口次数，直到不符合条件退出循环。

实现代码如下：

<?php
for($sum=100000,$num=0;$sum>=5000;) {
    if($sum > 50000) {
        // 当现金大于50000时，剩余金额为：总金额x(1-5%)
        $sum = 0.95*$sum;
    } else {
        // 当现金小于等于50000时，每次累减5000
        $sum -= 5000;
    }
    $num++;
}
echo $num; // 23
?>
1
2
3
4
5
6
7
8
9
10
11
12
13

1.13 球的反弹高度有多高

题目描述：

一个球从100米高度自由落下，每次落地后反弹回原高度的一半，然后再落下。求它在第10次落地时，共经过多少米？第10次反弹多高？

分析与解答：

初始高度为100米，每次下落高度反弹回的高度为上一次的一半，循环10次，每次循环都对上次反弹后的高度除以2并累加到总高度中。从而解出共经过多少米以及第十次的反弹高度。

实现代码如下：

<?php
$k = 100;
$sum = 100;
for($i=1;$i<=10;$i++) {
    $k /= 2;
    $sum += $k;
}
echo "共经过： $sum 米，第10次反弹高度为： $k 米"; // 共经过： 199.90234375 米，第10次反弹高度为： 0.09765625 米
?>
1
2
3
4
5
6
7
8
9

1.14 如何找出1000以内的“完数”

题目描述：

如果一个数恰好等于它的因子之和，那么这个数就被称为“完数”，例如：6=1+2+3。编程找出1000以内的所有“完数”。

分析与解答：

外部循环从6开始，每次循环得到的 $i 传入下个循环内，内部循环求解出符合$ i整除 $k 等于 0 的数，若能够整除，则说明$ k是 $i 的一个因子，则用$ sum累加，直到 $s u m + 1 （$ sum求解出的因子不包括1）等于 $i 条件成立，说明$ i是一个完数。需要注意的是： $i 的一个因子是不会大于$ ihttps://cdn.jxasp.com:9143/image/2的，因此内部循环判断是否继续循环的条件为$ihttps://cdn.jxasp.com:9143/image/2。

实现代码如下：

<?php
for($i=6; $i<1000; $i++) {
    $sum = 0;
    for($k = 2; $k <= $i/2; $k++) {
        if($i % $k == 0) {
            $sum += $k;
        }
    }
    if($sum+1 == $i) {
        echo $i." ";
    }
}
// 6 28 496 
?>
1
2
3
4
5
6
7
8
9
10
11
12
13
14

1.15 猴子吃了多少桃

题目描述：

猴子第一天摘了若干个桃子，当即吃了一半，没吃饱，又多吃了一个；第二天，吃了剩下桃子的一半多一个；之后每天都是如此，到第10天时，只剩下一个桃子。问：第一天猴子共摘了多少桃子？

分析与解答：

可以采用倒推的方式：

第10天 S₁₀ = 1
第9天 S₉ = 2x(S₁₀+1)
第8天 S₈ = 2x(S₉+1)
第7天 S₇ = 2x(S₈+1)
第6天 S₆ = 2x(S₇+1)
第5天 S₅ = 2x(S₆+1)
第4天 S₄ = 2x(S₅+1)
第3天 S₃ = 2x(S₄+1)
第2天 S₂ = 2x(S₃+1)
第1天 S₁ = 2x(S₂+1)

第10天	S₁₀ = 1
第9天	S₉ = 2x(S₁₀+1)
第8天	S₈ = 2x(S₉+1)
第7天	S₇ = 2x(S₈+1)
第6天	S₆ = 2x(S₇+1)
第5天	S₅ = 2x(S₆+1)
第4天	S₄ = 2x(S₅+1)
第3天	S₃ = 2x(S₄+1)
第2天	S₂ = 2x(S₃+1)
第1天	S₁ = 2x(S₂+1)

实现代码如下：

<?php
$s = 0;
$n = 1; // 最后一天的桃子数量
for($i=1; $i<10; $i++) {
    $s = ($n+1)*2;
    $n = $s;
}
printf("第一天共摘了 %d 个桃子\n",$s); // 第一天共摘了 1534 个桃子
?>
1
2
3
4
5
6
7
8
9

20200828

1.16 如何移动最少次数的三色旗

题目描述：

三色旗的问题最早由E.W.Dijkstra所提出，假设有一条绳子，上面有红、白、蓝三种颜色的旗子，起初绳子上的旗子颜色并没有顺序。现在希望将之分类，并排列为蓝、白、红的顺序，要如何移动才能让次数最少？注意：只能在绳子上进行这个动作，而且一次只能调换两个旗子。

分析与解答：

在一条绳子上移动，意味着在程序中只能使用一个阵列，不能使用辅助存储。问题的解法很简单：从绳子开头进行，遇到蓝色往前移，遇到白色留在中间，遇到红色往后移。如果要让移动次数最少的话，还需要一些技巧：

算法的主要思路就是用三个下标b、w、r分别指向不同的旗子。其中，b指向从0开始连续排列的蓝色旗子的最后面的第一个非蓝色旗子，r指向的从最后一个序号开始连续排列的红色旗子的第一个非红色旗子。例如：bbrwbbrr，那么b指向的就是序号为2的红色旗子，r指向的就是序号为倒数第三的蓝色旗子。

w作为可移动的指针来指引旗子的移动：当w指向的旗子是白色旗子时，w继续向前移动；当w指向的旗子是蓝色的时候，就需要把b所指的旗子和w所指的蓝色旗子互换；同理，当w指向的旗子为红色的时候就需要将w所指的红色旗子与r所指的旗子交换。

实现代码如下：

<?php
define("BLUE",'b');
define("WHITE",'w');
define("RED",'r');
function swap($x,$y,&$color) {
    $temp = $color[$x];
    $color[$x] = $color[$y];
    $color[$y] = $temp;
}
$color = array('r','b','r','w','r','r','w','b','b','r');
$wFlag = 0;
$bFlag = 0;
$rFlag = count($color)-1;
echo "旗子开始的排序： ";
for($i=0; $i < count($color); $i++) {
    echo $color[$i];
}
echo "\n";
while($wFlag <= $rFlag) {
    if($color[$wFlag] == WHITE) {
        $wFlag++;
    } else if($color[$wFlag] == BLUE) {
        swap($bFlag,$wFlag,$color);
        $bFlag++;
        $wFlag++;
    } else {
        while(($wFlag < $rFlag) && ($color[$rFlag] == RED)) {
            $rFlag--;
        }
        swap($rFlag,$wFlag,$color);
        $rFlag--;
    }
}
echo "排序后的旗子： ";
for($i=0; $i < count($color); $i++) {
    echo $color[$i];
}
echo "\n";
?>
3132
33
34
35
36
37
38
39

程序运行结果：

旗子开始的排序： rbrwrrwbbr
排序后的旗子： bbbwwrrrrr
1
2

关键词搜索

《PHP程序员面试算法宝典》读书笔记01——经典算法题

详情内容

文章目录

第1章经典算法题

1.1 有多少苹果用来分赃

1.2 选猴王

1.3 移动多少盘子才能完成汉诺塔游戏（递归）

1.4 约瑟夫环

1.5 如何得到阿姆斯壮数

1.6 获取规定的排列组合

1.7 如何实现洗牌算法

1.8 求解斐波那契数列

1.9 如何实现杨辉三角

1.10 牛的数量有多少

1.11 百钱买百鸡

1.12 经过这个路口多少次

1.13 球的反弹高度有多高

1.14 如何找出1000以内的“完数”

1.15 猴子吃了多少桃

1.16 如何移动最少次数的三色旗

相关技术文章

最新源码

下载排行榜

提示信息

选择支付方式

关键词搜索

《PHP程序员面试算法宝典》读书笔记01——经典算法题

详情内容

文章目录

第1章 经典算法题

1.1 有多少苹果用来分赃

1.2 选猴王

1.3 移动多少盘子才能完成汉诺塔游戏（递归）

1.4 约瑟夫环

1.5 如何得到阿姆斯壮数

1.6 获取规定的排列组合

1.7 如何实现洗牌算法

1.8 求解斐波那契数列

1.9 如何实现杨辉三角

1.10 牛的数量有多少

1.11 百钱买百鸡

1.12 经过这个路口多少次

1.13 球的反弹高度有多高

1.14 如何找出1000以内的“完数”

1.15 猴子吃了多少桃

1.16 如何移动最少次数的三色旗

相关技术文章

最新源码

下载排行榜

提示信息

选择支付方式

第1章经典算法题