摘要：由此可得初始状态为终止状态黑白或交错有两种，分别是翻转运算在圆圈上翻转连续张牌，可以用一个比特的有个比特为的整数称为掩码与表示排列状态的整数进行按比特异或运算得到。求余部分代表没有移出比特部分的值。
目录
本题关键在于围成一圈的排列以及翻转运算如何表示。
从某处剪开形成线性排列是常用套路。具体从哪里剪开看处理方便。
由于初始位置是黑白各连续N个，用1表示黑，0表示白。标示2*N个位置分别为pos0,pos1,...,pos(2N-1)。令初始状态中，pos0~pos(N-1)为1（即黑色卡片），posN~pos(2N-1)为0（即白色卡片）。
从pos0和pos(2N-1)中间剪开，这个排列可以用一个2N比特的无符号整数{pos(2N-1}, pos(2N-2}, ... , pos0}表示，约定pos0为LSB，pos(2N-1}为MSB。
由此可得：
初始状态为0b000...0111...1 = 2**N-1
终止状态（黑白或01交错）有两种，分别是：0b1010...10, 0b010...101
在圆圈上翻转连续3张牌，可以用一个2*N比特的有3个比特为1的整数（称为掩码）与表示排列状态的整数进行按比特异或运算得到。
在每个状态下，“翻转连续3张牌”的可能位置有2*N种，对应的整数为7, 14, ...。但是要注意翻转位置跨越剪开的那个位置时的处理。比特数比较少的时候，用手动计算出掩码也是可以的。也可以找出规律用代码来实现（这样代码可扩展性更好）。本题解中用以下方式来求2*N种掩码：
(7< 基于以上讨论，这个问题就转化成了图搜索问题中的最短路径问题了，可以用广度优先搜索来解决。 算法流程如下： 长假归来。。。Q48轻松搞定。呃，那一定是我的水平涨了嘛^-^老兵不死他只是慢慢凋零。。。 本系列总目录参见：程序员的算法趣题：详细分析和Python全解 2.3 算法流程
3. 代码及测试
# -*- coding: utf-8 -*-"""Created on Fri Oct 8 07:40:08 2021@author: chenxy"""# import sysimport time# import datetime# import math# import random# from typing import List# from queue import Queuefrom collections import deque# import itertools as it# import numpy as npN = 8target1 = 0b1010_1010_1010_1010target2 = 0b0101_0101_0101_0101start = 0b0000_0000_1111_1111mask = 2*N*[0]for k in range(2*N): mask[k] = (7 << k) // (2**16) + (7 << k) % (2**16)step = 0q = deque()visited = set()q.append((start,step))visited.add(start)while len(q) > 0: cur,step = q.popleft() # print("cur={0}, step={1}".format(cur,step)) if cur == target1 or cur == target2: break for k in range(2*N): nxt = cur ^ mask[k] if nxt not in visited: # print("/t{0}-->{1}".format(cur,nxt)) q.append((nxt,step+1)) visited.add(nxt)print("N = {0}, step = {1}".format(N,step))4. 后记
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/122000.html
摘要：本文先考虑深度优先搜索。深度优先搜索算法流程如下最后，将初始化为，初始化，和分别初始化为适当的全零数组，然后调用到最终退出后所得到的即为所求结果。 目录 1. 问题描述 2. 解题分析 3. 代码及测试 4. 后记 1. 问题描述 2. 解题分析 本题是要找最长路径，应该...
摘要：汉明距离可以用异或操作实现。这个问题其实可以看作是，具有个节点的全连接无向图，每条边的权重值代表两个节点所代表的数字的段码显示的二进制表示之间的汉明距离。 目录 1. 问题描述 2. 解题分析 3. 代码及测试 1. 问题描述 问题：求把10个数字全部显示出来时，亮灯/灭...
摘要：结合上下文猜测应该是说沙子同时漏完的意思。问题的焦点在于如何表示不同的排列状态以及如何处理沙漏翻转。上一篇完美洗牌完美洗牌下一篇糖果恶作剧本系列总目录参见程序员的算法趣题详细分析和全解程序员的算法趣题详细分析和全解 目录 1. 问题描述 1.1 原题的表述 2. 解题分析 2.1 转换为线...
摘要：能以最少交换次数到达升序有序排列记为的数列记为就等价于从代表的节点在这张图中到达对应的节点的最短路径长度。上一篇质数矩阵质数矩阵下一篇唯一的序列本系列总目录参见程序员的算法趣题详细分析和全解程序员的算法趣题详细分析和全解 目录 1. 问题描述 2. 解题分析 3. 代码及测试 4. 后记 ...
阅读 3029·2023-04-26 02:27
阅读 2729·2021-11-22 13:54
阅读 881·2021-11-12 10:36
阅读 3730·2021-10-09 09:44
阅读 3135·2021-10-09 09:41
阅读 1190·2021-09-22 10:02
阅读 2797·2019-08-30 15:56
阅读 3080·2019-08-30 11:02
