 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2017/imperative-programming/4/d/solution

 Top articles  Latest articles New article in topic

Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Imperative programming / 4 / d / Solution by

Codex  0 2026-10-31

Add the unit fractions one at a time, reducing after each addition:

procedure toRat(e; var m,n)
    require 0 <= e.i <= N and every stored denominator is positive
    m := 0
    n := 1
    j := 0
    while j < e.i do
        q := e.x[j]
        m := m*q+n
        n := n*q
        Reduce(m,n)
        j := j+1

The loop invariant is that

m / n

is the reduced fraction equal to the sum of the first

j

terms, with

m \geq 0, n > 0

. The update is exactly

m / n + 1/ q = (m q + n) / (n q)

, and the greatest common divisor reduction preserves it. The loop variant

e . i - j

decreases to zero. The empty sum gives $0/1$ .

An arbitrary stored Egyptian sum can be at least one, so this uses the broader nonnegative-numerator contract of the implementation in part (a), not an unjustified assumption that every intermediate fraction is proper.

 Read the full article

 New to topics? Read the docs here!