目錄

1. 問(wèn)題描述

1.1 原題的表述

2. 解題分析

2.1 轉(zhuǎn)換為線性排列

3. 代碼及測(cè)試

4. 后記

1. 問(wèn)題描述

1.1 原題的表述

????????首先，我認(rèn)為這道題目存在嚴(yán)重的表述問(wèn)題（是原文的問(wèn)題還是翻譯的問(wèn)題呢？）。

????????題干部分多次出現(xiàn)“同時(shí)向下落”的說(shuō)法，稍有常識(shí)就知道只要每個(gè)沙漏的上半部分都有沙子，那不就時(shí)“同時(shí)向下落”的情況嗎。結(jié)合上下文猜測(cè)應(yīng)該是說(shuō)“沙子同時(shí)漏完”的意思。

????????第一段話的括號(hào)里的“計(jì)時(shí)1分鐘時(shí)，倒掛一個(gè)沙漏；計(jì)時(shí)2分鐘時(shí)，倒掛兩個(gè)沙漏；計(jì)時(shí)N分鐘時(shí)，倒掛N個(gè)沙漏；”也是顯而易見(jiàn)的理解錯(cuò)誤。難道即是N+1分鐘時(shí)，倒掛N+1個(gè)沙漏嗎？哪來(lái)的N+1個(gè)沙漏呢？猜測(cè)應(yīng)該是說(shuō)：當(dāng)前倒掛操作的起始沙漏為1分鐘沙漏時(shí)則倒掛一個(gè)，為2分鐘沙漏時(shí)則倒掛兩個(gè)。。。依此類推。

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

2. 解題分析

????????沒(méi)有什么花哨（沒(méi)想到什么花哨），唯有暴力破解。問(wèn)題的焦點(diǎn)在于如何表示不同的排列狀態(tài)以及如何處理沙漏翻轉(zhuǎn)。

2.1 轉(zhuǎn)換為線性排列

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

????????以下為一種情況的狀態(tài)變化示例。

????????這個(gè)情況對(duì)應(yīng)于原書(shū)的例子，經(jīng)過(guò)6分鐘后?所有沙漏同時(shí)漏光沙子。

3. 代碼及測(cè)試

# -*- 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)) 

運(yùn)行結(jié)果：

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

4. 后記

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

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

? ? ? ? 呃。。。等著我回來(lái)。

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

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

????????本系列總目錄參見(jiàn)：程序員的算法趣題：詳細(xì)分析和Python全解