Introduction to Computer Science - Fall Semester 1998/9 Exercise 6

Due: 4/2/1999

Ex 6.1 Recursion

Write a program that computes the gcd (greatest common divisor) of two positive integers.

int gcd(int p, int q)
{
   int r;
   if ((r = p % q) == )
      return q;
   else
      return (gcd(q,r));
}

First, write a program to test the function (notice that it works only if p¿q). Then write and test an quivalent iterative function.

Ex 6.2 Merge Sort* - bonus

Write a recursive algorithm implementing the following merge sort algorithm:

Given an array n[0..l],

1. Independently sort n[0..l/2-1] and n[l/2..l] 2. Merge the two arrays.

Ex 1.4 (bonus) Binary Representation

The binary representation of a number n is b_{k}b_{k−1} ⋯ b_{0} where

n = b_{0} · 2^{0} + b_{1} · 2^{1} + … + b_{k} · 2^{k}

Write a program that asks the user for an integer and then prints out its binary representation. (Hint: print first the reverse representation b_{0}b_{1} ⋯ b_{k}).