0

假设我猜到了一个彩票号码：

1689

彩票的运作方式是，只要数字与实际中奖彩票号码中的数字 1:1 匹配，数字的顺序就无关紧要。

因此，数字 1689 将是一个中奖彩票号码：

1896、1698、9816等。

只要您猜中的每个数字都出现在目标号码中，那么您就中了彩票。

有没有数学方法可以做到这一点？

我已经通过 O(N^2) 循环检查每个数字与中奖彩票号码的每个数字（用模数分隔）解决了这个问题。这很好，它有效，但我想知道我是否可以做任何巧妙的数学技巧。

例如，起初......我认为我可能会很棘手，只取两个数字中每个数字的总和和乘积，如果它们匹配，那么你就赢了。

^ 你觉得这样行吗？

然而，当我发现彩票猜测：222 和 124 的数字不同但乘积和总和相同时，我很快就反驳了这一点。

任何人都知道我可以用来快速确定 num1 中的数字是否与 num2 中的数字匹配的任何数学技巧，而不管顺序如何？

4

14 回答 14

16

如何遍历每个数字，并计算每个数字出现的次数（进入两个不同的 10 元素数组）？完成总计后，比较每个数字的计数。由于您只查看每个数字一次，因此 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。

于 2009-02-19T21:15:04.623 回答
14

拆分为数组，排序数组，加入字符串，比较字符串。

（不是数学把戏，我知道）

于 2009-02-19T21:08:58.553 回答
3

您可以将数字放入数组中，对数组进行排序，然后逐个元素地比较数组。这将为您提供 O( NlogN ) 复杂度，优于 O( N^2 )。

于 2009-02-19T21:10:49.517 回答
2

如果 N 可以变大，那么对数字进行排序就是答案。

因为数字是 0..9，所以您可以在数组 [0..9] 中计算彩票答案的每个数字出现的次数。

要进行比较，您可以为猜测中遇到的每个数字减去 1。当你遇到一个计数已经为 0 的数字时，你知道猜测是不同的。当您通过所有数字时，猜测是相同的（只要猜测的数字与彩票答案一样多）。

于 2009-02-19T21:21:16.093 回答
2

对于每个数字 d 乘以第 (d+1) 个素数。

这比排序或桶方法更数学但效率更低。其实是变相的bucket方法。

于 2009-02-19T21:22:48.947 回答
0

我会对两个数字的数字进行排序并进行比较。

于 2009-02-19T21:09:50.547 回答
0

在存储数字之前对数字进行排序。之后，您的人数将相等。

于 2009-02-19T21:09:57.380 回答
0

如果您只处理 4 位数字，我认为您不必考虑使用哪种算法。它们的性能大致相同。

222 和 124 的总和也不相同

于 2009-02-19T21:12:04.117 回答
0

您必须考虑，当 n 较小时，效率的顺序无关紧要，常数开始变得更重要。你的数字实际上能有多大？你能达到10位数吗？20？100？如果您的数字只有几位数字，那么 n^2 确实还不错。如果您有数千位数字的字符串，那么您实际上可能需要做一些更聪明的事情，比如排序或分桶。（即数 0、数 1 等）

于 2009-02-19T21:13:54.440 回答
0

我从 Yuliy 和 starblue 那里偷了答案（支持他们）

除了 O(1) 之外，分桶是最快的

lottonumbers == mynumbers;

排序是 O(nlog2n)

Bucketsort 是一种 O(n) 算法。

因此，您需要做的就是做两次（一次用于您的数字，一次用于目标集），如果数字的数字相加，则它们匹配。在这种情况下，任何类型的排序都是不必要的额外开销。

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
}

我承认，这不是最漂亮的代码。

于 2009-02-19T21:32:59.660 回答
0

创建一个下标为 [0 .. 9] 的 10 个整数的数组。

将每个元素初始化为不同的素数

将产品设置为 1。

使用数字中的每个数字，在数组中下标，取出质数，然后将乘积乘以它。

这为您提供了与数字顺序无关的独特表示。

对其他号码执行相同的程序。

如果唯一表示匹配，则原始数字匹配。

于 2009-02-19T23:07:44.393 回答
0

如果不允许重复数字（但不确定是否是这种情况），则使用 10 位二进制数。最高有效位代表数字 9，LSB 代表数字 0。依次处理每个数字，并为找到的每个数字翻转适当的位

所以 1689 将是： 1101000010

和 9816 也将是： 1101000010

如果你是赢家，那么 XOR 或减法将留下 0

这只是一种简单的分桶形式

于 2009-02-20T02:36:37.557 回答
0

只是为了好玩，并在正常情况下思考，而不是排序和其他方式，做删除的事情。如果结果字符串为空，则您有赢家！

    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!"

这也适用于重复数字..

于 2009-02-20T04:23:06.507 回答
-1

一个可爱的解决方案是使用Zobrist hashing的变体。（是的，我知道这是矫枉过正的，以及概率，但嘿，它是“聪明的”。）

将一个十元素数组初始化a[0..9]为随机整数。然后，对于每个数字d[]，计算 的总和a[d[i]]。如果数字包含相同的数字，则结果数字将相等；以高概率（有多少个可能的整数约为 1），反之亦然。

（如果您知道总共最多有 10 位数字，那么您可以使用固定数字 1、10、100，...而不是随机数来保证成功。这是不太伪装的桶排序。 )

于 2009-02-21T09:13:40.187 回答