If all the irreducible fractions between 0 and 1, with denominators at most 99, are listed in ascending order, which two fractions would be before and after 11/21? Determine which two fractions are adjacent to 34/87 in this listing.

Found elements before and after 11/21
                45/86   43/82
Found elements before and after 34/87
                25/64   27/69

note 27/69 is 9/23 - but didnt think i needed to fuss with that since i can reduce little numbers like this pretty easily

 

the program:

#include <stdio.h>
#include <float.h>

#define SIZE 10000

typedef struct {int num; int denom; float val;} fracS;

int compare(const void *a, const void *b) {
  fracS *af = (fracS *)a;
  fracS *bf = (fracS *)b;
  return af->val > bf->val ? 1 : -1 ;
}

fracS frac[SIZE];

void findEnds(int num, int denom) {
  int k,r,s;

  //find input in our array
  for (k = 0; k < SIZE; k++)
    if (frac[k].num == num && frac[k].denom == denom)
      break;

  //get elem before
  for (r = k-1; r != -1; r--)
    if(frac[r].val != frac[k].val)
      break;

  //get elem after
  for (s = k+1; s != SIZE; s++)
    if(frac[s].val != frac[k].val)
      break;

  printf("Found elements before and after %d/%d\n \t\t%d/%d\t%d/%d\n",
  num, denom, frac[r].num, frac[r].denom, frac[s].num, frac[s].denom);
 
}

int main (int argc, char *argv[]){
  int i, j, k;

  //init fracs
  for (i = 0 ; i < 100; i++)
    for (j = 0 ; j < 100; j++) {
      k = i*100+j;
      frac[k].num = i+1;
      frac[k].denom = j+1;
      frac[k].val = (float)frac[k].num/(float)frac[k].denom;
    }

  qsort (frac, SIZE, sizeof(fracS), compare);

  findEnds(11,21);
  findEnds(34,87);

  return 0; 
}

Posted by vectorboy on 2004-07-23 16:35:26