Simplified vulgar fractions in C

Question

"How to write an algorithm that, given the number n, yields all simplified vulgar fractions that have the denominator 1..n"
(I hope I could formulate it correctly, feel free to rephrase.)

Example: If n is 3, the result should be like "1/2 1/3 2/3"

We talked about this issue at the end of the last class. He showed us the solution and asked us to understand the code. Here he is:

#include<stdio.h> void main() { int p,m,n,i,j,a,b; p=7; m=0; n=1; do { printf("%d/%d\n",m,n); i=j=1; for(b=2; b<=p; b++) { a=m*b/n+1; if(a*j<b*i) { i=a; j=b; } } m=i; n=j; } while(i<j); } 

I am new to C and just learning the code, to be honest, I couldn't figure out what this code was doing. And he also prints "0/1", I also wonder why this is so, I think that this should not print it.

Here is my basic approach to this problem:

 #include <stdio.h> int gcd(int a, int b) // Finds the GCD of two numbers. { int temp; while (a) { temp = a; a = b % a; b = temp; } return b; } int main(void) { int i, j; for (i = 1; i <= 7; i++) // Denominator goes from 1 to 7 for (j = 1; j < i; j++) // Numerator goes from 1 to denominator if (gcd(i, j) == 1) printf("%d/%d ", j, i); // If the numerator and the denominator // are coprimes then print the fraction return 0; } 

"n" is 7 in both codes. I checked the runtime with much larger numbers, and my algorithm is faster than the other. Therefore, I do not understand why another code is needed. Any suggestions / corrections about my code are also welcome.

Answer 1

Your professor code looks like it can be complex, perhaps an exercise. If so, I cannot say that I agree with this practice.

Your nested loop approach is exactly how I would approach the solution.

And he also prints "0/1", I also wonder why this is so, I think that this should not print it.

Simply put, it prints "0/1" because of this line:

 printf("%d/%d\n",m,n); 

The values ​​of m and n are initialized to 0 and 1 immediately before the do loop, so on the first pass it prints just that.

Answer 2

Your code is better than the first insertion in several ways. Looping over b is a crappy way to find a common simple coefficient for m and n . But it only works up to b=7 , so the first program can print 11/121 and other undefined fractions!

If the loop over b was correctly encoded, it will take O(sqrt(n)) . Your gcd() (using Euclidean algebra) has O(log(n)) time.

Answer 3

Other code is extremely poorly written. Single-letter variables for non-idiomatic applications? empty function ()? No comments? No one should understand that this code, and especially not students.

Your code seems pretty competent - it is much clearer and cleaner than other code, and in many ways surpasses all. The only thing I would like to do is, firstly, you should take N as user input from the console to make it easy to re-transmit the program for different values, and you should also comment on the GCD function explaining its operations.