您的第一个错误是有 50 个结果，实际上有 100 个（编辑：请参阅下面的评论以进行澄清）。这是因为得到 (1,2) 和 (2,1) 是两个单独结果的结果，但在每种情况下，较大的数字恰好是较小数字的两倍。

所以得到这个的全部可能的方法实际上是由集合给出的：

{ (1,2), (2,1), (2,4), (4,2), ..., (50,100), (100,50) }

这是 100 个可能结果的列表。

可能结果的总数是$100 \times 99$

因为第一次选择有 100 个可能的数字，第二次选择 99，因为它们必须是不同的。

因此答案如下：

$P = \frac{100}{100 \times 99} = \frac{1}{99}$

使用相同的论点，很容易证明从选择数字的更一般情况的概率由下式给出：$1, 2, ..., n$$n$

$P = \frac{1}{n-1}$

测试名称中的“黑客”表明我们试图找到一个面向计算的解决方案。

因此，让我们从一个蛮力枚举（a）一个整数是另一个整数两倍的“有利”情况和（b）所有可能情况的程序开始。答案就是他们的比例。我编写了一个通用解决方案。它的输入是一个正整数n，它的输出是概率。

n=100
all=favorable=0
for i=1 to n
    for j=1 to n
        if (i != j) all=all+1                  {1}
        if (j == 2*i) favorable = favorable+1  {2}
        if (i == 2*j) favorable = favorable+1  {3}
return(favorable / all)

（正确性的证明依赖于对于任何正数。）$i \ne 2i$$i$

该程序需要次测试和最多次内循环迭代的增量。因此，每次执行内循环时到到次。那是性能：对于像来说还可以，但是一旦超过左右就会很糟糕。$3$$3$$3n$$6n$$3n^2$$6n^2$$O(n^2)$$n$$n=100$$n$$10000$

作为一名黑客，您要做的第一件事就是通过简化内部循环（如果可能）来消除二次性能。为此，系统地遍历内部循环中的行（如编号）并注意以下几点：

1. 第 1 行对 的每个值只执行一次，i因此all递增次。因此，对于 的计算，可以通过递增 来代替循环。$n-1$alljalln-1

2. 时只执行一次，否则根本不执行。因此，每当时，它可以通过增加1替换。$2i \le n$all$1$$2i \le n$

3. 一旦提供i偶数，第 3 行就会执行。

这是转换后的程序。

n=100
all=favorable=0
for i=1 to n
    all = all + (n-1)                      {1'}
    if (2*i <= n) favorable = favorable+1  {2'}
    if (even(i)) favorable = favorable+1   {3'}
return(favorable / all)

我们可以更进一步并消除它的循环吗？

1. 第 1' 行被执行次。因此增加.$n$alln*(n-1)

2. 第 2' 行仅在时执行。一种计算方法是（小于或等于的最大整数）。$2i \le n$$\lfloor n/2\rfloor$$n/2$

3. 的偶数值执行。同样，这发生了次。$i$$\lfloor n/2 \rfloor$

程序的第二个变换是：

n=100
all=favorable=0                     {0}
all = all + n * (n-1)               {1''}
favorable = favorable + floor(n/2)  {2''}
favorable = favorable + floor(n/2)  {3''}
return(favorable / all)

这已经是一项了不起的成就： O算法已简化为算法（可以将其视为答案的“封闭公式”）。$O(n^2)$$O(1)$

最后，我们可以通过将初始化（第 0 行）滚动到每个变量的第一次使用并结合第 2 行和第 3 行来进行一些简单的代数转换：

n=100
all = n * (n-1) 
favorable = 2 * floor(n/2) 
return(favorable / all)

此时人类可以执行程序。 让我们用来做：$n=100$

all = 100 * (100-1) = 100*99
favorable = 2 * floor(100/2) = 2*50 = 100
favorable/all = 100 / (100*99) = 1/99

因此输出为。$1/99$

总而言之，可以使用简单的程序重写规则将蛮力算法系统地转换为时尚、优雅的程序。$O(1)$

首先，您是在没有更换的情况下进行采样。因此，有 100*99 种不同的结果，例如 (1,1) 不是有效结果。

其次，顺序无关紧要。较大的必须正好是两倍，而不是第二个。因此，删除对称对。

因此，(100)*99/2 中有 50 个是正数，即 1/99