資訊專欄INFORMATION COLUMN
摘要：的結果與原書的結果不符。上一篇程序員的算法趣題欲速則不達程序員的算法趣題欲速則不達下一篇程序員的算法趣題同時結束的沙漏本系列總目錄參見程序員的算法趣題詳細分析和全解程序員的算法趣題詳細分析和全解
目錄
????????問題：對2n張牌洗牌，并求當1<=n<=100時，一共有多少個n可以使得經過2(n-1)次洗牌后，恢復最初順序？分兩種情況考慮：
????????Case1: 2(n-1)次洗牌后，牌恢復最初順序
????????Case2: 2(n-1)次洗牌后第一次恢復順序
????????Case2可以看作是case1的一種特殊情況。Case1的意思是，如果在m{其中m為2(n-1)的因子}次洗牌后回復最初順序即可。
????????第一感是以下這個‘高大上’的想法：
????????呃。。。雖說如此，群論只學了一丟丟。。。等我先把群論學一學再來看這條路能不能走通。本系列其實出現過好幾道可以用群論來解決的問題。群論學習從開始到放棄經歷過好多次了，這次帶著問題去學習看看能不能走得遠一些。?
????????（沒有別的更炫的法子時）蠻干就是了。。。
????????針對每一個n，從初始狀態（初始狀態是什么并不重要）開始，以迭代的方式進行以上permutation操作，并判斷是否回到了最初狀態。
????????算法流程如下：
# -*- coding: utf-8 -*-"""Created on Sat Oct 9 19:33:11 2021@author: chenxy"""# import sysimport time# import datetime# import math# import random# from typing import List# from queue import Queue# from collections import deque# import itertools as itimport numpy as npN = 100ok_list = []tStart = time.perf_counter()for n in range(1,N+1): start = np.arange(2*n) p = np.zeros_like(start) for k in range(n): p[2*k] = start[k] p[2*k+1] = start[n+k] # print(p) cur = start cnt = 0 # recover = False while 1: cur = cur[p] cnt = cnt + 1 if np.array_equal(cur, start): # print(n, cur, start, cnt) if (2*(n-1) % cnt) == 0: # if (2*(n-1)) == cnt: # print(n, cur, start, cnt) # recover = True ok_list.append(n) break if cnt > 2*(n-1): break # if recover: # ok_list.append(n)tCost = time.perf_counter() - tStart print("length of ok_list = {0}, tCost = {1:6.3f}(sec)".format(len(ok_list),tCost))print(ok_list) case1運行結果：
length of ok_list = 46, tCost = ?0.046(sec)
[1, 2, 3, 4, 6, 7, 9, 10, 12, 15, 16, 19, 21, 22, 24, 27, 30, 31, 34, 36, 37, 40, 42, 45, 49, 51, 52, 54, 55, 57, 64, 66, 69, 70, 75, 76, 79, 82, 84, 87, 90, 91, 96, 97, 99, 100]
case2運行結果（注釋掉 "if (2*(n-1) % cnt) == 0:"，打開 “?if (2*(n-1)) == cnt:）"：
length of ok_list = 45, tCost = ?0.059(sec)
[2, 3, 4, 6, 7, 9, 10, 12, 15, 16, 19, 21, 22, 24, 27, 30, 31, 34, 36, 37, 40, 42, 45, 49, 51, 52, 54, 55, 57, 64, 66, 69, 70, 75, 76, 79, 82, 84, 87, 90, 91, 96, 97, 99, 100]
????????尷尬。。。case2的結果與原書的結果不符。想不出哪里不對，哪個小伙伴看出來毛病來了請不吝指教^-^
? ? ? ? 兩個遺留事項：
? ? ? ? (1) 基于群論的解決方法
? ? ? ? (2) case2的結果不對
? ? ? ? 嗯，我一定會回來的。。。
? ? ? ? 上一篇：程序員的算法趣題Q49: 欲速則不達
? ? ? ? 下一篇：程序員的算法趣題Q51: 同時結束的沙漏
????????本系列總目錄參見：程序員的算法趣題：詳細分析和Python全解
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/122179.html
摘要：本文先考慮深度優先搜索。深度優先搜索算法流程如下最后，將初始化為，初始化，和分別初始化為適當的全零數組，然后調用到最終退出后所得到的即為所求結果。 目錄 1. 問題描述 2. 解題分析 3. 代碼及測試 4. 后記 1. 問題描述 2. 解題分析 ????????本題是要找最長路徑，應該...
摘要：且聽下回分解基于動態規劃策略的優化解法參見程序員的算法趣題偷懶的算盤上一篇程序員的算法趣題同數包夾程序員的算法趣題同數包夾本系列總目錄參見程序員的算法趣題詳細分析和全解程序員的算法趣題詳細分析和全解 目錄 1. 問題描述 2. 解題分析 3. 代碼及測試 4. 后記 1. 問題描述 ??...
摘要：假設有幾個小朋友以相同間隔圍成圓周，要結對用紙杯電話相互通話。如果繩子交叉，很有可能會纏繞起來，所以結對的原則是不能讓繩子交叉。如下所示運行結果上一篇異或楊輝三角形下一篇禁止右轉本系列總目錄參見程序員的算法趣題詳細分析和全解 目錄 1. 問題描述 2. 解題分析 3. 代碼及測試 1. 問...
摘要：可以在遍歷所有矩陣時，對各種出現的次數進行計數，最后計數值為的個數即為所求結果。上一篇排序交換次數的最少化排序交換次數的最少化本系列總目錄參見程序員的算法趣題詳細分析和全解程序員的算法趣題詳細分析和全解 目錄 1. 問題描述 2. 解題分析 3. 代碼及測試 4. 后記 1. 問題描述 ...
閱讀 2107·2021-11-11 16:55
閱讀 3178·2021-10-11 10:58
閱讀 3052·2021-09-13 10:28
閱讀 3982·2021-07-26 23:57
閱讀 1031·2019-08-30 15:56
閱讀 1339·2019-08-29 13:15
閱讀 1274·2019-08-26 18:18
閱讀 1278·2019-08-26 13:44
