程序員的算法趣題Q48: 翻轉(zhuǎn)得到交錯(cuò)排列

lvzishen 發(fā)布于2021-10-09 09:44 / 3761人閱讀

摘要：由此可得初始狀態(tài)為終止?fàn)顟B(tài)黑白或交錯(cuò)有兩種，分別是翻轉(zhuǎn)運(yùn)算在圓圈上翻轉(zhuǎn)連續(xù)張牌，可以用一個(gè)比特的有個(gè)比特為的整數(shù)稱為掩碼與表示排列狀態(tài)的整數(shù)進(jìn)行按比特異或運(yùn)算得到。求余部分代表沒(méi)有移出比特部分的值。

1. 問(wèn)題描述

1. 問(wèn)題描述

2. 解題分析

????????本題關(guān)鍵在于圍成一圈的排列以及翻轉(zhuǎn)運(yùn)算如何表示。

2.1 圓圈排列的表示

????????從某處剪開(kāi)形成線性排列是常用套路。具體從哪里剪開(kāi)看處理方便。

? ? ?由于初始位置是黑白各連續(xù)N個(gè)，用1表示黑，0表示白。標(biāo)示2*N個(gè)位置分別為pos0,pos1,...,pos(2N-1)。令初始狀態(tài)中，pos0~pos(N-1)為1（即黑色卡片），posN~pos(2N-1)為0（即白色卡片）。

????????從pos0和pos(2N-1)中間剪開(kāi)，這個(gè)排列可以用一個(gè)2N比特的無(wú)符號(hào)整數(shù){pos(2N-1}, pos(2N-2}, ... , pos0}表示，約定pos0為L(zhǎng)SB，pos(2N-1}為MSB。

????????由此可得：

????????初始狀態(tài)為0b000...0111...1 = 2**N-1

????????終止?fàn)顟B(tài)（黑白或01交錯(cuò)）有兩種，分別是：0b1010...10, 0b010...101

2.2 翻轉(zhuǎn)運(yùn)算

????????在圓圈上翻轉(zhuǎn)連續(xù)3張牌，可以用一個(gè)2*N比特的有3個(gè)比特為1的整數(shù)（稱為掩碼）與表示排列狀態(tài)的整數(shù)進(jìn)行按比特異或運(yùn)算得到。

????????在每個(gè)狀態(tài)下，“翻轉(zhuǎn)連續(xù)3張牌”的可能位置有2*N種，對(duì)應(yīng)的整數(shù)為7, 14, ...。但是要注意翻轉(zhuǎn)位置跨越剪開(kāi)的那個(gè)位置時(shí)的處理。比特?cái)?shù)比較少的時(shí)候，用手動(dòng)計(jì)算出掩碼也是可以的。也可以找出規(guī)律用代碼來(lái)實(shí)現(xiàn)（這樣代碼可擴(kuò)展性更好）。本題解中用以下方式來(lái)求2*N種掩碼：

????????(7<

?2.3 算法流程

????????基于以上討論，這個(gè)問(wèn)題就轉(zhuǎn)化成了圖搜索問(wèn)題中的最短路徑問(wèn)題了，可以用廣度優(yōu)先搜索來(lái)解決。

????????算法流程如下：

3. 代碼及測(cè)試

# -*- 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))