資訊專欄INFORMATION COLUMN
摘要：基于以上討論可得，本題求解流程如下所示代碼及測試運行結果上一篇水果酥餅日下一篇異或楊輝三角形本系列總目錄參見程序員的算法趣題詳細分析和全解
目錄
????????“六度空間理論”非常有名。大概的意思是1個人只需要通過6個中間人就可以和世界上任何1 個人產(chǎn)生間接聯(lián)系。本題將試著找出數(shù)字的好友（這里并不考慮親密指數(shù)）。
????????假設擁有同樣約數(shù)（不包括 1）的數(shù)字互為“好友”，也就是說，如果兩個數(shù)字的最大公約數(shù)不是 1，那么稱這兩個數(shù)互為好友。
????????從1~N 中任意選取一個“合數(shù)”，求從它開始，要經(jīng)歷幾層好友，才能和其他所有的數(shù)產(chǎn)生聯(lián)系（所謂的“合數(shù)”是指“有除 1 以及自身以外的約數(shù)的自然數(shù)”）。
????????舉個例子，N ＝ 10 時，1~10 的合數(shù)有4、6、8、9、10這 5 個。
????????如果選取的是10，那么10的好友數(shù)字就是公約數(shù)為2的4、6、8這3個。
????????而9是6的好友數(shù)字（公約數(shù)為3），所以10只需要經(jīng)過2層就可以和 9 產(chǎn)生聯(lián)系。
????????如果選取的是6，則只需經(jīng)過1層就可以聯(lián)系到4、8、9、10這些數(shù)字。
????????因此N＝10時，無論最初選取的合數(shù)是什么，最多經(jīng)過2層就可以與其它所有數(shù)產(chǎn)生聯(lián)系。
????????問題：求從1~N中選取7個合數(shù)時，最多經(jīng)過6層就可以與其它所有數(shù)產(chǎn)生聯(lián)系的最小的N。
????????（不知道是原文如此還是翻譯不當）本題的背景描述和最后的問題描述（我認為）都是有明顯問題的。
????????問題描述應該修改如下：從1~N中選取7個合數(shù)，每個數(shù)字都可以與其它的6個數(shù)字建立聯(lián)系。求使得7個數(shù)字中關系最遠的兩個數(shù)字必須經(jīng)過6層才能產(chǎn)生聯(lián)系的最小的N。
????????記兩個數(shù)要產(chǎn)生聯(lián)系所需經(jīng)過的層數(shù)為兩數(shù)之間的“距離”，記為dist(x,y)。題目的要求可以改寫為：要求滿足“從1~N中任選的7個合數(shù)中至少存在兩個數(shù)，它們之間的距離為6”的條件的最小的N。
????????由于N1和N7之間的距離為6，則N1與其它5個數(shù)之間的距離必然分別為1~5，不失一般性，我們假定N1與N2的距離為1，N1與N3的距離為3，余者依此類推。
????????可以證明如下：
????????由于dist(N1,N7)=6，則必然存在1個數(shù)與N7距離為1，且與N1距離為5，令該數(shù)記為N6；
????????由于dist(N1,N6)=5，則必然存在1個數(shù)與N6距離為1，且與N1距離為4，令該數(shù)記為N5；。。。
????????余者依此類推。
????????滿足條件的N的最小值必然是N1~N7中的最大值，即N=max(N1,N2,…,N7).所以尋找滿足條件的最小的N，就是尋找滿足條件的最小的7個合數(shù)。
????????由于(N1,N2), (N2,N3), …,(N6,N7)的距離分別為1，要使得這些數(shù)最小，它們之間分別應該具有(大于1的)為質數(shù)的唯一的公約數(shù)，分別記為：gcd(N1,N2)=a, gcd(N2,N3)=b, …, gcd(N6,N7)=f（gcd: Greatest Common Divisor, 表示最大公約數(shù)）。因此，N2的最小取值為a*b，N3的最小取值為k3*b*c，…，N6的最小取值為e*f，而N1和N7由于分別可能只有一個好友，它們的取值可以寫為k1*a和k7*f。
????????顯而易見，將{a,b,c,d,e,f}取最小的6個素數(shù)，然后分別令k1=a, k7=f可以滿足以上條件（距離條件，且max(N1,…,N7)最?。?。
? ? ? ??(好吧，承認失敗。本來我是想給出一個嚴格地證明，但是最后看起來如此顯而易見的事情真要給出邏輯嚴謹?shù)淖C明似乎并不是一件容易的事情，最后還是得靠一個“顯而易見”敷衍了事。只嘆：書到用時方恨少，數(shù)學學得太潦草) 先擱在這里，后面有機會再回頭看能不能給出給嚴謹?shù)恼f明。
????????基于以上討論可得，本題求解流程如下所示：
# -*- 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全解
文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉載請注明本文地址：http://systransis.cn/yun/119797.html
摘要：假設有幾個小朋友以相同間隔圍成圓周，要結對用紙杯電話相互通話。如果繩子交叉，很有可能會纏繞起來，所以結對的原則是不能讓繩子交叉。如下所示運行結果上一篇異或楊輝三角形下一篇禁止右轉本系列總目錄參見程序員的算法趣題詳細分析和全解 目錄 1. 問題描述 2. 解題分析 3. 代碼及測試 1. 問...
摘要：結合上下文猜測應該是說沙子同時漏完的意思。問題的焦點在于如何表示不同的排列狀態(tài)以及如何處理沙漏翻轉。上一篇完美洗牌完美洗牌下一篇糖果惡作劇本系列總目錄參見程序員的算法趣題詳細分析和全解程序員的算法趣題詳細分析和全解 目錄 1. 問題描述 1.1 原題的表述 2. 解題分析 2.1 轉換為線...
摘要：面試后面試后及時總結，有可能下一個面試官會問你同樣的問題。同時面試官也對我的未來技術發(fā)展提出了很多建議?？偟膩碚f，四面的氛圍并沒有想象得那么嚴肅，面試官也說面試得很愉快。 ...
摘要：本文經(jīng)授權轉載自有一位供職于阿里的朋友跑來咨詢我一個關于跳槽的問題朋友目前在阿里工作兩年時間，剛拿到頭條的，但非常糾結是否要接，所以來咨詢下我的意見。 本文經(jīng)授權轉載自wingjay（ID：cool-coder）有一位供職于阿里的朋友跑來咨詢我一個關于跳槽的問題：朋友目前在阿里工作兩年時間，剛拿到頭條的 Offer，但非常糾結是否要接，所以來咨詢下我的意見。而正好最近不少我的小專欄讀者...
閱讀 3553·2021-09-10 10:51
閱讀 2524·2021-09-07 10:26
閱讀 2503·2021-09-03 10:41
閱讀 826·2019-08-30 15:56
閱讀 2919·2019-08-30 14:16
閱讀 3508·2019-08-30 13:53
閱讀 2122·2019-08-26 13:48
閱讀 1929·2019-08-26 13:37
