math - 各桁をチェックせずに、num1 の桁が num2 の桁であるかどうかをチェックする方法はありますか?

Question

私が宝くじの数字を推測したとしましょう：

1689年

宝くじのしくみは、数字が実際の当選番号の数字と 1:1 で一致する限り、数字の順序は関係ありません。

したがって、番号 1689 は次の場合の当選番号になります。

1896年、1698年、9816年など.

あなたの推測の各数字がターゲット番号に存在する限り、宝くじに当選します。

これを行うことができる数学的な方法はありますか？

この問題は、O(N^2) ループで各桁を宝くじの当選番号の各桁と照合してチェックすることで解決しました (モジュラスで区切ります)。それは問題ありませんが、うまくいきますが、私にできるきちんとした数学のトリックがあるかどうか知りたいです.

たとえば、最初は... 両方の数字の各桁の和と積を取り、それらが一致すれば勝てると思っていました。

↑それでいいと思いますか？

~~しかし、宝くじの推測を見つけたとき、すぐにこれを反証しました。222 と 124 は数字は異なりますが、積と和は同じです。~~

順序に関係なく num1 の数字が num2 の数字と一致するかどうかをすばやく判断するために使用できる数学のトリックを知っている人はいますか?

score 16 · Accepted Answer

各数値を調べて、各桁の出現回数を (2 つの異なる 10 要素配列に) カウントアップしてみてはどうでしょうか? 合計したら、各桁の数を比較します。各桁を 1 回しか見ないので、それは O(N) です。

コードは次のようになります。

for(int i=0; i<digit_count; i++)
{
   guessCounts[guessDigits[i] - '0']++;
   actualCounts[actualDigits[i] - '0']++;
}

bool winner = true;
for(int i=0; i<10 && winner; i++)
{
   winner &= guessCounts[i] == actualCounts[i];
}

上記のコードは、guessDigits と actualDigits が両方とも char 文字列であると仮定しています。彼らが実際の数字を保持している場合は、- '0'ビジネスをスキップできます。

これがより少ないスペースを占有するか、より早く終了するようにする最適化がおそらくありますが、これは O(N) アプローチの非常に簡単な例です。

ちなみに、コメントで述べたように、ゼロのために乗算/合計の比較は確実に機能しません。0123 と 0222 を考えてみましょう。どちらの場合も積は 0、合計は 6 です。

score 14 · Accepted Answer

配列に分割し、配列を並べ替え、文字列に結合し、文字列を比較します。

（数学のトリックではありません、私は知っています）

score 3 · Accepted Answer

数字を配列に配置し、配列をソートしてから、要素ごとに配列を比較できます。これにより、O( N^2 ) よりも優れた O( NlogN ) の複雑さが得られます。

score 2 · Accepted Answer

N が大きくなる可能性がある場合は、数字の並べ替えが答えです。

数字は 0..9 であるため、配列 [0..9] 内の宝くじの各数字の出現回数をカウントできます。

比較するには、推測で出くわした数字ごとに 1 を引くことができます。カウントがすでに 0 である数字に遭遇すると、推測が異なることがわかります。すべての桁を通過すると、推測は同じになります (推測の桁数が宝くじの答えと同じである限り)。

score 2 · Accepted Answer

各桁 d に対して (d+1) 番目の素数を掛けます。

これはより数学的ですが、並べ替えやバケットの方法よりも効率的ではありません。実はバケツ方式に変装しています。

score 0 · Accepted Answer

私はユーリから答えを盗んでいます、そしてスターブルー（彼らを賛成する）

バケット化はO（1）を除いて最速です

lottonumbers == mynumbers;

並べ替えはO（nlog2n）です

BucketsortはO（n）アルゴリズムです。

したがって、あなたがする必要があるのは、それを2回（あなたの数に対して1回、ターゲットセットに対して1回）行うことです。そして、桁の数が合算される場合、それらは一致します。あらゆる種類の並べ替えは、この場合は不要な追加のオーバーヘッドです。

array[10] digits;
while(targetnum > 0)
{
    short currDig = targetnum % 10;
    digits[currDig]++;
    targetnum = targetnum / 10;
}
while(mynum > 0)
{
    short myDig = mynum % 10;
    digits[myDig]--;
    mynum = mynum / 10;
}
for(int i = 0; i < 10; i++)
{
   if(digits[i] == 0)
      continue;
   else
     //FAIL TO MATCH
}

最も美しいコードではありません、私は認めます。

score 0 · Accepted Answer

0

両方の数字の桁を並べ替えて比較します。

于 2009-02-19T21:09:50.547 に答える

score 0 · Accepted Answer

数字を格納する前に数字を並べ替えます。その後、あなたの数は等しくなります。

score 0 · Accepted Answer

4桁しか扱っていない場合は、使用するアルゴリズムについてあまり考える必要はないと思います. それらはすべてほぼ同じように機能します。

また、222 と 124 の合計は同じではありません

score 0 · Accepted Answer

n が小さい場合、効率の順序は無関係であり、定数がより重要になり始めることを考慮する必要があります。あなたの数字は実際にどれくらい大きくなることができますか？10桁までいけますか？20? 100? 数値が数桁しかない場合、n^2 はそれほど悪くありません。数千桁の文字列がある場合は、実際には、並べ替えやバケット化など、より巧妙な処理が必要になる場合があります。(つまり、0 を数える、1 を数えるなど)

score 0 · Accepted Answer

ただの楽しみとして、並べ替えやその他の方法ではなく、通常とは異なる考えで、削除を行います。結果文字列が空の場合、勝者がいます!

    Dim ticket As String = "1324"
    Dim WinningNumber As String = "4321"

    For Each s As String In WinningNumber.ToCharArray
        ticket = Replace(ticket, s, "", 1, 1)
    Next

    If ticket = "" Then MsgBox("WINNER!")
    If ticket.Length=1 then msgbox "Close but no cigar!"

これは繰り返し数字でも機能します..

score 0 · Accepted Answer

[0 .. 9] の添字が付いた 10 個の整数の配列を作成します。

各要素を異なる素数に初期化する

積を 1 に設定します。

数値の各桁を使用して、配列に添字を付け、素数を取り出し、その積を掛けます。

これにより、桁の順序に依存しない一意の表現が得られます。

もう一方の番号についても同じ手順を実行します。

一意の表現が一致する場合、元の数値は一致します。

score 0 · Accepted Answer

数字の繰り返しが許可されていない場合 (これが当てはまるかどうかはわかりません)、10 ビットの 2 進数を使用します。最上位ビットは数字の 9 を表し、LSB は数字の 0 を表します。各数字を順番に調べて、見つけた数字ごとに適切なビットを反転させます。

したがって、1689 は 1101000010 になります。

9816 は次のようにもなります: 1101000010

あなたが勝者である場合、XORまたは減算は0のままになります

これはバケット化の単純な形式です

score -1 · Accepted Answer

かわいい解決策の 1 つは、Zobist ハッシュの変形を使用することです。(はい、私はそれが過剰であり、確率論的であることを知っていますが、ねえ、それは「賢い」です。)

10 要素の配列a[0..9]をランダムな整数に初期化します。次に、各数値d[]について、の合計を計算しa[d[i]]ます。数値に同じ数字が含まれている場合、結果の数値は等しくなります。確率が高い場合 (考えられる int の数で ~ 1)、その逆も当てはまります。

(最大で合計 10 桁になることがわかっている場合は、乱数の代わりに 1、10、100 などの固定数を使用して、成功を保証することができます。これは、あまり偽装されていないバケットの並べ替えです。 )

math - 各桁をチェックせずに、num1 の桁が num2 の桁であるかどうかをチェックする方法はありますか?

14 に答える 14

Related

Reference