2025年3月16日 星期日 甲辰(龙)年 月十五 设为首页 加入收藏
rss
您当前的位置:首页 > 计算机 > 编程开发 > 数据结构与算法

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

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

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轻松搞定。呃,那一定是我的水平涨了嘛^-^老兵不死他只是慢慢凋零。。。

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