3

配列を介して100個のランダム要素を作成する次のプログラムがあります。これらの 100 個のランダム値は一意であり、すべての値は 1 回だけ表示されます。

ただし、線形検索では配列全体を検索し続けます。どうすればジャグ配列をこれに入れることができるので、残りの場所だけを「スキャン」しますか? (テーブルを 100 個の最大要素で保持すると仮定すると、1 つのランダムな値が生成された場合、配列は線形検索スキャンで 99 個の要素を保持します...)

FoundLinearInArray のどこかにギザギザの配列を実装する必要があると思いますか?

うまくいけば、これは何らかの意味を成しました。よろしく。

 private int ValidNumber(int[] T, int X, int Range)
    {
        Random RndInt = new Random();
        do
        {
            X = RndInt.Next(1, Range + 1);
        } while (FoundLinearInArray(T, X));

        return X; 

    }/*ValidNumber*/

    private bool FoundLinearInArray(int[] A, int X)
    {
        byte I = 0;
        while ((I < A.Length) && (A[I] != X))
        {
            I++;
        }
        return (I < A.Length);
    }/*FoundInArray*/


    public void FillArray(int[] T, int Range)
    {
        for (byte I = 0; I < T.Length; I++)
        {
            T[I] = ValidNumber(T, I, Range);
        }

    }/*FillArray*/
4

3 に答える 3

1

配列を埋めたいように見えますが、その中の各項目が一意であることを保証したいですか? その場合は、生成した各数値をハッシュセットに入れます。ハッシュセットのルックアップは O(1) (またはおそらく対数) です。100 万個のアイテムを入れることができ、それでも非常に高性能なルックアップを行うことができます。

于 2010-03-11T16:05:10.107 に答える
0

これがあなたが探していたものかどうかはわかりませんが、範囲内の一意の乱数のセットで配列を埋めるコードのスニペットを次に示します。JMarsch が示唆したように、HashSet を使用して、使用されている数値を追跡します。

また、問題が解決可能であることを確認するための簡単なチェックも行います。Range が配列のサイズよりも小さい場合は、配列を埋めるのに十分な一意の数値がありません。

最後に、乱数ジェネレーターを複数回ではなく 1 回作成するため、数値の分布が改善されます。数字は一意でなければならないので、この場合は気付かないかもしれませんが、練習するのは良い習慣だと思います。

    private int GenerateUniqueRandomNumber(Random chaos, HashSet<int> used, int range)
    {
        while (true)
        {
            int candidate = chaos.Next(range);
            if (!used.Contains(candidate))
            {
                used.Add(candidate);
                return candidate;
            }
        }
    }



    public void FillArray(int[] array, int range)
    {
        if (range < array.Length)
        {
            throw new ArgumentException("Range is too small");
        }

        Random chaos = new Random();
        HashSet<int> used = new HashSet<int>();

        for (int i = 0; i < array.Length; i++)
        {
            array[i] = GenerateUniqueRandomNumber(chaos, used, range);
        }
    }

これが役立つことを願っています。

于 2010-03-27T04:35:31.897 に答える
0 
static int[] FillArray(int low, int high, int count)
    {
        Random rand = new Random();
        HashSet<int> Data = new HashSet<int>();
        while (Data.Count() < count)
            Data.Add(rand.Next(low, high));
        return Data.ToArray();
    }

これは、JMarsch が提案していたことと似ています。ハッシュセットは行く方法です。

于 2010-03-27T04:47:48.550 に答える