0

我正在开发一个简单的游戏，我需要使用诸如“hello world”之类的单词或短语并将其转换为一系列数字。

标准是：

  1. 数字需要不同
  2. 需要配置最大数字序列的能力。IE 总共 10 个数字。
  3. 需要能够按顺序为每个数字配置最大范围。
  4. 必须是确定性的，即对于相同的输入短语，我们每次都应该得到相同的序列。

我试过像这样分解问题：

  1. 将字符转换为 ASCII 数字代码：“hello world”=104 101 108 108 111 32 119 111 114 108 100
  2. 删除所有其他数字，直到我们满足总数（在这种情况下为 10）
  3. Foreach 数字如果数字 > 最大数字然后除以 2 直到数字 <= 最大数字
  4. 如果有任何数字重复，则增加或减少第一次出现的次数，直到满意为止。（这可能会导致问题，因为您可以通过解决另一个副本来创建副本）

有没有更好的方法来做到这一点，还是我走在正确的轨道上？如上所述，我认为我可能会遇到消除区别的问题。

4

4 回答 4

1

如果你想限制输出系列的大小——那么这是不可能的。

证明：
假设你的输出是一系列 size k，每个 range都是r <= M一些预定义M的，那么最多k*M有可能的输出。

但是，输入的数量是无限的，具体来说，输入是k*M+1不同的。

根据鸽笼原理（输入为鸽子，输出为鸽笼）-一个鸽笼（输出）中有2只鸽子（输入）-因此无法满足要求。

原始答案，在不限制输出系列大小的情况下提供解决方法：

您可以使用素数，让我们p1,p2,...成为素数系列。
然后，将字符串转换为一系列数字，使用number[i] = ascii(char[i]) * p_i
每个字符的范围显然是那么[0,255 * p_i]

因为对于 eachi,j这样i != j-> p_i * x != p_j * y(对于 each 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 个数字，那么这些数字必须包含编码中的所有信息。

所以对于你的例子

“你好世界”-> 104 101 108 108 111 32 119 111 114 108 100

您必须保留每个数字的含义。最简单的方法是将您的数字填充为三位数字并将它们连接在一起成为一个大数字...使您的结果为 104101108111032119111114108100 最大数字 = 1。（您可以看到问题出在哪里，对于任意长度的输入，您需要非常大的数字。）所以当然可以将任意长度的字符串输入编码为n 个数字，但是数字会变得非常大。

如果“数字”是指数字，那么不，您不能有不同的输出，正如@amit 在他的示例中使用 pidgeonhole 原理解释的那样。

于 2013-02-21T17:36:42.447 回答
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 回答
0

让我们尽可能轻松地消除您的标准。对于不同的、确定的，只需使用哈希码。（哈希实际上并不能保证是不同的，但很有可能是）：

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

请注意，我将返回的带符号整数转换GetHashCode为无符号整数，以避免出现“-”的机会。

然后，对于每个数字的最大范围，只需转换 base。

这为您留下了最大的序列标准。如果没有更好地了解您的要求，我只能建议在必要时截断：

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

截断会留​​下您不再与众不同的机会，但必须将其内置为您的要求可以接受？正如阿米特在另一个答案中解释的那样，您不能有无限的输入和非无限的输出。

于 2013-02-21T17:30:48.037 回答