During this activity, students should be able to:
This activity helps the student develop the following skills, values and attitudes: ability to analyze and synthesize, capacity for identifying and solving problems, and efficient use of computer systems.
Individually, solve the following set of recursive
programming exercises using Erlang. Place all your functions in a module
called recursion
.
NOTE: For this activity, you are not allowed to use any
of the functions defined in Erlang's lists
module.
but_last
returns a list with the same
elements as its input list but excluding the last element. Assume
that the input list contains at least one element. For example:
> recursion:but_last([a, b, c, d]). [a,b,c] > recursion:but_last([1]). [] > recursion:but_last([first, middle, last]). [first,middle]
insert
takes two arguments: a number
N and a list of numbers L in ascending order. It
returns a new list with the same elements as L but
inserting N in its corresponding place. For example:
> recursion:insert(5, [1, 3, 6, 7, 9, 16]). [1,3,5,6,7,9,16] > recursion:insert(10, [1, 5, 6]). [1,5,6,10] > recursion:insert(14, []). [14]
sort
takes an unordered list of numbers as
an argument, and returns a new list with the same elements but in
ascending order. You must use the insert
function
defined in the previous problem. For example:
> recursion:sort([4, 3, 6, 8, 3, 0, 9, 1, 7]). [0,1,3,3,4,6,7,8,9] > recursion:sort([]). []
bcd
takes an integer N as input
(assume that N ≥ 0), and returns a list of strings with
the BCD representation of N. A BCD (Binary Coded Decimal)
number is an encoding for decimal numbers in which each decimal
digit is represented by its own 4-bit binary sequence. Examples:
> recursion:bcd(27). ["0010","0111"] > recursion:bcd(1093). ["0001","0000","1001","0011"] > recursion:bcd(0). ["0000"]
prime_factors
takes an integer N
as input (assume that N > 0), and returns a list
containing the prime factors of N in ascending order. The
prime factors are the prime numbers that divide a number exactly. If
you multiply all the prime factors you get the original number.
Examples:
> recursion:prime_factors(6). [2,3] > recursion:prime_factors(17). [17] > recursion:prime_factors(96). [2,2,2,2,2,3] > recursion:prime_factors(666). [2,3,3,37] > recursion:prime_factors(1). []
compress
takes a list Lst as its
argument. If Lst contains consecutive repeated elements,
they should be replaced with a single copy of the element. The
order of the elements should not be changed. For example:
> recursion:compress([a, a, a, a, b, c, c, a, a, d, e, e, e, e]). [a,b,c,a,d,e]
encode
takes a list Lst as its
argument. Consecutive duplicates of elements in Lst are
encoded as tuples {N, E} where N is the
number of duplicates of the element E. If an element has no
duplicates, it is simply copied into the result list. For example:
> recursion:encode([a, a, a, a, b, c, c, a, a, d, e, e, e, e]). [{4,a},b,{2,c},{2,a},d,{4,e}]
decode
takes as its argument an encoded
list Lst like the output from the previous problem. It
returns the decoded version of Lst. For example:
> recursion:decode([{4, a}, b, {2, c}, {2, a}, d, {4, e}]). [a,a,a,a,b,c,c,a,a,d,e,e,e,e]
combinations
takes two arguments: a list
Lst and a number N. It returns a list containing
all possible combinations of size N taken from Lst
(assume that 0 < N ≤ length(Lst)). For
example:
> recursion:combinations([a, b, c, d], 3). [[a,b,c],[a,b,d],[a,c,d],[b,c,d]] > recursion:combinations([january, february, march], 2). [[january,february],[january,march],[february,march]] > recursion:combinations([1, 2, 3], 1). [[1],[2],[3]] > recursion:combinations([1, 2, 3], 3). [[1,2,3]]
permutations
takes two arguments: a list
Lst and a number N. It returns a list containing
all possible permutations of size N taken from
Lst with no repetitions (assume that 0 < N
≤ length(Lst)). For example:
> recursion:permutations([a, b, c, d], 3). [[a,b,c], [a,b,d], [a,c,b], [a,c,d], [a,d,b], [a,d,c], [b,a,c], [b,a,d], [b,c,a], [b,c,d], [b,d,a], [b,d,c], [c,a,b], [c,a,d], [c,b,a], [c,b,d], [c,d,a], [c,d,b], [d,a,b], [d,a,c], [d,b,a], [d,b,c], [d,c,a], [d,c,b]] > recursion:permutations([january, february, march], 2). [[january,february], [january,march], [february,january], [february,march], [march,january], [march,february]] > recursion:permutations([1, 2, 3], 1). [[1],[2],[3]] > recursion:permutations([1, 2, 3], 3). [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Using the Online
Assignment Delivery System (SETA), deliver the file called
recursion.erl
. No assignments will be accepted through
e-mail or any other means.
IMPORTANT: The program source file must include at the top the author's personal information (name and student id) within comments. For example:
%% ITESM CEM, August 25, 2008. %% Erlang Source File %% Activity: Recursive Functions %% Author: Steve Rogers, 449999 . . (The rest of the program goes here) .
Due date: Monday, August 25.
This activity will be evaluated using the following criteria:
-10 | The program doesn't contain within comments the author's personal information. |
---|---|
10 | The program contains syntax errors. |
DA | The program was plagiarized. |
10-100 | Depending on the amount of exercises that were solved correctly. |