Project Euler/33
From charlesreid1
Problem Statement
The fraction 49/98 can mistakenly be reduced to a correct reduced value 4/8 by cancelling out the 9s.
The cas of fractions like 30/50 are considered trivial.
There are four non-trivial examples of this type of fraction, all less than 1 in value, with 2-digit numbers in the denominator and in the numerator.
Find the product of these four fractions, and give the value of the denominator.
Solution Approach
The solution algorithm for this problem is not difficult to come up with, given that the numerator and denominator are 2-digit numbers and that all of the fractions are less than 1. This will be a nested for loop, with the outer loop being the denominator from 10 to 99, and the inner loop being the numerator from 10 to denominator.
The more subtle part of the problem is how you handle the fractions, and determining if two fractions are equivalent, in the program.
My approach was to create a Fraction class that stores the numerator and denominator:
- Checking if a fraction is in its most reduced form is equivalent to checking if the gcd of the denominator and numerator is 1
- Checking if two fractions are equivalent (to within some numerical tolerance) can be implemented by just doing the division for the two fractions, and checking the absolute value of the difference
Flags
