найти рациональное число со свойством

Question

Я должен написать программу, чтобы найти рациональное число, которое имеет свойство.Я написал код для проверки свойства, но теперь я не знаю, как проверить все рациональные числа.Я пробовал с

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;
}

, но это работает только иногда.Как я могу решить это?

Answer 1

Рациональные числа являются счетными , что означает, что они могут быть приведены в однозначном соответствии с целыми числами.Если вы сделаете это, то у вас будет решение.

Вместо того, чтобы переписываться один на один, более простой способ пройти через рациональные решения заключается в следующем.

Построить(счетно) бесконечно по (счетно) бесконечной матрице Q, так что Q_(i,j) = i/j, где i и j, варьируются от 1 до 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 на шаге (r+s)(r+s-1)/2 + s, поэтому любое заданное рациональное число будет встречаться за конечное время.

Один из способов закодировать это - разрешить i индекс строки (внешний цикл for) и j индекс индекса столбца (внутренний цикл for).Тогда i будет варьироваться от 1 до infinity, но j будет варьироваться только от 1 до i.

Если ваша goodRat функция занимает достаточно много времени,затем вы можете ускорить это, сначала проверив, что i и j взаимно просты, а если нет, то пропустите их.

Answer 2

Дерево Штерна-Броко - это один из способов систематически генерировать все рациональные числа без повторений. Смотрите других на https://math.stackexchange.com/questions/7643/produce-an-explicit-bijection-between-rationals-and-naturals.

Answer 3

Во-первых, о вашей первой попытке:

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