您当前的位置:首页 > 计算机 > 编程开发 > 数据结构与算法

程序员的算法趣题Q48: 翻转得到交错排列

时间:12-31来源:作者:点击数:

1. 问题描述

2. 解题分析

本题关键在于围成一圈的排列以及翻转运算如何表示。

2.1 圆圈排列的表示

从某处剪开形成线性排列是常用套路。具体从哪里剪开看处理方便。

由于初始位置是黑白各连续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

2.2 翻转运算

在圆圈上翻转连续3张牌,可以用一个2*N比特的有3个比特为1的整数(称为掩码)与表示排列状态的整数进行按比特异或运算得到。

在每个状态下,“翻转连续3张牌”的可能位置有2*N种,对应的整数为7, 14, ...。但是要注意翻转位置跨越剪开的那个位置时的处理。比特数比较少的时候,用手动计算出掩码也是可以的。也可以找出规律用代码来实现(这样代码可扩展性更好)。本题解中用以下方式来求2*N种掩码:

(7<<k)对应于没有位宽限制时从7(0b111)出发的线性左移。求余部分代表没有移出2*N比特部分的值。移出的部分在循环左移中挪到了最右端,对应于以上整除部分。

2.3 算法流程

基于以上讨论,这个问题就转化成了图搜索问题中的最短路径问题了,可以用广度优先搜索来解决。

算法流程如下:

3. 代码及测试

# -*- coding: utf-8 -*-
"""
Created on Fri Oct  8 07:40:08 2021

@author: chenxy
"""

# import sys
import time
# import datetime
# import math
# import random
# from   typing import List
# from   queue import Queue
from   collections import deque
# import itertools as it
# import numpy as np

N       = 8
target1 = 0b1010_1010_1010_1010
target2 = 0b0101_0101_0101_0101
start   = 0b0000_0000_1111_1111

mask    = 2*N*[0]
for k in range(2*N):
    mask[k] = (7 << k) // (2**16) + (7 << k) % (2**16)

step    = 0
q       = 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. 后记

长假归来。。。Q48轻松搞定。呃,那一定是我的水平涨了嘛^-^老兵不死他只是慢慢凋零。。。

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门