3

给定一个函数，它返回一个介于和（包括）Random(x, y)之间的随机数。设计一个算法来打印从到的 unique_random_numbers 列表。列表中必须有数字，并且每个数字只能出现一次。xy1nn

例如

PrintRandomList(1, 5) can print -> 2, 5, 1, 4, 3    
PrintRandomList(1, 6) can print -> 4, 1, 6, 3, 2, 5

我已经能够提出一种算法，但无法证明它会生成一个真正的随机列表（假设Random(x, y)会生成真正的随机数）。

void PrintRandomList(int a, int b) {
    if(a<=b) {
        int pivot = Random(a, b);
        printf("%d ", pivot);
        PrintRandomList(a, pivot-1);
        PrintRandomList(pivot+1, b);    
    }
}

我的问题：算法正确吗？如果是的话，我们能证明算法的正确性吗？

如果这个算法是正确的，那么我们也可以用它来洗牌一个数组，而不是使用 Knuth 洗牌算法。

4

2 回答 2

3

证明这个算法是否有效的根本问题的诀窍是你必须证明每个结果都是同样可能的。正如其他人指出的那样，情况并非如此。

如果您可以找到任何无法到达甚至不太可能到达的序列，那么您就知道该算法不“公平”。这个论点的反面证明它是。

于 2013-09-18T12:35:12.347 回答
1

您的算法不正确，大多数时候从 1 到 n/2 的数字将位于返回列表的前半部分（想象枢轴返回大约 n/2）。（也不容易证明不正确^^）

你需要多想一点，但如果你问我们可以提供提示

于 2013-09-18T12:32:19.267 回答