-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathEgyptianFraction.java
More file actions
62 lines (56 loc) · 1.9 KB
/
EgyptianFraction.java
File metadata and controls
62 lines (56 loc) · 1.9 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
package algorithm.greedyalgorithm;
/**
* The type Egyptian fraction.
*/
public class EgyptianFraction {
/**
* Gets fractions.
*
* @param numerator the numerator
* @param denominator the denominator
*/
public static void getFractions(int numerator, int denominator) {
//if either numerator or denominator is zero
if (denominator == 0 || numerator == 0) {
return;
}
//numerator divides denominator -> fraction in 1/n form
if (denominator % numerator == 0) {
System.out.print("1/" + denominator / numerator);
return;
}
//denominator can divide numerator -> number not a fraction
if (numerator % denominator == 0) {
System.out.println(numerator / denominator);
return;
}
//if numerator greater than denominator
if (numerator > denominator) {
System.out.println(numerator / denominator + " , ");
getFractions(numerator % denominator, denominator);
return;
}
//denominator greater than numerator here
int n = denominator / numerator + 1;
System.out.print("1/" + n + " , ");
//call function recursively for remaining part
getFractions(numerator * n - denominator, denominator * n);
}
/**
* Main.
*
* @param args the args
*/
public static void main(String[] args){
//Example 1
int numerator = 6, denominator = 14;
System.out.print("Egyptian Fraction Representation of " + numerator + "/" + denominator + " is\n ");
getFractions(numerator, denominator);
System.out.println();
//Example 2
numerator = 2;
denominator = 3;
System.out.print("Egyptian Fraction Representation of " + numerator + "/" + denominator + " is\n ");
getFractions(numerator, denominator);
}
}