第1章 经典算法题

在PHP程序员面试时，经常会考查一些非常经典的算法题，主要为了考查面试者的逻辑思维能力以及对编程语言掌握的熟悉程度。

1.1 有多少苹果用来分赃

难度系数：★★★☆☆

被考查系数：★★★☆☆

题目描述：

有5个人偷了一堆苹果，他们准备在第二天进行分赃。晚上，有一个人溜出来，他把所有苹果分成了5份，但是多了一个，他顺手把这多的一个苹果扔给树上的猴子，自己先拿1/5藏了起来。没想到其他四人也都是这么想的，都如第一个人一样把苹果分成5份，把多的那一个扔给了树上的猴，偷走了1/5。第二天，大家分赃，也是分成5份多一个扔给猴子。最后一人分了一份。问：共有多少苹果？

分析与解答：

假设总的苹果数量为s，上一个人对苹果划分时剩余的苹果为y，s/5为藏起来的一份，1为扔给猴子的一个苹果，则有公式y=s-s/5-1。从这个公式开始，第一个人分的苹果总数s为最初的苹果总数，第二个人开始分赃直到结束分赃时，这个s 都为上一个人分完苹果剩余的苹果数。所以可以根据这个式子，通过循环找出最后符合这个公式的解，从而得到苹果总数。

实现代码如下：

程序的运行结果为

从程序运行的结果知道，苹果总共有15621个。

1.2 哪只猴子可以当大王

难度系数：★★★☆☆

被考查系数：★★★☆☆

题目描述：

一群猴子排成一圈，按1，2，…，n依次编号。然后从第1只开始数，数到第m只，把它踢出圈，从它后面再开始数，再数到第m只，再把它踢出去……，如此不停地进行下去，直到最后只剩下一只猴子为止，那只猴子就可以当大王。要求编程模拟此过程，输入m、n，输出最后那个大王的编号。

分析与解答：

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

设m=5，n=2，实现代码如下：

程序的运行结果为

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

难度系数：★★★★☆

被考查系数：★★★★☆

题目描述：

汉诺塔（又称河内塔）问题是印度的一个古老的传说。在一个庙里有三根金刚石棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不停地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为辅助，但每次只能搬一个，而且大的不能放在小的上面。经过运算移动圆片的次数为18446744073709551615，看来众僧们耗尽毕生精力也不可能完成金片的移动。

后来，这个传说就演变为汉诺塔游戏，游戏规则如下：

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。

此外，汉诺塔问题也是程序设计中的经典递归问题。

分析与解答：

如果柱子标为ABC，那么要由A搬至C，在只有一个盘子时，就将它直接搬至C，当有两个盘子时，就将B当作辅助柱。如果盘数超过2个，那么将第三个以下的盘子遮起来，就很简单了，每次处理两个盘子，也就是：A-＞B、A-＞C、B-＞C这三个步骤，而被遮住的部分，其实就是进入程序的递归处理。事实上，若有n个盘子，则移动完毕所需次数为2ⁿ-1，所以当盘数为64时，则所需次数为：2⁶⁴-1=18446744073709551615，如果对这数字没什么概念，那么可以假设每秒钟搬一个盘子，也要约5850亿年。

实现代码如下：

程序的运行结果为

1.4 如何利用约瑟夫环来保护你与你的朋友

难度系数：★★★★☆

被考查系数：★★★★☆

题目描述：

据说著名犹太历史学家Josephus（约瑟夫）有过以下的故事：在罗马人占领乔塔帕特后， 39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，报数每报到第3个人该人就必须自杀，然后再由下一个人从1开始重新报数，直到所有人都自杀身亡为止。

然而Josephus和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

约瑟夫问题可用代数分析来求解，假设现在你与m个朋友不幸参与了这个游戏，你要如何保护你与你的朋友？

分析与解答：

实际上只要画两个圆圈就可以让自己与朋友免于死亡游戏，这两个圆圈中内圈是排列顺序，而外圈是自杀顺序，如下图所示。

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

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

由上述排列可知，最后一个自杀的是在第31个位置的人，而倒数第二个自杀的要排在第16个位置，之前的人都死光了，所以他们也就不知道约瑟夫与他的朋友有没有遵守游戏规则了。

实现代码如下：

程序的运行结果为

1.5 怎样才能得到阿姆斯壮数

难度系数：★★☆☆☆

被考查系数：★★★☆☆

题目描述：

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

分析与解答：

方法一：遍历三位数求解

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

百位：a=floor（input/100）

十位：b=floor（（input%100）/10）

个位：c=input%10

实现代码如下：

程序的运行结果为

方法二: 穷举数求解

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

实现代码如下：

程序的运行结果为

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-＞ 继续将右边134进行递归处理；

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

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

实现代码如下：

程序的运行结果为

1.7 如何实现洗牌算法

难度系数：★★★☆☆

被考查系数：★★★☆☆

题目描述：

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

分析与解答：

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

实现代码如下：

因为洗牌的结果是随机不唯一的，所以在这里不再罗列运行结果。

1.8 怎样求解斐波那契数列

难度系数：★★★☆☆

被考查系数：★★★☆☆

题目描述：

若有一只兔子，它每个月生一只小兔子，而小兔子一个月后也开始生产。起初只有一只兔子，一个月后就有两只兔子，两个月后就有三只兔子，三个月后有五只兔子，以此类推， 12个月后有多少只兔子？

分析与解答：

兔子的出生规律数列为1,1,2,3,5,8,13,21…，实际是求解斐波那契数列，即S（n） =S（n-1）+S（n-2），其中n表示月份，S（n）表示n个月后兔子的数量。首先以$k表示要求解多少个月，$k1表示上个月的兔子数量，$k2代表上上个月的兔子数量，$sum 为兔子的总数。然后从1月开始循环，通过斐波那契数列公式得到$sum=$k1+$k2，求和后，把$k1（上个月的兔子数量）赋值给$k2（上上个月的兔子数量），再把$sum（当月的总兔子数）赋值给$k1（上个月的兔子数量）。循环结束后输出的$sum就是兔子的总数了。

实现代码如下：

程序的运行结果为

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）遍历二维数组求出每行的其他值。

实现代码如下：

程序的运行结果为

1.10 牛的数量有多少

难度系数：★★★☆☆

被考查系数：★★☆☆☆

题目描述：

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

分析与解答：

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

设n为8年，实现代码如下：

程序的运行结果为

1.11 百钱买百鸡

难度系数：★★☆☆☆

被考查系数：★★★★☆

题目描述：

公鸡5文钱1只，母鸡3文钱1只，小鸡1文钱3只，现在用100文钱共买了100只鸡。假设每种鸡至少一只，那么在这100只鸡中，公鸡、母鸡和小鸡各是多少只？

分析与解答：

根据百钱买百鸡的要求，可以假设一共有i只公鸡，j只母鸡，k只小鸡，并且i+j+k的总数为100，即i×5+j×3+k/3=100（k必须是3的倍数）。依次对公鸡、母鸡、小鸡的总数循环，进而求解出满足这两个条件的答案。

实现代码如下：

程序的运行结果为

1.12 经过这个路口多少次

难度系数：★★★☆☆

被考查系数：★★★☆☆

题目描述：

假设某人有100,000现金。每经过一次路口需要进行一次交费。交费规则为当他身上的现金数大于50,000时，每次需要交现金的5%，当现金小于等于50,000时，每次需要交5,000。请写一个程序计算此人可以经过多少次这个路口。

分析与解答：

依题可知，某人拥有的总现金为100,000，初始过路口次数为0，当金额条件不满足5,000时，则停止过路口。所以可以通过循环求解过路口次数，当他现金大于50,000时，剩余金额为：总金额×（1-5%），当他现金小于等于50,000时，剩余金额为：总金额减少5000，依次循环累加过路口次数，直到不符合条件退出循环。

实现代码如下：

程序的运行结果为

1.13 球的反弹高度有多高

难度系数：★★☆☆☆

被考查系数：★★☆☆☆

题目描述：

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

分析与解答：

根据题目要求，假设初始总高度为100米，因为每次下落高度反弹回的高度为上一次的一半，循环10次，每次循环都对上次反弹后的高度除以2并且累加到总高度中。从而求解出共经过多少米和第十次的反弹高度。

实现代码如下：

程序的运行结果为

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

难度系数：★★★☆☆

被考查系数：★★★★☆

题目描述：

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

分析与解答：

外层循环998次，每次循环得到的$i传入下个循环内，内部循环求解出符合$i整除$k等于0的数，如果能够整除，那么说明$k是$i的一个因子，则用$sum累加，直到$sum+1等于$i条件成立，说明$i是一个“完数”。需要注意的是，因为$sum求解出的因子是不包括1的，所以还需要额外的加1到$sum中，并且$i的一个因子是不会大于$i/2的，所以内部循环判断是否继续循环的条件为$i/2。

实现代码如下：

程序的运行结果为

1.15 猴子吃了多少桃子

难度系数：★★★☆☆

被考查系数：★★★☆☆

题目描述：

猴子第一天摘了若干个桃子，当即吃了一半，它还不解馋，于是又多吃了一个；第二天，它吃了剩下桃子的一半，还不过瘾，又多吃了一个；以后每天都吃前一天剩下的一半多一个，到第10天想再吃时，只剩下一个桃子了。问第一天共摘了多少个桃子？

分析与解答：

本题可以采用逆向思维，从后往前推断，发现其中有相同的地方，即出现递推公式，可以采用递归方法。令S10=1，可以得出S9=2×（S10+1），简化罗列关系为：

S9=2×S10+2

S8=2×S9+2

…

Sn=2×Sn+2

实现代码如下：

程序的运行结果为

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

难度系数：★★★☆☆

被考查系数：★★★☆☆

题目描述：

三色旗的问题最早由E.W.Dijkstra所提出，他所使用的用语为“Dutch Nation Flag”（他是荷兰人），而多数的作者则使用“Three-Color Flag”来称之。

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

分析与解答：

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

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

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

实现代码如下：

程序的运行结果为