0

私は単純なゲームに取り組んでおり、「helloworld」などの単語やフレーズを取得して一連の数字に変換する必要があります。

基準は次のとおりです。

  1. 数字は区別する必要があります
  2. 数列の最大数を構成する機能が必要です。IE10の合計数。
  3. 各番号の最大範囲を順番に構成する機能が必要です。
  4. 決定論的である必要があります。つまり、同じ入力フレーズに対して毎回同じシーケンスを取得する必要があります。

私は次のように問題を分解しようとしました：

  1. 文字をASCII数値コードに変換します： "hello world" =104 101 108 108 111 32 119 111 114 108 100
  2. 総数（この場合は10）を満たすまで、1つおきの数を削除します。
  3. 数値>最大数値の場合は数値を計算し、数値<=最大数値になるまで2で除算します
  4. 番号が重複している場合は、満足するまで最初の出現を増減します。（これは、別の複製を解決することによって複製を作成できるため、問題を引き起こす可能性があります）

これを行うためのより良い方法はありますか、それとも私は正しい方向に進んでいますか？上で述べたように、私は区別を取り除くことで問題にぶつかるかもしれないと思います。

4

4 に答える 4

1

出力系列のサイズを制限したい場合、これは不可能です。

証明：
出力が一連のサイズkであり、それぞれの範囲r <= Mが事前定義されていると仮定するとM、最大でk*M可能な出力があります。

ただし、入力の数は無限であり、具体的にはk*M+1さまざまな入力があります。

鳩の巣原理（入力が鳩であり、出力が鳩穴である）から-1つの鳩穴（出力）に2つの鳩（入力）がある-したがって、要件を達成することはできません。

元の回答は、出力系列のサイズを制限せずに回避策を提供します。

あなたは素数を使うことができます、素数のp1,p2,...シリーズとしましょう。 次に、を使用して文字列を一連の数値に変換します 。各文字の範囲は明らかに次のようになります。
number[i] = ascii(char[i]) * p_i
[0,255 * p_i]

それぞれi,jについてi != j-> p_i * x != p_j * y（それぞれについてx,y）-あなたは独自性を得るからです。ただし、生成された数値は急速に増加する可能性があるため、これは理論的には主に優れています。実際の実装では、JavaのBigIntegerなどの大きな数値ライブラリが必要になります（C＃に相当するものを思い出せません）。

別の可能な解決策（シリーズ制限なしの同じ緩和を使用）は次のとおりです。

number[i] = ascii(char[i]) + 256*(i-1)

ここでは、の範囲number[i]は[256*(i-1),256*i)であり、要素はまだ異なります。

于 2013-02-21T17:14:35.767 に答える
1

数学的には、理論的にはやりたいことを実行できますが、C＃では実行できません。

出力を区別する必要がある場合は、ASCII値を使用して文字列をエンコードした後、情報を失うことはありません。これは、出力サイズをn個の数値に制限する場合、数値にはエンコーディングからのすべての情報を含める必要があることを意味します。

だからあなたの例のために

「HelloWorld」->10410110810811132119111114108100

これらの各番号の意味を保持する必要があります。これを行う最も簡単な方法は、数字を3桁に0で埋め、それらを1つの大きな数字に連結することです...最大数= 1の場合、結果は104101108111032119111114108100になります（任意の長さの入力に対して、問題がどこにあるかを確認できます。非常に大きな数が必要です。）したがって、任意の長さの文字列入力をn個の数にエンコードすることは確かに可能ですが、数は非常に大きくなります。

「数字」が数字を意味する場合、@ amitがpidgeonholeの原則を使用して彼の例で説明したように、明確な出力を持つことはできません。

于 2013-02-21T17:36:42.447 に答える
0

できるだけ簡単に基準を削除しましょう。明確で決定論的な場合は、ハッシュコードを使用してください。（ハッシュは実際には区別されることが保証されていませんが、区別される可能性が非常に高いです）：

string s = "hello world";
uint hash = Convert.ToUInt32(s.GetHashCode());

GetHashCode'-'が表示される可能性を回避するために、returnedのsignedintをunsignedに変換したことに注意してください。

次に、数値ごとの最大範囲については、ベースを変換するだけです。

これにより、最大のシーケンス基準が残ります。要件をよりよく理解せずに、私が提案できるのは、必要に応じて切り捨てることだけです。

hash.toString().Substring(0, size)

切り捨てを行うと、区別がつかなくなる可能性がありますが、要件に応じて組み込む必要がありますか？amitが別の回答で説明しているように、無限の入力と非無限の出力を持つことはできません。

于 2013-02-21T17:30:48.037 に答える
0

さて、あるコメントで、これは宝くじの番号を選ぶためだけだとあなたは言いました。その場合、次のようなことができます。

public static List<int> GenNumbers(String input, int count, int maxNum)
{
    List<int> ret = new List<int>();
    Random r = new Random(input.GetHashCode());
    for (int i = 0; i < count; ++i)
    {
        int next = r.Next(maxNum - i);
        foreach (int picked in ret.OrderBy(x => x))
        {
            if (picked <= next)
                ++next;
            else
                break;
        }
        ret.Add(next);
    }
    return ret;
}

アイデアは、文字列のハッシュコードを使用して乱数ジェネレーターをシードすることです。残りの部分は、置き換えなしで番号を選択するだけです。より効率的に書くことができると確信しています-別の方法は、すべての数字を生成しmaxNum、最初の数字をシャッフルすることcountです。警告、テストされていません。

新しいバージョンの.Netランタイムはランダムな文字列ハッシュコードアルゴリズムを使用していることを知っています（したがって、結果は実行ごとに異なります）が、これはオプトインであると思います。独自のハッシュアルゴリズムを作成することはオプションです。

于 2013-02-22T20:50:39.863 に答える