Assignment #1
Due September 6
- Make sure JDK 5.0 or later is installed on your machine. Choose a development environment that is comfortable.
- The greatest common divisor of two numbers can be found in a pedestrian
way by just looping through the possible divisors of the smaller number and
determining the largest divisor which also evenly divides the larger number.
This is an O(n) algorithm; it grows linearly in proportion to the value
of the smaller number. A much faster approach, which has been known for about
2500 years, is Euclid's algorithm. Euclid's algorithm finds the gcd of two numbers
by looking at the remainder after division (%) of the two numbers; if this
remainder is 0 then the answer is simply the smaller number; if it is not 0,
then the answer is the gcd of the remainder and the smaller number. For
example, to find gcd(84,48) we would go through the following steps:
84 mod 48 = 36
48 mod 36 = 12
36 mod 12 = 0
so the gcd is 12.
Write two methods, one recursive and one not, to determine the gcd of two numbers using Euclid's algorithm.
- Exercise 1.5 on p. 26
- Exercise 1.6 on p. 26 (more difficult)
- Exercise 1.7 on p. 26
- Pascal's triangle is constructed so that each number is the sum of the two numbers
above it. We also know that each entry in the triangle represents the combination of n things taken
k at a time, where n is the number of the row, and k is how far from the left the
entry is (starting counting with 0 on the far left). This gives rise to Pascal's theorem,
which states that
C(n, k) = C(n -1, k - 1) + C(n - 1, k).
Another way to think of this theorem is to note that the number of ways of choosing k things out of n possibilities must be the sum of all those choices which include a given thing, X, from among the n possibilities, and all those choices which do not include X. There are C(n - 1, k - 1) choices which include X (since X has already been chosen, this is the number of ways of picking the remaining k - 1 items out of the remaining n - 1 possibilities), and there are C(n - 1, k) choices which do not include X (since this is the number of ways of choosing k items out of just those possibilities which do not include X). Use this observation to write a recursive method:int combination(int n, int k)
to return the number of combinations of n things taken k at a time. Note that there is only one way to choose 0 items or all n items. Also note that there are no ways to choose less than 0 items or greater than n items. Test to make sure that your method works: combination(9,5) should give 126. - Exercise 1.10 on p. 26.
- Exercise 1.13 on p. 26.
Updated August 24, 2007