3

～の間のRandom(x, y)乱数を返す関数が与えられます。からまでの unique_random_numbers のリストを出力するアルゴリズムを設計します。リストには番号が含まれている必要があり、すべての番号は 1 回だけ表示される必要があります。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

1

ほとんどの場合、1 から n/2 までの数値が返されるリストの前半に含まれます (ピボットがおよそ n/2 を返すことを想像してください)。(それが正しくないことを証明するのも簡単ではありません^^)

もう少し考える必要がありますが、お尋ねいただければヒントを差し上げます

于 2013-09-18T12:32:19.267 に答える