目錄
1. 問題描述
2. 解題分析--深度優先搜尋
3. 代碼及測試
代碼實作有兩個小細節值得一提：
運作結果如下：
1. 問題描述
日本每月的 22 日是水果酥餅日。因為看月曆的時候， 22 日的上方剛好是 15日，也就是“‘22’這個數字上面點綴着草莓”(如果将日語的 15 拆為 1 和 5發音[イチゴ]，則與日語“草莓[イチゴ]”一詞發音相同，而水果酥餅中最為著名的就是草莓酥餅)
切分酥餅的時候，要求切分後每一塊上面的草莓個數都不相同。假設切分出來的 N 塊酥餅上要各有“1~N 個（共 N(N ＋ 1)÷2 個草莓）”。但這裡要追加一個條件，那就是“一定要使相鄰的兩塊酥餅上的數字之和是平方數”。
舉個例子，假設 N ＝ 4 時采用如下圖的切法。這時，雖然 1 ＋ 3 ＝4 得到的是平方數，但“1 和 4” “2和 3” “2 和 4”的部分都不滿足條件。
2. 解題分析--深度優先搜尋
本題等價于這樣一個問題：求[1…N]的一個圓排列（circular permutation）,使得任意相鄰兩個數之和為完全平方數。
作為一個直覺的辦法，可以考慮周遊[1,…,N]的圓排列，然後檢驗每一個圓排列是否滿足條件。然後對N進行從小到大周遊，直到找到一個N使得對于這個N存在一個滿足條件的圓排列。但是對于N來說，圓排列數等于(N-1)!(注意，由于圓排列的對稱性，如果隻考慮各個數的相對位置的話，N個線性排列對應于同一個圓排列)。對于略大的N這個需要周遊的排列數将無法忍受。
本題可以用深度優先搜尋算法來解決。除了問題的表象以外，本題作為一個深度優先搜尋問題與Q14非常相似，可以用幾乎相同的方式解決。
從1開始，尋找與它的和能構成完全平方數的數（看作是1的子節點），然後針對1的子節點進一步尋找與它的和能構成完全平方數的子節點。。。
一個圓排列對應一個深度優先搜尋路徑。由于在圓排列中每個數隻能用一次，是以用used和unused分别表示已經使用的數和尚未使用的數。進一步的exploration僅從unused中選取下一個探索對象，是以省掉了“是否已被通路過”的檢查判斷，另一方面，used是按照通路順序存入被通路對象，是以其中存儲的就是目前搜尋的接龍順序。used和unused都需要以棧的方式進行管理，是以如果用遞歸調用的方式實作的話，将它們作為遞歸函數的接口參數傳遞即可；如果用循環方式實作的話，則需要注意顯式的入棧和出棧管理。
如果used的長度等于N，并且首尾的和也是完全平方數的話就表示找到了一個符号條件的圓排列。此時的used中存儲的就是對應的圓排列。
與Q14不同的是，從任何一點開始搜尋圓排列都是等價的，是以不需要針對起點周遊，固定從1開始即可。
算法流程（python-style僞代碼）如下圖所示：
以下是針對N=10和N=20的筆算示意圖（如果可能的話，在紙上進行一些計算有助于建立對問題的直覺感覺，我認為是非常有用。隻不過N=20時居然能走這麼遠一開始沒想到，否則的話可能就不敢挑戰了）。
3. 代碼及測試
# -*- coding: utf-8 -*-
"""
Created on Tue Sep 7 07:11:00 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
class Solution:
def cutFruitCake(self, N:int)->(bool,List):
"""
Given an integer, find one circular permutation of 1...N, satisfying
the condition that the sum of each pair of neighbours is one complete
square number
Parameters
----------
N : int.
Returns : True or False to indicate whether such circular permutation exists,
and if True, the circular permutation
-------
"""
squNum = [k*k for k in range(N)]
def explore(used, unused):
if len(used)==N and (used[0]+used[-1]) in squNum:
# print(used)
return True, used
cur = used[-1]
cutOK = False
for k,nxt in enumerate(unused):
if cur+nxt in squNum:
cutOK,finalCut = explore(used+[nxt], unused[:k]+unused[k+1:])
if cutOK:
return True,finalCut
return False,[]
used = [1]
unused = [k for k in range(2,N+1)]
return explore(used,unused)
if __name__ == '__main__':
sln = Solution()
tStart = time.time()
N = 2
while (1):
cutOK, finalCut = sln.cutFruitCake(N)
if cutOK:
break
print('N = {0}: Fail'.format(N))
N += 1
tCost = time.time() - tStart
print('The minimum integer satisfying the condition is:\nN={0}, tCost = {1:6.3f}(sec)'.format(N,tCost))
print('finalCut = {0}'.format(finalCut))
代碼實作有兩個小細節值得一提：
(1) 預計算的完全平方數清單用于提高是否平方數的檢驗效率。如果用dict()來存儲完全平方數用于查詢應該會更快
(2) 深度搜尋是線性向前的，但是到最後不能忘記首尾是否滿足條件的判斷：used[0]+used[-1]
運作結果如下：
The minimum integer satisfying the condition is:
N=32, tCost = 0.868(sec)
finalCut = [1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11, 5, 31, 18, 7, 29, 20, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15]
上一篇：Q17：30人31足遊戲
下一篇：
本系列總目錄參見：程式員的算法趣題：詳細分析和Python全解