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. (More information can be found in the instructions for Programming Assignment 2.)
[2 points] Prime Factorization.
Every integer greater than 1 can be expressed as the product of one or more prime numbers (which may be repeated). For example, \(60 = 2 \times 2 \times 3 \times 5\), and two, three, and five are all prime. This is called the number's prime factorization, and it is unique for each integer number of at least 2.
A number \(n\)'s prime factorization can be calculated using the following algorithm.
Set dividend equal to \(n\).
Set possible_factor equal to 2.
Set factors to be an empty array.
While dividend is not 1, do the following:
If possible_factor is a divisor of dividend:
Otherwise, (if you did not execute the substeps 1 and 2, above):
Return factors.
Hint: To determine if a number is a divisor of another number, think about using the modulo operator. If y is a divisor of x, what would x % y equal?
Implement this algorithm as a Ruby function called factor(n) (stored in factor.rb). Your function should be able to be used as follows:
>> factor(60) => [2, 2, 3, 5] >> factor(45) => [3, 3, 5] >> factor(35) => [5, 7] >> factor(13) => [13]
[2 points] Printing an ASCII-art Triangle.
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 triangle shown below, are easy to create—even at different sizes—algorithmically.
*
***
*****
*******
*********
***********
This triangle can be created using the following algorithm, which requires the triangle's height (that is, the number of lines in the triangle). It assumes that height is non-negative.
For each integer \(i\) from 1 through \(\textit{height}\), inclusive, do the following:
Print \(\textit{height}-i\) spaces.
Print \(2i - 1\) asterisks ("*").
Print the new line character ("\n").
Hint: You will need loops here! In fact, 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 triangle(height) (in triangle.rb) that implements this algorithm. Your function should be able to be used as follow:
>> triangle(3)
*
***
*****
=> nil
>> triangle(5)
*
***
*****
*******
*********
=> 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 (in years) that 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 implements this algorithm giving the result as shown below. You should insure that all divisions are floating point division. You may assume that the interest rate will be at least 0.00001.
Example:
>> load "doubling.rb" => true >> doubling(0.1) => 6.93127512931824 >> doubling(0.05) => 13.8632953166962 >> doubling(0.01) => 69.3149864673615
Pascal's Triangle
[1 point] Factorial.
The factorial of \(n\), written \(n!\) is \(1 \times 2 \times \ldots \times n\), n ≥ 1. Note that \(0!\) = 1 by definition.
Recall, that factorial can be computed using the following Ruby function:
def factorial(n)
result = 1
for i in 1..n do
result = result * i
end
return result
end
In factorial.rb, write the function factorial(n) that computes \(n!\) for any non-negative integer \(n\) (i.e. \(n\) ≥ 0). Add a comment that explains why this function works correctly when n = 0.
Example:
>> factorial(4) => 24 >> factorial(0) => 1[3 points] The Triangle.
The first \(n\) rows of a slightly rotated version of Pascal's Triangle can be computed using the following algorithm:
For each integer \(i\) from \(0\) through \(n-1\), inclusive, do the following:
For each integer \(j\) from \(0\) through \(i\), inclusive, do the following:
Print a new line character ("\n").
Return nil.
In pascal.rb, define a function pascal(n) that implements this algorithm to produce \(n\) rows of Pascal's Triangle in the format shown in the example below. You will need to figure out how to accomplish step I.A.2 so that it right aligns each column; you can assume that the largest value in the triangle is less than 1000. You should make calls to your factorial function from part (a) to get the values of \(i!\), \(j!\), and \((i-j)!\).
Example:
>> load "factorial.rb" => true >> 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
You should now have a pa3 directory that contains the files factor.rb, triangle.rb, doubling.rb, factorial.rb, and pascal.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 starting after lab finishes on Friday, 5/24.)