我正在解決 USACO 培訓中的以下問題。我發現這個非常快速的解決方案，我發現它無法完全吸收。
問題：考慮一個由 N (1 <= N <= 31) 位組成的有序字串集合 S。當然，位是 0 或 1。
這組字串很有趣，因為它是有序的并且包含所有可能的長度為 N 且具有 L (1 <= L <= N) 或更少位為“1”的字串。
你的任務是從輸入中讀取一個數字 I (1 <= I <= sizeof(S)) 并列印 N 位的有序集合的第 I 個元素，其中不超過 L 位為“1”。
樣本輸入：5 3 19 輸出：10110
我能想到的兩種解決方案： 首先，通過所有可能的位組合的蠻力解決方案，選擇并存盤'1'的計數小于等于'L'的字串并回傳第I個字串。
其次，我們可以從count（0到L）范圍內的5個位置找到'1'的所有排列，將字串按升序排序并回傳第I個字串。
最佳解決方案： 發布解決方案的 OP 使用組合而不是排列。據他介紹，可能的字串總數為 5C0 5C1 5C2 5C3。
因此，在字串的每個位置 i，我們根據構建字串其余部分的方法總數來決定是否在輸出中包含第 i 位。下面是上述輸入的整個方法的試運行。
N = 5, L = 3, I = 19
00000
at i = 0, for the rem string, we have 4C0 4C1 4C2 4C3 = 15
It says that, there are 15 other numbers possible with the last 4 positions. as 15 is less than 19, our first bit has to be set.
N = 5, L = 2, I = 4
10000
at i = 1, we have 3C0 3C1 3C2 (as we have used 1 from L) = 7
as 7 is greater than 4, we cannot set this bit.
N = 5, L = 2, I = 4
10000
at i = 2 we have 2C0 2C2 = 2
as 2 <= I(4), we take this bit in our output.
N = 5, L = 1, I = 2
10100
at i = 3, we have 1C0 1C1 = 2
as 2 <= I(2) we can take this bit in our output.
as L == 0, we stop and 10110 is our answer. I was amazed to find this solution. However, I am finding it difficult to get the intuition behind this solution.
這個解決方案如何將零直接歸入集合中的第 I 個數？
為什么在設定位的組合中位的順序無關緊要？
uj5u.com熱心網友回復：
假設我們已經預先計算了長度為 n 且設定了 k 位或更少位的字串的數量。稱之為 S(n, k)。
現在假設我們想要第 i 個長度為 N 的字串（按字典順序），其中設定了 L 位或更少的位。
所有最高有效位為零的字串都在最高有效位 1 之前。最高有效位為零的字串有 S(N-1,L) 個字串，最高有效位為零的字串有 S(N-1,L-1) 個字串最高有效位 1。因此，如果我們想要第 i 個字串，如果 i<=S(N-1, L)，那么它的最高位必須為零，余數必須是長度為 N-的第 i 個字串1 最多設定 L 位，否則它的最高位必須為 1，余數必須是長度為 N-1 且最多設定 L-1 位的第 (iS(N-1, L)) 字串.
剩下的代碼就是預先計算 S(n, k) 并處理基本情況。
您可以像您的朋友那樣找出 S(n, k) 的組合解決方案，但使用遞回關系更實用：S(n, k) = S(n-1, k) S(n-1 , k-1) 和 S(0, k) = S(n, 0) = 1。
這是完成所有這些的代碼，例如，按字典順序列印出所有設定了 3 位或更少位的 8 位數字。如果i超出范圍，那么它會引發IndexError例外，盡管在您的問題中您假設i始終在范圍內，所以也許這沒有必要。
S = [[1] * 32 for _ in range(32)]
for n in range(1, 32):
for k in range(1, 32):
S[n][k] = S[n-1][k] S[n-1][k-1]
def ith_string(n, k, i):
if n == 0:
if i != 1:
raise IndexError
return ''
elif i <= S[n-1][k]:
return "0" ith_string(n-1, k, i)
elif k == 0:
raise IndexError
else:
return "1" ith_string(n-1, k-1, i - S[n-1][k])
print([ith_string(8, 3, i) for i in range(1, 94)])
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/514871.html
標籤：算法数据结构位操作
上一篇：將遞回轉換為動態