Card#0 Card#1 Card#2 Card#3 Card#4
1, 3, 5, 7 2, 3, 6, 7 4, 5, 6, 7 8, 9, 10,11 16, 17, 18, 19
9, 11, 13, 15 10,11,14,15 12,13,14,15 12,13,14,15 20, 21, 22, 23
17, 19, 21, 23 18,19,22,23 20,21,22,23 24,25,26,27 24, 25, 26, 27
25, 27, 29, 31 26,27,30,31 28,29,30,31 28,29,30,31 28, 29, 30, 31
這可以預測 1 到 31 之間的任何數字。因此它可以通過告訴程式員自己的數字出現在哪些卡片中來預測你的生日。卡上出現的數字。
例如：
我選擇的數字是 27。#27 出現在卡片 #0、1、3、4 上。出現在每張卡片上的相應第一個數字是 #1 2 8 16 = 27
通過知道做這個算術，我相信我們看到了一個 log(n) 演算法被使用，因為它將代碼切成兩半并在大約 2-3 個函式中完成。
我的問題是如何通過增加引數號來擴展這個陣列集，以創建更多可以完美排序的陣列集，并且會產生超過 #4 的額外卡片。換句話說，我怎樣才能使這個代碼預測引數更寬，并且仍然執行 O(log(n) 線性。
uj5u.com熱心網友回復：
這種作業方式實際上只是二進制編碼。n如果第nth 位（從右側開始）打開，則卡上存在一個數字。
因此，例如， 19 = 10011 2，因此它顯示在卡片 0、1 和 4 上。
因此，如果你想讓這個系統適用于數字1..n，你只需要卡片的數量等于 中的位數n。然后，在每張卡片上，只包含所有翻轉了該位的數字。
這是一個演示，但請花時間考慮如何首先實作它，然后嘗試理解我的代碼，而不是復制它：
n = int(input())
digits = len(bin(n)) - 2
def get_card(place):
card = []
for x in range(1, n 1):
if x & (1 << place):
card.append(x)
return card
for x in range(digits):
print(f"Card {x 1}:", get_card(x))
在線試試吧！
我注意到您也提到了時間復雜度限制。我還沒有檢查我的代碼是否符合那個 - 我在這里的目標純粹是演示它可能是什么樣子 - 可能有一種更有效的方法來獲取翻轉該位的所有數字的串列（盡管，我認為這實際上是O(n log n)，但我不確定）。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/362609.html