Computer programming - Lab 12: Structures

1.Rational numbers Define a structure type for rational numbers, holding numerator and denominator. Implement functions to add and multiply rationals. Return results that are in canonical form (denominator is positive and gcd with numerator is 1).

2.Continued fractions A real number 0 < x < 1 can be successively approximated in a continued fraction with 1/a1, 1/(a1+1/a2), 1/(a1+1/(a2+1/a3)), ... where a1, a2, a3, ... are natural numbers. In the initial approximation, a1 is ⌊1/x⌋, and one continues using the same rule for the fractional part of the denominator approximated with a1, etc. One obtains a sequence of rational numbers p1/q1, p2/q2, ... that approximate x increasingly well, alternating from above and below.
Define a structure that represents a rational number and compute (recursively) the nth rational approximation of a fractional number x using a continued fraction.

3.Prime factors. Define a data structure to represent an unsigned number as a product of powers of primes. Write a function that computes the product of two numbers, in the same representation.

4. 2D vectors Define a structure type for vectors in 2-dimensional space. Define functions for addition, subtraction and magnitude, and to read a vector (space-separated real coordinates of endpoint, assuming zero origin). Use this function to compute the total length of the segments drawn in the path d="..." element read from a SVG file. The path keeps a current point, and the commands are of the form letter x y, with L/l for "line to" and M/m for "move", uppercase for absolute coordinates, and lowecase for relative.

5. CSV files A .csv file contains the grade situation for a class of students. Each line contains fields separated by commas. The first field is the student name, followed by up to 10 fields with real-numbered grades or other characters; any remainder of the line is ignored.
Read the file using an appropriate data structure; you may assume there are at most 200 students. Compute averages for the students that have 10 passing grades. Sort students in decreasing order of their grade averages; break ties in alphabetical order. Print the sorted list with grade averages.

6. Sorting text Design a data structure that stores a line of text, together with its length (in characters) and number of words. Read all lines of a file named on the command line into an array of such structures. Sort and print the file with lines in increasing order of length, breaking ties first in decreasing order of words and then in alphabetical order.

7. Predicate formulas. A formula in predicate logic is

Design a data structure to represent a predicate formula. Write a function to print and another function to read a predicate formula written as an s-expression with operators written in prefix notation, e.g.,
(and (=> p q) (or q r) (not f)). (This syntax is used in the SMT2 format).

8.Processor simulation A simple processor has registers labeled by lowercase letters and uses the following instructions:

Design a structure type that can hold such instructions.
Write a function that simulates the execution of code given by such instruction. The function will receive as parameters an array with register values (for all letters) and another array with the code. Use it for the computation of factorial.


Marius Minea
Last modified: Wed Dec 16 21:30:00 EET 2015