資訊專欄INFORMATION COLUMN
摘要：由此可得初始狀態為終止狀態黑白或交錯有兩種，分別是翻轉運算在圓圈上翻轉連續張牌，可以用一個比特的有個比特為的整數稱為掩碼與表示排列狀態的整數進行按比特異或運算得到。求余部分代表沒有移出比特部分的值。
目錄
????????本題關鍵在于圍成一圈的排列以及翻轉運算如何表示。
????????從某處剪開形成線性排列是常用套路。具體從哪里剪開看處理方便。
? ? ?由于初始位置是黑白各連續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輕松搞定。呃，那一定是我的水平漲了嘛^-^老兵不死他只是慢慢凋零。。。 ? ? ? ? 上一篇：程序員的算法趣題Q47: 格雷碼循環 ? ? ? ? 下一篇：程序員的算法趣題Q49: 欲速則不達 ????????本系列總目錄參見：程序員的算法趣題：詳細分析和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. 后記
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/122000.html
摘要：本文先考慮深度優先搜索。深度優先搜索算法流程如下最后，將初始化為，初始化，和分別初始化為適當的全零數組，然后調用到最終退出后所得到的即為所求結果。 目錄 1. 問題描述 2. 解題分析 3. 代碼及測試 4. 后記 1. 問題描述 2. 解題分析 ????????本題是要找最長路徑，應該...
摘要：漢明距離可以用異或操作實現。這個問題其實可以看作是，具有個節點的全連接無向圖，每條邊的權重值代表兩個節點所代表的數字的段碼顯示的二進制表示之間的漢明距離。 目錄 1. 問題描述 2. 解題分析 3. 代碼及測試 1. 問題描述 ????????問題：求把10個數字全部顯示出來時，亮燈/滅...
摘要：結合上下文猜測應該是說沙子同時漏完的意思。問題的焦點在于如何表示不同的排列狀態以及如何處理沙漏翻轉。上一篇完美洗牌完美洗牌下一篇糖果惡作劇本系列總目錄參見程序員的算法趣題詳細分析和全解程序員的算法趣題詳細分析和全解 目錄 1. 問題描述 1.1 原題的表述 2. 解題分析 2.1 轉換為線...
摘要：能以最少交換次數到達升序有序排列記為的數列記為就等價于從代表的節點在這張圖中到達對應的節點的最短路徑長度。上一篇質數矩陣質數矩陣下一篇唯一的序列本系列總目錄參見程序員的算法趣題詳細分析和全解程序員的算法趣題詳細分析和全解 目錄 1. 問題描述 2. 解題分析 3. 代碼及測試 4. 后記 ...
閱讀 3046·2023-04-26 02:27
閱讀 2763·2021-11-22 13:54
閱讀 902·2021-11-12 10:36
閱讀 3753·2021-10-09 09:44
閱讀 3177·2021-10-09 09:41
閱讀 1222·2021-09-22 10:02
閱讀 2833·2019-08-30 15:56
閱讀 3103·2019-08-30 11:02
