Geek asks and answers

Finding a rational number with a property

I need to write a program to find a rational number that has a property. I wrote code to check the property, but now I do not know how to check all rational numbers. I tried using

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

but it never ends! And he misses too much. So i tried this

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

but it only works sometimes. How can i solve this?

+3
source share
3 answers

Rational numbers are countable, which means that they can be placed in a one-to-one correspondence with integers. If you do, you will have your decision.

Instead of giving a one-to-one correspondence, an easier way to go through rational actions is as follows.

() 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 , .

+10

-, :

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

0

More articles:


All Articles