程序员的算法趣题Q19: 朋友的朋友还是朋友吗？

oogh 发布于2021-09-10 10:51 / 3325人阅读

摘要：基于以上讨论可得，本题求解流程如下所示代码及测试运行结果上一篇水果酥饼日下一篇异或杨辉三角形本系列总目录参见程序员的算法趣题详细分析和全解

1. 问题描述

2. 解题分析

3. 代码及测试

1. 问题描述

“六度空间理论”非常有名。大概的意思是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 产生联系。

如果选取的是6，则只需经过1层就可以联系到4、8、9、10这些数字。

因此N＝10时，无论最初选取的合数是什么，最多经过2层就可以与其它所有数产生联系。

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

（不知道是原文如此还是翻译不当）本题的背景描述和最后的问题描述（我认为）都是有明显问题的。

以上第3段话中，“。。。才能和其他所有的数产生联系。。。”，从后文来看，这里应该是“。。。才能和其他所有的合数产生联系。。。”。因为一个合数不可能与非自己因子的素数产生联系。
最后的问题。直接从字面理解的话，N=15，比如说{4,6,8,10,12,14,15}就满足条件。因为题目是要求最多经过6层，只要不超过6层（事实上只有7个数要产生联系也不可能超过6层）即可，并没有说一定必须到达6层。

问题描述应该修改如下：从1~N中选取7个合数，每个数字都可以与其它的6个数字建立联系。求使得7个数字中关系最远的两个数字必须经过6层才能产生联系的最小的N。

2. 解题分析

记两个数要产生联系所需经过的层数为两数之间的“距离”，记为dist(x,y)。题目的要求可以改写为：要求满足“从1~N中任选的7个合数中至少存在两个数，它们之间的距离为6”的条件的最小的N。

由于N1和N7之间的距离为6，则N1与其它5个数之间的距离必然分别为1~5，不失一般性，我们假定N1与N2的距离为1，N1与N3的距离为3，余者依此类推。

可以证明如下：

由于dist(N1,N7)=6，则必然存在1个数与N7距离为1，且与N1距离为5，令该数记为N6；

由于dist(N1,N6)=5，则必然存在1个数与N6距离为1，且与N1距离为4，令该数记为N5；。。。

余者依此类推。

满足条件的N的最小值必然是N1~N7中的最大值，即N=max(N1,N2,…,N7).所以寻找满足条件的最小的N，就是寻找满足条件的最小的7个合数。

由于(N1,N2), (N2,N3), …,(N6,N7)的距离分别为1，要使得这些数最小，它们之间分别应该具有(大于1的)为质数的唯一的公约数，分别记为：gcd(N1,N2)=a, gcd(N2,N3)=b, …, gcd(N6,N7)=f（gcd: Greatest Common Divisor, 表示最大公约数）。因此，N2的最小取值为a*b，N3的最小取值为k3*b*c，…，N6的最小取值为e*f，而N1和N7由于分别可能只有一个好友，它们的取值可以写为k1*a和k7*f。

显而易见，将{a,b,c,d,e,f}取最小的6个素数，然后分别令k1=a, k7=f可以满足以上条件（距离条件，且max(N1,…,N7)最小）。

(好吧，承认失败。本来我是想给出一个严格地证明，但是最后看起来如此显而易见的事情真要给出逻辑严谨的证明似乎并不是一件容易的事情，最后还是得靠一个“显而易见”敷衍了事。只叹：书到用时方恨少，数学学得太潦草) 先搁在这里，后面有机会再回头看能不能给出给严谨的说明。

基于以上讨论可得，本题求解流程如下所示：

3. 代码及测试

# -*- coding: utf-8 -*-"""Created on Thu Sep  9 08:27:24 2021@author: chenxy"""import sysimport timeimport datetimeimport math# import randomfrom   typing import List# from   queue import Queue# from   collections import dequeimport itertools as itprime = [2,3,5,7,11,13]globalMin = prime[-1]*prime[-1]for p in it.permutations(prime):         # print(p)    nums   = [p[0]*p[0]]    curmax = nums[0]    for k in range(1,len(p)):        nums.append(p[k-1]*p[k])        curmax = max(curmax,nums[-1])    nums.append(p[-1]*p[-1])        curmax = max(curmax,nums[-1])        if globalMin >= curmax:        globalMin = curmax         maxNums   = nums       print("globalMin = {0}, {1}".format(globalMin, maxNums))

运行结果：

上一篇：Q18: 水果酥饼日

下一篇：Q21: 异或杨辉三角形

本系列总目录参见：程序员的算法趣题：详细分析和Python全解

私有云服务器托管程序员的女朋友你的女朋友打造有吸引力的朋友圈阿里云绑定朋友的服务器

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/119797.html

程序员的算法趣题Q22: 不缠绕的纸杯电话

摘要：假设有几个小朋友以相同间隔围成圆周，要结对用纸杯电话相互通话。如果绳子交叉，很有可能会缠绕起来，所以结对的原则是不能让绳子交叉。如下所示运行结果上一篇异或杨辉三角形下一篇禁止右转本系列总目录参见程序员的算法趣题详细分析和全解目录 1. 问题描述 2. 解题分析 3. 代码及测试 1. 问...

MoAir 2021-09-09 09:33 评论0 收藏0
程序员的算法趣题Q51: 同时结束的沙漏

摘要：结合上下文猜测应该是说沙子同时漏完的意思。问题的焦点在于如何表示不同的排列状态以及如何处理沙漏翻转。上一篇完美洗牌完美洗牌下一篇糖果恶作剧本系列总目录参见程序员的算法趣题详细分析和全解程序员的算法趣题详细分析和全解目录 1. 问题描述 1.1 原题的表述 2. 解题分析 2.1 转换为线...

bovenson 2021-10-12 10:12 评论0 收藏0
程序员的算法趣题Q56: 鬼脚图中的横线(思路2的Python题解)

摘要：接下来就是判断两根线段是否相交的问题了。据此可以得到本题的算法流程代码实现运行结果不过要注意的是，原题说的是最少需要条横线的鬼脚图数，但是最后给出的解其实是正好需要条横线的鬼脚图数。书中给出的解释类似于数学证明中臭名昭著的显而易见。。。目录 1. 问题描述 2. 实现方案 3. 代码实现...

dance 2021-11-18 10:02 评论0 收藏0
35岁以后依然被公司抢着要？4面字节跳动，完虐面试官年薪70w，图形化app开发工具

摘要：面试后面试后及时总结，有可能下一个面试官会问你同样的问题。同时面试官也对我的未来技术发展提出了很多建议。总的来说，四面的氛围并没有想象得那么严肃，面试官也说面试得很愉快。 ...

XGBCCC 2021-11-24 09:39 评论0 收藏0
从阿里平薪跳头条，值得吗？

摘要：本文经授权转载自有一位供职于阿里的朋友跑来咨询我一个关于跳槽的问题朋友目前在阿里工作两年时间，刚拿到头条的，但非常纠结是否要接，所以来咨询下我的意见。本文经授权转载自wingjay（ID：cool-coder）有一位供职于阿里的朋友跑来咨询我一个关于跳槽的问题：朋友目前在阿里工作两年时间，刚拿到头条的 Offer，但非常纠结是否要接，所以来咨询下我的意见。而正好最近不少我的小专栏读者...

ideaa 2019-08-16 16:11 评论0 收藏0