4
\$\begingroup\$

The 'friendly form' of a number is written as a sum of reciprocals of distinct positive integers. eg. $$\frac{4}{5} = \frac{1}{2} + \frac{1}{4} +\frac{1}{20}$$

I have written a python program that calculates the friendly form of an inputted fraction.

import math
from fractions import Fraction

def decompose(x):
    if x.numerator == 1:
        return [x]

    # Finds the largest fraction m = 1/p which is less than or equal to x
    m = Fraction(1, math.ceil(float(1 / x)))
    x = x - m

    #Recursively returns a chain of fractions
    return decompose(x) + [m]

def main():
    inp = input("Enter positive fraction in form \"a/b\": ")

    try:
        x = Fraction(inp)
    except ValueError:
        print("Invalid input.")
        return

    if float(x) == 0:
        print("Enter non-zero value.")
        return

    if float(x) < 0:
        print("Converting to positive value.")
        x = -x

    if float(x) >= 1:
        print("Enter valid fraction")
        return

    answer = decompose(x)
    for a in answer:
        print(a)

if __name__ == "__main__":
    main()
\$\endgroup\$
4
\$\begingroup\$

Overall, the code is very good, but a few tiny improvements can be made:

  • In the decompose function x = x - m can be replaced with x -= m

  • Instead of return decompose(x) + [m] and such, use yield

  • Instead of for a in answer ..., use print(*answer, sep='\n')

  • In the decompose function, math.ceil(float(1 / x)) can be changed to math.ceil(1 / x). Python 3.x automatically interprets / as a float operator

  • As only math.ceil is used, you could just do from math import ceil

Here's the final code:

from math import ceil
from fractions import Fraction

def decompose(x):
    if x.numerator == 1:
        yield x
        return 

    m = Fraction(1, ceil(1 / x))
    x -= m

    yield m
    yield from decompose(x)

def main():
    inp = input("Enter positive fraction in form 'a/b': ")

    try:
        x = Fraction(inp)

    except ValueError:
        print("Invalid input.")
        return

    if float(x) == 0:
        print("Enter non-zero value.")
        return

    if float(x) < 0:
        print("Converting to positive value.")
        x = -x

    if float(x) >= 1:
        print("Enter valid fraction")
        return

    print(*decompose(x), sep='\n')

if __name__ == "__main__":
    main()

Hope this helps!

|improve this answer|||||
\$\endgroup\$
3
\$\begingroup\$

Every recursive algorithm can be rewritten without recursion. In worst case, using one stack.

I'm not a pythonist, so instead I will write in pseudocode:

def decompose(x)
    result = []
    while x.numerator != 1:
        m = Fraction(1, ceil(1/x))
        x -= m
        result.append(m)

    result.append(x)
    return result

Now using yield as suggested by @Srivaths it gets simpler:

def decompose(x)
    while x.numerator != 1:
        m = Fraction(1, ceil(1/x))
        x -= m
        yield m

    yield x
|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.