This chapter is from the book
This chapter is from the book
This chapter is from the book
Creative Exercises
2.3.15 Binary representation. Write a program that takes a positive integer n (in decimal) as a command-line argument and prints its binary representation. Recall, in PROGRAM 1.3.7, that we used the method of subtracting out powers of 2. Now, use the following simpler method: repeatedly divide 2 into n and read the remainders backward. First, write a while loop to carry out this computation and print the bits in the wrong order. Then, use recursion to print the bits in the correct order.
2.3.16 A4 paper. The width-to-height ratio of paper in the ISO format is the square root of 2 to 1. Format A0 has an area of 1 square meter. Format A1 is A0 cut with a vertical line into two equal halves, A2 is A1 cut with a horizontal line into two halves, and so on. Write a program that takes an integer command-line argument n and uses StdDraw to show how to cut a sheet of A0 paper into 2n pieces.
2.3.17 Permutations. Write a program Permutations that takes an integer command-line argument n and prints all n ! permutations of the n letters starting at a (assume that n is no greater than 26). A permutation of n elements is one of the n ! possible orderings of the elements. As an example, when n = 3, you should get the following output (but do not worry about the order in which you enumerate them):
bca cba cab acb bac abc
2.3.18 Permutations of size k. Modify Permutations from the previous exercise so that it takes two command-line arguments n and k, and prints all P(n, k) = n ! / (n–k)! permutations that contain exactly k of the n elements. Below is the desired output when k = 2 and n = 4 (again, do not worry about the order):
ab ac ad ba bc bd ca cb cd da db dc
2.3.19 Combinations. Write a program Combinations that takes an integer command-line argument n and prints all 2n combinations of any size. A combination is a subset of the n elements, independent of order. As an example, when n = 3, you should get the following output:
a ab abc ac b bc c
Note that your program needs to print the empty string (subset of size 0).
2.3.20 Combinations of size k. Modify Combinations from the previous exercise so that it takes two integer command-line arguments n and k, and prints all C(n, k) = n ! / (k !(n–k)!) combinations of size k. For example, when n = 5 and k = 3, you should get the following output:
abc abd abe acd ace ade bcd bce bde cde
2.3.21 Hamming distance. The Hamming distance between two bit strings of length n is equal to the number of bits in which the two strings differ. Write a program that reads in an integer k and a bit string s from the command line, and prints all bit strings that have Hamming distance at most k from s. For example, if k is 2 and s is 0000, then your program should print
0011 0101 0110 1001 1010 1100
Hint: Choose k of the bits in s to flip.
2.3.22 Recursive squares. Write a program to produce each of the following recursive patterns. The ratio of the sizes of the squares is 2.2:1. To draw a shaded square, draw a filled gray square, then an unfilled black square.
2.3.23 Pancake flipping. You have a stack of n pancakes of varying sizes on a griddle. Your goal is to rearrange the stack in order so that the largest pancake is on the bottom and the smallest one is on top. You are only permitted to flip the top k pancakes, thereby reversing their order. Devise a recursive scheme to arrange the pancakes in the proper order that uses at most 2n – 3 flips.
2.3.24 Gray code. Modify Beckett (PROGRAM 2.3.3) to print the Gray code (not just the sequence of bit positions that change).
2.3.25 Towers of Hanoi variant. Consider the following variant of the towers of Hanoi problem. There are 2n discs of increasing size stored on three poles. Initially all of the discs with odd size (1, 3, ..., 2n-1) are piled on the left pole from top to bottom in increasing order of size; all of the discs with even size (2, 4, ..., 2n) are piled on the right pole. Write a program to provide instructions for moving the odd discs to the right pole and the even discs to the left pole, obeying the same rules as for towers of Hanoi.
2.3.26 Animated towers of Hanoi. Use StdDraw to animate a solution to the towers of Hanoi problem, moving the discs at a rate of approximately 1 per second.
2.3.27 Sierpinski triangles. Write a recursive program to draw Sierpinski triangles (see PROGRAM 2.2.3). As with Htree, use a command-line argument to control the depth of the recursion.
2.3.28 Binomial distribution. Estimate the number of recursive calls that would be used by the code
public static double binomial(int n, int k)
{
if ((n == 0) && (k == 0)) return 1.0;
if ((n < 0) || (k < 0)) return 0.0;
return (binomial(n-1, k) + binomial(n-1, k-1))/2.0;
}to compute binomial(100, 50). Develop a better implementation that is based on dynamic programming. Hint: See EXERCISE 1.4.41.
2.3.29 Collatz function. Consider the following recursive function, which is related to a famous unsolved problem in number theory, known as the Collatz problem, or the 3n+1 problem:
public static void collatz(int n)
{
StdOut.print(n + " ");
if (n == 1) return;
if (n % 2 == 0) collatz(n / 2);
else collatz(3*n + 1);
}For example, a call to collatz(7) prints the sequence
7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
as a consequence of 17 recursive calls. Write a program that takes a command-line argument n and returns the value of i < n for which the number of recursive calls for collatz(i) is maximized. The unsolved problem is that no one knows whether the function terminates for all integers (mathematical induction is no help, because one of the recursive calls is for a larger value of the argument).
2.3.30 Brownian island. B. Mandelbrot asked the famous question How long is the coast of Britain? Modify Brownian to get a program BrownianIsland that plots Brownian islands, whose coastlines resemble that of Great Britain. The modifications are simple: first, change curve() to add a random Gaussian to the x-coordinate as well as to the y-coordinate; second, change main() to draw a curve from the point at the center of the canvas back to itself. Experiment with various values of the parameters to get your program to produce islands with a realistic look.
2.3.31 Plasma clouds. Write a recursive program to draw plasma clouds, using the method suggested in the text.
2.3.32 A strange function. Consider McCarthy’s 91 function:
public static int mcCarthy(int n)
{
if (n > 100) return n - 10;
return mcCarthy(mcCarthy(n+11));
}Determine the value of mcCarthy(50) without using a computer. Give the number of recursive calls used by mcCarthy() to compute this result. Prove that the base case is reached for all positive integers n or find a value of n for which this function goes into an infinite recursive loop.
2.3.33 Recursive tree. Write a program Tree that takes a command-line argument n and produces the following recursive patterns for n equal to 1, 2, 3, 4, and 8.
2.3.34 Longest palindromic subsequence. Write a program LongestPalindromicSubsequence that takes a string as a command-line argument and determines the longest subsequence of the string that is a palindrome (the same when read forward or backward). Hint: Compute the longest common subsequence of the string and its reverse.
)
)
)