ip地点 每组数字的寄义 （ip地点 每一位代表什么）〔ip地址每组数字的含义〕

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

　　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：100 目标 时间：30分钟）

　　大概 大部分 读者都清楚 ，IPv4 中的IP 地点 是二进制的32 位数值 。不外 ，如许 的数值对我们人类而言可读性比力 差，以是 我们通常会以8 位为1 组分割 ，用雷同 192.168.1.2 这种十进制数来表现 它（ 图12 ）。

　　这里，我们思考 一下十进制数0~9 这10 个数字各出现1 次的IP 地点 （像正常环境 一样，省略每组数字首位的0。也就是说 ，不能像192.168.001.002 如许 表现 ，而要像192.168.1.2 如许 来表现 ）

　　题目 ：

　　求用二进制数表现 上述情势 的IP 地点 时，能使二进制数左右对称的IP 地点 的个数（用二进制数表现 时不省略0 ，用完备 的32 位数表现 ） 。

　　Q4：高级

　　改变思绪 让程序速率 更快

　　难度系数：★★★★

　　异性相邻的座次安排

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

　　追念 起门生 时期调座位的时间 ，我们的内心 总是会小鹿乱闯 。想必很多 人都对谁会坐本身 旁边这件事莫名地冲动 吧？

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

　　题目 ：

　　假设有一个男生和女生分别有15 人的班级，要像图26 那样 ，倾轧 一个6×5的座次。求满意 上述条件的座次安排共多少种（前后大概 左右镜像的座次也看作差别 的安排。别的 ，这里不在意具体 某个门生 坐那边 ，只看男生和女生的座次安排）？

　　答案及分析

　　Q1-Q4

　　Q1解题思绪

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

　　Q1答案

　　324932种。

　　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答案

　　55

　　满意 条件的组合为：

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

　　Q3解题思绪

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

　　要想求左右对称的二进制数，可以通过把16 位的二进制数逆序分列 ，并将结果 与该16 位的二进制数本身 拼合 ，即天生 32 位数来求得。由于 是16 位，以是 全量搜刮 时只必要 遍历65536 种环境 即可 。

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

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

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

　　Point！

　　用十进制数表现 的时间 ，假如 以点号分割的各部分 左右对称，那么团体 也就左右对称，因而只必要 观察 0~255 这些数对应的二进制数中左右对称的数就可以了。也就是说 ，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 秒左右求出精确 答案。