Programming Projects

Programming Projects require more problem-solving than Practice Programs and can usually be solved many different ways. Visit www.myprogramminglab.com to complete many of these Programming Projects online and get instant feedback.

  1. The formula for computing the number of ways of choosing r different things from a set of n things is the following:

    C(n, r)=n!/(r! *(n−r)!)

    The factorial function n! is defined by

    n!=n*(n−1)*(n−2)*…*1

    Discover a recursive version of this formula and write a recursive function that computes the value of the formula. Embed the function in a program and test it.

  2. Write a recursive function that has an argument that is an array of characters and two arguments that are bounds on array indexes. The function should reverse the order of those entries in the array whose indexes are between the two bounds. For example, if the array is

    a[0] == 'A' a[1] == 'B' a[2] == 'C' a[3] == 'D' a[4] == 'E'

    and the bounds are 1 and 4, then after the function is run the array elements should be

    a[0] == 'A' a[1] == 'E' a[2] == 'D' a[3] == 'C' a[4] == 'B'

    Embed the function in a program and test it. After you have fully debugged this function, define another function that takes a single argument which is an array that contains a string value and that reverses the spelling of the string value in the array argument. This function will include a call to the recursive definition you did for the first part of this project. Embed this second function in a program and test it.

  3. Write an iterative version of the recursive function in Programming Project 1. Embed it in a program and test it.

  4. Write a recursive function to sort an array of integers into ascending order using the following idea: Place the smallest element in the first position, then sort the rest of the array by a recursive call. This is a recursive version of the selection sort algorithm discussed in Chapter 7. (Note: Simply taking the program from Chapter 7 and plugging in a recursive version of indexOfSmallest will not suffice. The function to do the sorting must itself be recursive and not merely use a recursive function.)

  5. Towers of Hanoi: There is a story about Buddhist monks who are playing this puzzle with 64 stone disks. The story claims that when the monks finish moving the disks from one post to a second via the third post, time will end.

    A stack of n disks of decreasing size is placed on one of three posts. The task is to move the disks one at a time from the first post to the second. To do this, any disk can be moved from any post to any other post, subject to the rule that you can never place a larger disk over a smaller disk. The (spare) third post is provided to make the solution possible. Your task is to write a recursive function that describes instructions for a solution to this problem. We don’t have graphics available, so you should output a sequence of instructions that will solve the problem.

    (Hint: If you could move up n−1 of the disks from the first post to the third post using the second post as a spare, the last disk could be moved from the first post to the second post. Then by using the same technique (whatever that may be) you can move the n−1 disks from the third post to the second post, using the first disk as a spare. There! You have the puzzle solved. You only have to decide what the nonrecursive case is, what the recursive case is, and when to output instructions to move the disks.)

  6. The game of “Jump It” consists of a board with n positive integers in a row, except for the first column, which always contains 0. These numbers represent the cost to enter each column. Here is a sample game board where n is 6:

    A row of 6 adjacent boxes containing the following numbers, respectively: 0, 3, 80, 6, 57, 10.

    The object of the game is to move from the first column to the last column with the lowest total cost. The number in each column represents the cost to enter that column. You always start the game in the first column and have two types of moves. You can either move to the adjacent column or jump over the adjacent column to land two columns over. The cost of a game is the sum of the costs of the columns visited.

    In the board shown above, there are several ways to get to the end. Starting in the first column, our cost so far is 0. We could jump to 80, then jump to 57, then move to 10 for a total cost of 80 + 57 + 10 = 147. However, a cheaper path would be to move to 3, jump to 6, then jump to 10, for a total cost of 3 + 6 + 10 = 19.

    Write a recursive solution to this problem that computes the lowest cost of the game and outputs this value for an arbitrarily large game board represented as an array. Your program doesn’t have to output the actual sequence of jumps, only the lowest cost of this sequence. After making sure that your solution works on small arrays, test it on boards of larger and larger values of n to get a feel for the scalability and efficiency of your solution.

  7. Suppose we can buy chocolate bars from the vending machine for $1 each. Inside every chocolate bar is a coupon. We can redeem 7 coupons for 1 chocolate bar from the machine. We would like to know how many chocolate bars can be eaten, including those redeemed via coupon, if we have n dollars.

    For example, if we have $20, then we can initially buy 20 chocolate bars. This gives us 20 coupons. We can redeem 14 coupons for 2 additional chocolate bars. These two additional chocolate bars have 2 more coupons, so we now have a total of 8 coupons when added to the 6 left over from the original purchase. This gives us enough to redeem for 1 final chocolate bar. As a result we now have 23 chocolate bars and 2 leftover coupons.

    Write a recursive solution to this problem that inputs from the user the number of dollars to spend on chocolate bars and outputs how many chocolate bars you can collect after spending all your money and redeeming as many coupons as possible. Your recursive function will be based upon the number of coupons owned.

  8. Some problems require finding all permutations (different orderings) of a set of items. For a set of n items { a1, a2, a3, . . . an } there are n! permutations. For example, given the set {1, 2, 3} there are six permutations:

    {3, 2, 1} {2, 3, 1} {2, 1, 3} {3, 1, 2} {1, 3, 2} {1, 2, 3}

    Write a recursive function that generates all the permutations of a set of numbers. The general outline of a solution is given here, but the implementation is up to you. The program will require storing a set of permutations of numbers that you can implement in many ways (for example, linked lists of nodes, linked lists of vectors, arrays, etc.) Your program should call the recursive function with sets of several different sizes, printing the resulting set of permutations for each.

    One solution is to first leave out the n th item in the set. Recursively find all permutations using the set of (n−1) items. If we insert the nth item into each position for all of these permutations, then we get a new set of permutations that includes the nth item. The base case is when there is only one item in the set, in which case the solution is simply the permutation with the single item.

    For example, consider finding all permutations of {1, 2, 3}. We leave the 3 out and recursively find all permutations of the set {1, 2}. This consists of the permutations:

    {1, 2}         {2, 1}

    Next we insert the 3 into every position for these permutations. For the first permutation, we insert the 3 in the front, between 1 and 2, and after 2. For the second permutation, we insert the 3 in the front, between 2 and 1, and after 1:

    {3, 1, 2} {1, 3, 2} {1, 2, 3}  {3, 2, 1} {2, 3, 1} {2, 1, 3}

    The resulting six permutations comprise all permutations of the set {1, 2, 3}.

  9. The word ladder game was invented by Lewis Carroll in 1877. The idea is to begin with a start word and change one letter at a time until arriving at an end word. Each word along the way must be an English word.

    For example, starting from FISH you can make a word ladder to MAST through the following ladder:

    FISH, WISH, WASH, MASH, MAST

    Write a program that uses recursion to find the word ladder given a start word and an end word, or determines if no word ladder exists. Use the file words.txt that is available online with the source code for the book as your dictionary of valid words. This file contains 87314 words. Your program does not need to find the shortest word ladder between words, any word ladder will do if one exists.