程序員的算法趣題Q19: 朋友的朋友還是朋友嗎？

oogh 發布于2021-09-10 10:51 / 3536人閱讀

摘要：基于以上討論可得，本題求解流程如下所示代碼及測試運行結果上一篇水果酥餅日下一篇異或楊輝三角形本系列總目錄參見程序員的算法趣題詳細分析和全解

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全解

GPU云服務器云服務器程序員的女朋友你的女朋友打造有吸引力的朋友圈阿里云綁定朋友的服務器

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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
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