摘要：结合上下文猜测应该是说沙子同时漏完的意思。问题的焦点在于如何表示不同的排列状态以及如何处理沙漏翻转。上一篇完美洗牌完美洗牌下一篇糖果恶作剧本系列总目录参见程序员的算法趣题详细分析和全解程序员的算法趣题详细分析和全解
目录
首先，我认为这道题目存在严重的表述问题（是原文的问题还是翻译的问题呢？）。
题干部分多次出现“同时向下落”的说法，稍有常识就知道只要每个沙漏的上半部分都有沙子，那不就时“同时向下落”的情况吗。结合上下文猜测应该是说“沙子同时漏完”的意思。
第一段话的括号里的“计时1分钟时，倒挂一个沙漏；计时2分钟时，倒挂两个沙漏；计时N分钟时，倒挂N个沙漏；”也是显而易见的理解错误。难道即是N+1分钟时，倒挂N+1个沙漏吗？哪来的N+1个沙漏呢？猜测应该是说：当前倒挂操作的起始沙漏为1分钟沙漏时则倒挂一个，为2分钟沙漏时则倒挂两个。。。依此类推。
“补充”说明的第一段所说的跟第二段说的根本就不是一回事。第一段是说想解释倒挂沙漏起始位置不同看作是不同排列，而第二段解释了两种看上去不同的排列（由于圆的对称性的特性）其实是同一种排列，牛头不对马嘴。不过这个有可能不是翻译的问题，而是原文就有问题。
没有什么花哨（没想到什么花哨），唯有暴力破解。问题的焦点在于如何表示不同的排列状态以及如何处理沙漏翻转。
N个沙漏，圆排列总共有 种（与之相对，线性排列的场合是 种）。但是，对于每个圆排列，第一次沙漏倒挂操作的起始位置共有N种（其后的沙漏倒挂操作的起始位置是按顺时针旋转），所以{圆排列，首次沙漏倒挂起始位置}组合起来的话就又回到 种了。所以可以把沙漏圆形排列还原成线性排列，只不过在线性排列中首次沙漏倒挂总是从排在首位的沙漏开始。只不过，要注意(1)沙漏倒挂起始位置是循环的，(2)连续倒挂多个沙漏时，存在跨越首尾边界的情况，即从尾部回到头部。
以下为一种情况的状态变化示例。
这个情况对应于原书的例子，经过6分钟后 所有沙漏同时漏光沙子。
# -*- 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)
再一次遭遇尴尬。抱怨了半天问题描述有问题，最后（在自以为理解正确？的前提下）却没有得出正确的答案。看半天也没有看出个所以然来，不死磕了，嗯，反正也不是第一次了，虽然好像翻车的次数有点多。同往常一样，厚着脸谱挂出来，看看有没有小伙伴帮我指出错误来。
其次，太慢了，10秒钟！代码层面如何优化？
呃。。。等着我回来。
上一篇：Q50: 完美洗牌
下一篇：Q52: 糖果恶作剧
本系列总目录参见：程序员的算法趣题：详细分析和Python全解
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/122319.html
摘要：且听下回分解基于动态规划策略的优化解法参见程序员的算法趣题偷懒的算盘上一篇程序员的算法趣题同数包夹程序员的算法趣题同数包夹本系列总目录参见程序员的算法趣题详细分析和全解程序员的算法趣题详细分析和全解 目录 1. 问题描述 2. 解题分析 3. 代码及测试 4. 后记 1. 问题描述 ...
摘要：假设有几个小朋友以相同间隔围成圆周，要结对用纸杯电话相互通话。如果绳子交叉，很有可能会缠绕起来，所以结对的原则是不能让绳子交叉。如下所示运行结果上一篇异或杨辉三角形下一篇禁止右转本系列总目录参见程序员的算法趣题详细分析和全解 目录 1. 问题描述 2. 解题分析 3. 代码及测试 1. 问...
摘要：可以在遍历所有矩阵时，对各种出现的次数进行计数，最后计数值为的个数即为所求结果。上一篇排序交换次数的最少化排序交换次数的最少化本系列总目录参见程序员的算法趣题详细分析和全解程序员的算法趣题详细分析和全解 目录 1. 问题描述 2. 解题分析 3. 代码及测试 4. 后记 1. 问题描述 ...
阅读 2255·2021-11-25 09:43
阅读 3121·2021-10-14 09:42
阅读 3484·2021-10-12 10:12
阅读 1526·2021-09-07 10:17
阅读 1899·2019-08-30 15:54
阅读 3180·2019-08-30 15:54
阅读 1550·2019-08-30 15:53
阅读 1907·2019-08-29 11:21
