目錄

1. 問題描述

1.1 原題的表述

2. 解題分析

2.1 轉換為線性排列

3. 代碼及測試

4. 后記

1. 問題描述

1.1 原題的表述

????????首先，我認為這道題目存在嚴重的表述問題（是原文的問題還是翻譯的問題呢？）。

????????題干部分多次出現“同時向下落”的說法，稍有常識就知道只要每個沙漏的上半部分都有沙子，那不就時“同時向下落”的情況嗎。結合上下文猜測應該是說“沙子同時漏完”的意思。

????????第一段話的括號里的“計時1分鐘時，倒掛一個沙漏；計時2分鐘時，倒掛兩個沙漏；計時N分鐘時，倒掛N個沙漏；”也是顯而易見的理解錯誤。難道即是N+1分鐘時，倒掛N+1個沙漏嗎？哪來的N+1個沙漏呢？猜測應該是說：當前倒掛操作的起始沙漏為1分鐘沙漏時則倒掛一個，為2分鐘沙漏時則倒掛兩個。。。依此類推。

????????“補充”說明的第一段所說的跟第二段說的根本就不是一回事。第一段是說想解釋倒掛沙漏起始位置不同看作是不同排列，而第二段解釋了兩種看上去不同的排列（由于圓的對稱性的特性）其實是同一種排列，牛頭不對馬嘴。不過這個有可能不是翻譯的問題，而是原文就有問題。?

2. 解題分析

????????沒有什么花哨（沒想到什么花哨），唯有暴力破解。問題的焦點在于如何表示不同的排列狀態以及如何處理沙漏翻轉。

2.1 轉換為線性排列

????????N個沙漏，圓排列總共有 種（與之相對，線性排列的場合是 種）。但是，對于每個圓排列，第一次沙漏倒掛操作的起始位置共有N種（其后的沙漏倒掛操作的起始位置是按順時針旋轉），所以{圓排列，首次沙漏倒掛起始位置}組合起來的話就又回到 種了。所以可以把沙漏圓形排列還原成線性排列，只不過在線性排列中首次沙漏倒掛總是從排在首位的沙漏開始。只不過，要注意(1)沙漏倒掛起始位置是循環的，(2)連續倒掛多個沙漏時，存在跨越首尾邊界的情況，即從尾部回到頭部。

????????以下為一種情況的狀態變化示例。

????????這個情況對應于原書的例子，經過6分鐘后?所有沙漏同時漏光沙子。

3. 代碼及測試

# -*- coding: utf-8 -*-"""Created on Mon Oct 11 07:25:51 2021@author: chenxy"""# import sysimport time# import datetime# import math# import random# from   typing import List# from   queue import Queue# from   collections import dequeimport itertools as itimport numpy as npdef flip_sandclock(state0):    timer   = 0    state0  = np.array(state0) + 1 # Convert to 1~N    cur     = state0     # print(state0)        visited = set()    flip_start = 0    while 1:                cur_state  = tuple(list(cur)+[flip_start])        if cur_state in visited:            return False, -1          visited.add(cur_state)                # 1 minute later        nxt   = cur - 1 # Using numpy broadcasting        nxt[nxt<0] = 0 # If no sand in the up half, keep it empty.        # print(nxt)                      if np.array_equal(nxt, np.zeros(N,dtype="int")):            return True, len(visited)                        # Flip the sand clocks        for k in range(flip_start, flip_start + state0[flip_start]):            m = k%N            nxt[m] = state0[m] - nxt[m]        cur = nxt        flip_start = (flip_start + 1)%N               N      = 8OK_cnt = 0tStart = time.perf_counter()for state0 in it.permutations(np.arange(N)):    rslt, steps = flip_sandclock(state0)    if rslt    :        # print(state0, steps)        OK_cnt += 1tCost  = time.perf_counter() - tStartprint("N={0}, OK_cnt={1}, tCost = {2:6.3f}(sec)".format(N,OK_cnt,tCost)) 

運行結果：

????????N=8, OK_cnt=11897, tCost = 10.633(sec)

4. 后記

? ? ? ? 再一次遭遇尷尬。抱怨了半天問題描述有問題，最后（在自以為理解正確？的前提下）卻沒有得出正確的答案。看半天也沒有看出個所以然來，不死磕了，嗯，反正也不是第一次了，雖然好像翻車的次數有點多。同往常一樣，厚著臉譜掛出來，看看有沒有小伙伴幫我指出錯誤來。

? ? ? ? 其次，太慢了，10秒鐘！代碼層面如何優化？

? ? ? ? 呃。。。等著我回來。

? ? ? ? 上一篇：Q50: 完美洗牌

? ? ? ? 下一篇：Q52: 糖果惡作劇

????????本系列總目錄參見：程序員的算法趣題：詳細分析和Python全解