(2) Recall the algorithm for find the greatest common divisor (GCD) of two integers x and y:
Let r = x % y
- If r=0, then GCD = y
- If r!=0, then do the following:
- Let x=y
- Let y=r
- Got back to step 1
You originally did this problem when we studied loops. Now write a program that uses a recursive method to find the GCD of two integers input by the user. Display the GCD when it is found. Try a variety of values to test your program.
|
(5) Pascal’s Triangle is a famous arrangement of numbers first discovered by the Chinese. The name Pascal, however, comes from the French mathematician/philosopher Blaise Pascal, who did extensive work with this triangle and found that it had many connections to various branches of mathematics, such as probability.
Recall that the triangle appears as follows:
1
1 1
1 2 1
1 3 3 1
etc…
In which each of the numbers in the triangle is the sum of the 2 numbers above it. An alternative arrangement of the triangle is as follows:
1
1 1
1 2 1
1 3 3 1
etc…
The numbers in the triangle can be generated using the following recursive algorithm:
For row n and column k, the coefficients of Pascal’s Triangle, C(n, k), can be found by
C(n, 0) = 1
C(n, k) = 0, if k > n
C(n, k) = C(n-1, k) + C(n-1, k-1), for n ≥ k > 0
Important Note: The first row is defined as row 0 and the first column is defined as column 0.
-
Your first job is to write a recursive function that will generate the coefficient for any given row and column location. For example, a call of C(2, 1) will return 2, since the coefficient at row 2, column 1 is 2.
- The second task is to use this function, along with nested loops, to generate and display rows 0 through 9 of Pascal’s Triangle in the format as shown in the alternative arrangement above. Don’t worry if things don’t look quite so “pretty.”
|