For this assignment, you will create a Ruby source file containing a ruby function implementing each of the algorithms described below. You should store all of these files in a folder named pa3.
Note: You are responsible for protecting your solutions to these problems from being seen by other students either physically (e.g., by looking over your shoulder) or electronically.
[2 points] Greatest Common Divisor.
In mathematics, the greatest common divisor (gcd) of two or more non-zero integers is the largest positive integer that divides the numbers without a remainder. For example gcd of 24 and 36 is 12.
Below is a Euclidian algorithm for calcutating gcd of two positive integers a and b is as follows
Implement this algorithm as a Ruby function called gcd(a,b) (stored in gcd.rb). Your function should be able to be used as follows:
>> gcd(12,36) => 12 >> gcd(30,75) => 15
[2 points] ASCII-art. (Typos corrected)
By printing out different characters at different locations, it is possible create images. This is sometimes called ASCII art, and works best in a terminal that uses a fixed-width font. Regular shapes, such as the square shown below, are easy to create—even at different sizes—algorithmically.
XXXXX XX-XX XX-XX XX-XX XXXXX
The sides of this square can be created using the following algorithm, which requires the square's size (that is, the number of columns of characters wide and lines of text height the square is). It assumes that size is at least five.
First, print out size copies of the character "X" on one line. Then, for the next \(\textit{size}-2\) lines, print out two copies of "X", print out \(\textit{size}-4\) hyphens, and then two copies of "X". Finally, for the last line print out size copies of the character "X" again.
Hint: You will probably need a loop inside of a loop for part of your solution. If you use a loop inside of another loop, please, choose a different variable for each loop (e.g., if the outer loop uses "i", the inner loop can use "j").
Create a Ruby function make_square(size) (in make_square.rb) that implements this algorithm. Your function should be able to be used as follows:
>> make_square(5) XXXXX XX-XX XX-XX XX-XX XXXXX => nil >> make_square(9) XXXXXXXXX XX-----XX XX-----XX XX-----XX XX-----XX XX-----XX XX-----XX XX-----XX XXXXXXXXX => nil
(4 points) Pascal's Triangle
If you throw a fair coin n times, what are the odds of getting exactly i heads and n-i tails? This is easily calculated using Pascal's triangle. Some examples:
>> pairsum([1, 10, 50, 300, 80]) => [11, 60, 350, 380] >> pairsum([0, 1, 2, 1, 0]) => [1, 3, 3, 1]
for v in x do printf "%4d", v end
The output of your function should look like this:
>> load "pascal.rb" => true >> pascal(10) 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 => nil
[2 points] Doubling Time.
For an account with a deposit of \(P\) dollars that earns interest compounded continuously at an annual rate of \(r\) for \(t\) years, the final amount \(A\) of the account is given by the formula:
\[A = Pe^{rt}\]The bisection method can be used to approximate how much time would be required for an initial deposit to double (i.e., finding a value of \(t\) for which \(0 = e^{rt} - 2\)). It works by maintaining a lower and upper bound for a range in which the desired value of \(t\) is known to exist. In each iteration, it finds the half-way point of that range and determines whether the desired value of \(t\) is above or below that half-way point. The algorithm stops when the range is smaller than some threshold.
The bisection method can be realized using the following algorithm, which is parameterized by rate:
While guess_error is greater than 0.001, do the following:
Set guess to \(\frac{\textit{high} + \textit{low}}{2}.\)
Set guess_error to \(\frac{\textit{high} - \textit{low}}{2}.\)
Return guess.
Write a Ruby function called doubling(rate) in doubling.rb that computes the result using this algorithm. In addition to returning the result, your algorithm should keep track of the number of iterations needed to compute the result and print it, as shown below.
Example:
>> load "doubling.rb" => true >> doubling(0.05) 33 => 13.8633185997605 >> doubling(0.25) 33 => 2.77243088930845
You should now have a pa3 directory that contains the files gcd.rb, make_square.rb, pascal.rb and doubling.rb, each in turn containing the corresponding function. Zip up your directory and upload it using the handin system. (The handin system will accept submissions beginning on Friday until the deadline Tuesday night.)