Best Rational Approximation: Difference between revisions
Jump to navigation
Jump to search
imported>Kmk21 Created page with "This problem asks for the best fractional representation of a floating point number less than 1, with a specified denominator maximum. The maximum denominator is 10^5, so we..." |
imported>Kmk21 No edit summary |
||
| Line 4: | Line 4: | ||
You could also start with 0/1, and if the resulting quotient is less than the target, add 1 to the numerator...else add 1 to the denominator. Return whatever comes out best, being sure to check +-1 when you hit the maximum denominator just to be sure you didn't miss an edge case. | You could also start with 0/1, and if the resulting quotient is less than the target, add 1 to the numerator...else add 1 to the denominator. Return whatever comes out best, being sure to check +-1 when you hit the maximum denominator just to be sure you didn't miss an edge case. | ||
Be sure your answer is in lowest terms. | |||
[[Category:ICPC Problems]] | [[Category:ICPC Problems]] | ||
Latest revision as of 23:12, 27 December 2017
This problem asks for the best fractional representation of a floating point number less than 1, with a specified denominator maximum.
The maximum denominator is 10^5, so we can try every denominator. You can either just multiply the input number by the denominator and try the two possible numerators around that, or if you're really bored, you could binary search.
You could also start with 0/1, and if the resulting quotient is less than the target, add 1 to the numerator...else add 1 to the denominator. Return whatever comes out best, being sure to check +-1 when you hit the maximum denominator just to be sure you didn't miss an edge case.
Be sure your answer is in lowest terms.