目錄
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 sys
import time
import datetime
import math
# import random
from typing import List
# from queue import Queue
# from collections import deque
import itertools as it
prime = [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.uj5u.com/qita/298889.html
標籤：其他