100的程序员都想挑战的算法趣题 - 竹笋

TUhjnbcbe - 2022/11/4 19:34:00

计算机的世界每天都在发生着深刻的变化。新操作系统的发布、CPU性能的提升、智能手机和平板电脑的流行、存储介质的变化、云的普及……这样的变化数不胜数。

在这样日新月异的时代中，“算法”是不变的重要基石。要编写高效率的程序，就需要优化算法。无论开发工具如何进化，熟识并能灵活运用算法仍然是对程序员的基本要求。

本文为那些已经学习过排序、搜索等知名算法，并想要学习更多有趣的算法，进一步提升编程技巧的工程师准备了四道数学谜题形式的问题。这四道趣题分入门、初级、中级、高级，四种级别。

%的程序员都想挑战这四道有算法趣题。

在挑战之前，先听小编介绍下问题的具体形式：

每个问题大致分为“问题”和“详解”两部分。

请各位先通读问题描述，并动手编写程序尝试解题。在这个过程中，具体的实现方法是其次，更重要的是思考“通过哪些步骤来实现才能够解决问题”。

每个问题都有思路讲解和源代码示例。请留意自己编程时在处理速度、可读性等方面进行的优化，和本文的源代码示例有什么不同。如果事先看了思路讲解和答案，就会失去解题的乐趣，所以这里建议大家先编程解题，再看讲解。

小编为了大家更好的享受解题乐趣，把“详解”和“答案”放在了最后。

准备好了吗？我们开始答题吧！

Q1：入门

尝试用编程解决问题

难度系数：★

优秀的扫地机器人

（IQ：80目标时间：20分钟）

现在有很多制造商都在卖扫地机器人，它非常有用，能为忙碌的我们分担家务负担。不过我们也很难理解为什么扫地机器人有时候会反复清扫某一个地方。

假设有一款不会反复清扫同一个地方的机器人，它只能前后左右移动。举个例子，如果第1次向后移动，那么连续移动3次时，就会有以下9种情况（图6）。又因为第1次移动可以是前后左右4种情况，所以移动3次时全部路径有9×4＝36种。

※最初的位置用0表示，其后的移动位置用数字表示。

问题：

求这个机器人移动12次时，有多少种移动路径？

Q2：初级

解决简单问题体会算法效果

难度系数：★★

朋友的朋友也是朋友吗

（IQ：90目标时间：25分钟）

“六度空间理论”非常有名。大概的意思是1个人只需要通过6个中间人就可以和世界上任何1个人产生间接联系。本题将试着找出数字的好友（这里并不考虑亲密指数）。

假设拥有同样约数（不包括1）的数字互为“好友”，也就是说，如果两个数字的最大公约数不是1，那么称这两个数互为好友。

从1~N中任意选取一个“合数”，求从它开始，要经历几层好友，才能和其他所有的数产生联系（所谓的“合数”是指“有除1以及自身以外的约数的自然数”）。

举个例子，N＝10时，1~10的合数是4、6、8、9、10这5个。

如果选取的是10，那么10的好友数字就是公约数为2的4、6、8这3个。而9是6的好友数字（公约数为3），所以10只需要经过2层就可以和9产生联系（图5）。如果选取的是6，则只需经过1层就可以联系到4、8、9、10这些数字。因此N＝10时，无论最初选取的合数是什么，最多经过2层就可以与其他所有数产生联系。

问题：

求从1~N中选取7个合数时，最多经过6层就可以与其他所有数产生联系的最小的N。

Q3：中级

优化算法实现高速处理

难度系数：★★★

优雅的IP地址

（IQ：目标时间：30分钟）

可能大部分读者都清楚，IPv4中的IP地址是二进制的32位数值。不过，这样的数值对我们人类而言可读性比较差，所以我们通常会以8位为1组分割，用类似..1.2这种十进制数来表示它（图12）。

这里，我们思考一下十进制数0~9这10个数字各出现1次的IP地址（像正常情况一样，省略每组数字首位的0。也就是说，不能像...这样表示，而要像..1.2这样来表示）

问题：

求用二进制数表示上述形式的IP地址时，能使二进制数左右对称的IP地址的个数（用二进制数表示时不省略0，用完整的32位数表示）。

Q4：高级

改变思路让程序速度更快

难度系数：★★★★

异性相邻的座次安排

（IQ：目标时间：60分钟）

回想起学生时期调座位的时候，我们的心里总是会小鹿乱撞。想必很多人都对谁会坐自己旁边这件事莫名地激动吧？

这里我们考虑一种“前后左右的座位上一定都是异性”的座次安排。也就是说，像图26右侧那样，前后左右都是同性的座次安排是不符合要求的（男生用蓝色表示，女生用灰色表示）。

问题：

假设有一个男生和女生分别有15人的班级，要像图26那样，排出一个6×5的座次。求满足上述条件的座次安排共多少种（前后或者左右镜像的座次也看作不同的安排。另外，这里不在意具体某个学生坐哪里，只看男生和女生的座次安排）？

答案及解析

Q1-Q4

Q1解题思路

用坐标(0,0)表示最初的位置。从这个原点开始，避开已经走过的坐标，使机器人前进。用深度优先搜索就可以实现逻辑，如代码清单08.01所示。

Q1答案

种。

Q2解题思路

要解决这个问题，首先要正确理解问题中出现的词。首先是“合数”。

其次是“公约数”这个词。小学的时候，我们就做过求最大公约数的题。公约数的意思就是“共同的约数”。这里，拥有共同约数的数字互为“好友”，那么就需要求最大公约数非1的情况。

从1~N中选取7个合数，且“最多经过6层”，那么可以得知，我们要找的是“由2个数相乘得到的数字”的组合。这样的话，乘法运算中的这2个数就会成为公约数。

举个例子，选出a~h这些数。简单地说就是，当7个数字分别是以下的形式时，经过6层就能与其他所有数产生联系。

a×b,b×c,c×d,d×e,e×f,f×g,g×h

※这里a~h这些数字必须“互质”。

Point！

更进一步考虑，也可以像本题中的例子一样，把第1个数字设置成“平方数”（即4），也就是说变成下面这样的组合更好。

a×a,a×b,b×c,c×d,d×e,e×f,f×g

末尾如果同样设置成平方数就会变得更小，也就是变成下面这样的组合。

a×a,a×b,b×c,c×d,d×e,e×f,f×f

用Ruby可以像代码清单19.01这样实现。

Q2答案

满足条件的组合为：

[4,26,39,33,55,35,49]

Q3解题思路

按照题意，用十进制数表示时要使用0~9这10个数字各1次，那么最高位是除0以外的9种情况，而其他各个数位可分别使用0~9这10个数字各1次，其排列组合一共9!（9的阶乘）种，所以总共要遍历9×9!种，也就是种情况。

要想求左右对称的二进制数，可以通过把16位的二进制数逆序排列，并将结果与该16位的二进制数本身拼合，即生成32位数来求得。因为是16位，所以全量搜索时只需要遍历种情况即可。

然后，把这个二进制数转换成十进制数，分别使用0~9这10个数字各1次即可。

用Ruby实现时，代码如代码清单40.01所示。

执行程序可得到正确答案“8”，因而符合条件的IP地址有8个，如表4所示。

Point！

用十进制数表示的时候，如果以点号分割的各部分左右对称，那么整体也就左右对称，因而只需要调查0~这些数对应的二进制数中左右对称的数就可以了。也就是说，A.B.C.D这种形式中，A要和D对称，B要和C对称。

下面我们试着找出A~D的各种组合中，0~9这10个数字各使用1次的组合。每组（A,D）,（B,C）生成的IP地址有8种情况，所以用组合数乘以8就可以求出结果。

用Ruby实现时，代码如代码清单40.02所示。

Q3答案

8个。

Q4解题思路

如果完全按照问题描述实现，只需要遍历30个座位中15个男生的座次，满足条件就OK了。如果不考虑可扩展性、处理速度等，只需要把不符合条件的情况排除就可以了，并不是很难。

这里，我们事先准备好要排除的座次安排，统计不在这个范围内的座次安排即可。用Ruby实现时，如代码清单68.01所示。

要想改善处理速度，就要考虑“如何缩小搜索范围”。基本的办法不外乎“剪枝”和“内存化”。

这里，我们事先准备前2排的座次安排，然后生成下一排可能的安排，并递归地搜索下去。同时，把已经搜索过的结果保存到内存中，避免重复搜索（代码清单68.02）。

上面这个程序可以在2秒左右求出正确答案。

Q4答案

13374种。

最后介绍一下文中出场人物：