3

我必须编写一个程序来找到具有属性的有理数。我编写了代码来检查属性，但现在我不知道如何检查所有有理数。我试过了

float rat;
for (int i=1 ; i ; ++i) {
  for (int j=1 ; j ; ++j) {
    rat = (float)i/(float)j;
    if goodRat(rat) then return rat;
  }
}

但它永远不会结束！它错过了太多。所以我尝试了这个

float rat;
while {
  int i = random(1000) + 1;
  int j = random(1000) + 1;
  rat = (float)i/(float)j;
  if goodRat(rat) 
      return rat;
}

但这仅在某些时候有效。我该如何解决这个问题？

4

3 回答 3

10

有理数是可数的，这意味着它们可以与整数一一对应。如果你这样做，那么你就会有你的解决方案。

下面是一种更简单的遍历有理数的方法，而不是一一对应。

通过（可数）无限矩阵构造一个（可数）无限矩阵Q，使得Q_(i,j) = i/jwherei和jrange from1到infinity。矩阵如下所示：

 1  1/2 1/3 1/4 1/5 . . .
2/1 2/2 2/3 2/4 2/5 . . .
3/1 3/2 3/3 3/4 3/5 . . . 
4/1 4/2 4/3 4/4 4/5 . . .
5/1 5/2 5/3 5/4 5/5 . . .
 .   .   .   .   .
 .   .   .   .   .
 .   .   .   .   .

当然，有很多重复（整个对角线都是 1！），但我会为了简单而不是速度。

您要做的是沿着无限的列走，因此您会错过很多数字。相反，你应该沿着有限的对角线走。即按以下顺序取元素

 1  3  6 10 15  . 
 2  5  9 14  .  .
 4  8 13  .  .  .
 7 12  .  .  .
11  .  .  .
 .  .  .
 .  .
 .

所以你会得到1, 2/1, 1/2, 3/1, 2/2, 1/3, 4/1, 3/2, 2/3, 1/4, .... 此外，您知道您将r/s在 step遇到(r+s)(r+s-1)/2 + s，因此任何给定的有理数都将在有限时间内遇到。

对此进行编码的一种方法是让i为行索引（外for循环）并让j为列索引（内for循环）。然后i将范围从1到infinity，但j范围仅从1到i。

如果你的goodRat函数需要相当长的时间，那么你可以通过首先测试它i并且j是互质的，如果不是跳过它们来加快速度。

于 2011-06-16T01:55:51.773 回答
4

Stern-Brocot 树是系统地生成所有有理数而不重复的一种方法。在https://math.stackexchange.com/questions/7643/produce-an-explicit-bijection-between-rationals-and-naturals上查看其他人。

于 2011-06-16T01:55:04.117 回答
0

首先，关于您的第一次尝试：

float rat;
for (int i=1 ; i ; ++i) {
    // the loop for the first won't be reached
  for (int j=1 ; j ; ++j) {
  // this loop will never end, it will either loop for ever or return something like (floag)1/(float)j
    rat = (float)i/(float)j;
    if goodRat(rat) then return rat;
  }
}

我的建议是，明确你的目的，也许你可以参考http://en.wikipedia.org/wiki/Stern-Brocot_tree

于 2011-06-16T02:03:42.060 回答