如何创建另一个保证预测的数组集

Question

  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) linear.

Answer 1

它的工作方式实际上只是二进制编码。如果卡 n 的第 n 位（从右边开始）已打开，则卡 n 上存在一个数字。

因此，例如，19 = 10011₂，因此它出现在卡片 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))

Try it online!

我注意到您也提到了时间复杂度限制。我还没有检查我的代码是否符合这一点——我的目标纯粹是演示它可能是什么样子——可能有一种更有效的方法来获取所有数字的列表，并打开该位（尽管，我认为这实际上是 O(n log n)，但我不确定）。

如何创建另一个保证预测的数组集

How to create another array set that guarantees prediction

python

arrays

algorithm

validation