1

首先让我明确一点，这是一个人为的例子，而不是现实世界的问题。

如果我在创建 0 到 10 之间的随机数时遇到问题。我这样做 11 次以确保不会再次绘制先前出现的数字，如果我得到一个重复的数字，我会再次创建另一个随机数以确保它有不早见。所以基本上我得到一个从 0 到 10 以随机顺序排列的唯一数字序列，例如 3 1 2 0 5 9 4 8 10 6 7 等等

现在想出逻辑来确保随机数是唯一的，而不是我们之前绘制的，我们可以使用多种方法

使用 C++std::bitset并将索引对应的位设置为每个随机数的值。下次抽到新的随机数时再检查。

或者

使用 astd::map<int,int>来计算次数，甚至是简单的 C 数组，其中一些标记值存储在该数组中，以指示该数字是否发生。

如果我必须避免上述这些方法并使用一些数学/逻辑/按位运算来查找之前是否已绘制随机数，有没有办法？

4

5 回答 5

3

你不想按照你建议的方式去做。考虑一下当您已经选择了 11 个项目中的 10 个时会发生什么；您的随机数生成器将循环直到找到丢失的数字，这可能永远不会，这取决于您的随机数生成器。

更好的解决方案是按顺序创建一个 0 到 10 的数字列表，然后将列表随机排列。执行此操作的常规算法归功于 Knuth、Fisher 和 Yates：从第一个元素开始，将每个元素与一个位置比数组中当前元素大的元素交换。

function shuffle(a, n)
    for i from n-1 to 1 step -1
        j = randint(i)
        swap(a[i], a[j])

我们假设一个索引为 0 到 n-1 的数组，以及一个将 j 设置为 0 <= j <= i 的范围的 randint 函数。

于 2012-12-10T13:59:44.477 回答
1

使用一个数组并向其中添加所有可能的值。然后从阵列中挑选一个并将其移除。下一次，再次选择，直到数组为空。

于 2012-12-10T13:26:16.283 回答
1

是的，有一种数学方法可以做到这一点，但它有点宽泛。

有一个数组：primes[]where primes[i] = the i'th prime number. 所以它的开始将是[2,3,5,7,11,...]。

还存储一个数字mult现在，一旦您绘制了一个数字（让它成为i），您检查是否mult % primes[i] == 0，如果是 - 之前绘制的数字，如果不是 - 那么数字不是。选择它并做mult = mult * primes[i]。

然而，它是可扩展的，因为它可能需要大量空间用于大范围（可能的值mult呈指数增长

（这是一个很好的数学方法，因为我们实际上看的是一组素数p_i，素数数组只是抽象素数集的实现）。

小值的位操作替代方法是使用intorlong作为位集。

使用这种方法，要检查候选人i不在，set您只需要检查：

if (pow(2,i) & set == 0) // not in the set
else //already in the set

向集合中输入一个元素i：

set = set | pow(2,i)

更好的方法是list用所有数字填充 a，用Fisher-yates shuffle对其进行洗牌，然后对其进行迭代以生成新的随机数。

于 2012-12-10T13:37:26.713 回答
0

如果我必须避免上述这些方法并使用一些数学/逻辑/按位运算来查找之前是否已绘制随机数，有没有办法？

受制于您人为的约束，是的，您可以使用按位运算来模仿一个小的位集：

您可以根据需要的大小在右侧选择不同的整数类型。

bitset code                    bitwise code

std::bitset<32> x;             unsigned long x = 0;
if (x[i]) { ... }              if (x & (1UL << i)) { ... }
// assuming v is 0 or 1
x[i] = v;                      x = (x & ~(1UL << i)) | ((unsigned long)v << i);
x[i] = true;                   x |= (1UL << i);
x[i] = false;                  x &= ~(1UL << i);

对于更大的集合（超出 的位大小unsigned long long），您将需要一个您选择的整数类型的数组。将索引除以每个值的宽度以了解要在数组中查找的索引，并使用模数进行位移。这基本上就是bitset这样做的。

我假设告诉你如何最好地洗牌 10 个数字的各种答案完全没有抓住重点：你人为的约束在那里是因为你实际上不想或不需要知道如何最好地洗牌 10 个数字:-)

于 2012-12-10T14:11:43.393 回答
0

保留一个变量来映射绘制的数字。如果之前绘制了该数字，则该变量的第 i 位将为 1：

int mapNumbers = 0;

int generateRand() {        
    if (mapNumbers & ((1 << 11) - 1) == ((1 << 11) - 1)) return; // return if all numbers have been generated
    int x;  
    do {
        x = newVal();
    } while (!x & mapNumbers);
    mapNumbers |= (1 << x);
    return x;
}
于 2012-12-10T14:18:25.127 回答