As always, these exercises are optional, but I recommend that you work through some of them, especially to get more practice with recursion.
Suppose that we modify the Tower of Hanoi puzzle so that moves between the left peg to the right peg are disallowed: you may make moves only between the left and middle pegs, or between the middle and right pegs.
Write a program that reads an integer N and prints out the sequence of moves needed to solve this modified Tower of Hanoi, i.e. to move a tower of N disks from the left peg to the right peg.
Consider another modified Hanoi in which moves are allowed only from A to B, from B to C and from C to A, where A, B and C are the left, midle and right pegs. Moves in the opposite direction (e.g. from B to A) are not allowed.
Is it always possible to move N disks from the left to right peg (A to C) even in this case? If so, write a program that prints out the sequence of moves.
Write a recursive function reverse(s:
string): string that reverses the string s. You may use string
concatenation, but may not call any library functions or use any
loops.
Write a recursive function that determines whether an array of integers is a palindrome. Do not use any loops.
Write a recursive function
replaceChar(s: string, c: char, d: char): string
that returns a transformed string in which all occurrences of the
character c have been replaced with the
character d. Do not use any loops.
Write a recursive function
trim(s: string): string
that returns a copy of s with all spaces
removed from the front and end. Do not use any loops.
Write a recursive function printBinary(n:
integer) that prints out the binary representation of n.
Use recursion to write a function sameAsFirst(a:
array of integer): integer that returns the number of integers
in an array that are equal to its first element. You may use
auxiliary functions, but do not use any loops.
A composition of an integer N > 0 is a sequence of positive integers i ≤ N that add up to N, where different orders are considered to be distinct compositions. Write a program that reads an integer N and writes out all its compositions. For example, if N = 4, the output should be
4 3 + 1 2 + 2 2 + 1 + 1 1 + 3 1 + 2 + 1 1 + 1 + 2 1 + 1 + 1 + 1
Write a program that reads an integer N ≥ 1 and prints all base
4 numbers that have N or fewer digits, in numeric order. Do not use
the div or mod
operators in your program. For example, if N is 3 then the output
will be
0 1 2 3 10 11 12 … 331 332 333
Write a program that computes the sum of all prime numbers whose digits are permutations of the digits 1..9.
Write a program that reads a word W and an integer N. Consider W to be a set of characters, and print out all subsets of W of length N. Write the characters in each subset in the same order in which they appear in W. For example, if W = ‘tram’ and N = 3, the output will be
tra trm tam ram
Write a program which reads a number N and writes all strings of length N containing only the letters ‘a’, ‘b’ and ‘c’ and in which no adjacent characters are the same. Write the strings in alphabetical order. For example if N = 3 then the output is
aba abc aca acb bab bac ...
Write a program that reads an integer N, and writes the number of distinct permutations a1, …, aN of the integers {1, 2, … N } such that a1 < a2, a2 > a3, a3 < a4, a4 > a5 and so on. Note that the program should write the number of such permutations, not the permutations themeslves.
Write a program that reads an integer N, and writes all N-letter words containing only the letters { a, o, h, k, l } in which consonants and vowels alternate. For example, if N = 4 then here are some of the words that will be printed:
kola haha lala okok akah
Write a function that for an integer N determines the number of distinct paths in the xy-plane such that
Each path begins at (1, 1) and ends at (N, N).
Each path consists of a sequence of steps of length 1, each of which moves to the right (increasing x) or upward (increasing y).
No path ever touches a point (x, y) where x > 2y or y > 2x.
Write a program that reads an integer N <= 15 and reports the number of distinct paths in the xy-plane of length ≤ N such that
Each path begins at (0, 0) and ends at (0, 0), and does not otherwise cross the point (0, 0).
Each path consists of a sequence of steps of length 1, each of which goes up, down, left or right.
Write a function summitSearch that
takes an array of integers which is guaranteed to contain a strictly
increasing sequence followed by a strictly decreasing sequence. For
example, the array might contain these values:
3, 6, 12, 14, 18, 22, 19, 18, 15, 11, 8, 4, 3, 2, 1
The function should return the largest value in the array. It must run in time O(log n), where n is the length of the input array.
Solve Project Euler’s Problem 12.
Solve Project Euler’s Problem 14.