Starting from:

$30

02393 C++ Programming Exercises  Assignment 9 -Solved

The goal of the following exercises is for you to familiarize with recursion. 
All the exercises can be solved without recursion, but we suggest that you try 
to use recursion. In all cases input is to be read from cin and the result is to 
be provided to cout. 
Reverse 
Write a program that reverses a sequence of integers, as provided in 
the standard input. 
For example, if the input is 
1 2 3 4 5 
then the output should be 
5 4 3 2 1 
Fibonacci 
Write a program that computes the Fibonacci numbers Fni for a 
sequence n0, . . . nk given in the standard input. See http://en.wikipedia. 
org/wiki/Fibonacci_number 
For example if the input is 
0 5 
then the output should be 
1 8 
since F0 is 1 and F5 is 8. 
Palindrome 
Write a program that decides whether a sequence of integers is 
a palindrome, i.e. if reading the sequence from right to left results in the very 
same sequence. 
For example, if the input is 
13 22 33 22 13 
then the output should be 
yesbut if the input is 
13 22 31 
then the output should be 
no 
since the right-to-left reading is 
31 22 13 
Note that the right-to-left reading does not refer to individual digits, but to 
entire numbers. 
The Levenshtein distance 
The Levenshtein distance between two sequences 
of characters u = u1, u2, . . . , uk and v = v1, v2, . . . , vl is defifined by: 
d(u, v) = 














|v| 
if |u| = 0, 
|u| 
if |v| = 0, 
min 




 
d(
u
1 , v
) + 1 
d(
u, v

) + 1 
d(u1 , v1 ) + f(u1, v1) 
otherwise. 
where |w| denotes the length of a sequence w; w1 denotes the suffiffiffix w2, w3, . . . 
of a sequence w = w1, w2, w3, . . . ; w1 denotes the fifirst element of a sequence 
w = w1, w2, w3, . . . ; and f(e, e0 ) is 0 when e = e0 and 1 otherwise. 
As an example you can easily check that the distance d(“AB”, “B”) between 
“AB” and “B” is 1 since: 
d(“AB”, “B”) = min(d(“B”, “B”) + 1, d(“AB”, “”) + 1, d(“B”, “”) + 1) = min(1, 3, 2) = 1 
d(“B”, “B”) = min(d(“”, “B”) + 1, d(“B”, “”) + 1, d(“”, “”) + 0) = min(2, 2, 0) = 0 
d(“AB”, “”) = 2 
d(“B”, “”) = 1 
d(“”, “B”) = 1 
Write a program that reads two words and returns their distance. 
Challenges. Try to write a function that, given a set of elements, computes 
all the possible permutations of the elements. Try to write a function that, 
given a set, computes its powerset. 
2

More products