程序员的算法趣题|程序员的算法趣题Q51: 同时结束的沙漏算法趣题|python|算法

目录

1. 问题描述
1.1 原题的表述
2. 解题分析
2.1 转换为线性排列
3. 代码及测试
4. 后记
1. 问题描述
文章图片

文章图片

1.1 原题的表述首先，我认为这道题目存在严重的表述问题（是原文的问题还是翻译的问题呢？）。
题干部分多次出现“同时向下落”的说法，稍有常识就知道只要每个沙漏的上半部分都有沙子，那不就时“同时向下落”的情况吗。结合上下文猜测应该是说“沙子同时漏完”的意思。
第一段话的括号里的“计时1分钟时，倒挂一个沙漏；计时2分钟时，倒挂两个沙漏；计时N分钟时，倒挂N个沙漏；”也是显而易见的理解错误。难道即是N+1分钟时，倒挂N+1个沙漏吗？哪来的N+1个沙漏呢？猜测应该是说：当前倒挂操作的起始沙漏为1分钟沙漏时则倒挂一个，为2分钟沙漏时则倒挂两个。。。依此类推。
“补充”说明的第一段所说的跟第二段说的根本就不是一回事。第一段是说想解释倒挂沙漏起始位置不同看作是不同排列，而第二段解释了两种看上去不同的排列（由于圆的对称性的特性）其实是同一种排列，牛头不对马嘴。不过这个有可能不是翻译的问题，而是原文就有问题。
2. 解题分析 【程序员的算法趣题|程序员的算法趣题Q51: 同时结束的沙漏】没有什么花哨（没想到什么花哨），唯有暴力破解。问题的焦点在于如何表示不同的排列状态以及如何处理沙漏翻转。
2.1 转换为线性排列 N个沙漏，圆排列总共有
文章图片
种（与之相对，线性排列的场合是
文章图片
种）。但是，对于每个圆排列，第一次沙漏倒挂操作的起始位置共有N种（其后的沙漏倒挂操作的起始位置是按顺时针旋转），所以{圆排列，首次沙漏倒挂起始位置}组合起来的话就又回到
文章图片
种了。所以可以把沙漏圆形排列还原成线性排列，只不过在线性排列中首次沙漏倒挂总是从排在首位的沙漏开始。只不过，要注意(1)沙漏倒挂起始位置是循环的，(2)连续倒挂多个沙漏时，存在跨越首尾边界的情况，即从尾部回到头部。
以下为一种情况的状态变化示例。

文章图片

这个情况对应于原书的例子，经过6分钟后所有沙漏同时漏光沙子。

3. 代码及测试

# -*- coding: utf-8 -*- """ Created on Mon Oct 11 07:25:51 2021@author: chenxy """# import sys import time # import datetime # import math # import random # fromtyping import List # fromqueue import Queue # fromcollections import deque import itertools as it import 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)%NN= 8 OK_cnt = 0 tStart = time.perf_counter() for state0 in it.permutations(np.arange(N)): rslt, steps = flip_sandclock(state0) if rslt: # print(state0, steps) OK_cnt += 1 tCost= time.perf_counter() - tStart print('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: 完美洗牌
本系列总目录参见：程序员的算法趣题：详细分析和Python全解