Write a C++ recursive method countBinary that has one integer parameter n and re

Question

Write a C++ recursive method countBinary that has one integer parameter n and returns the number of binary strings of length n that do not have two consecutive 0's. For example, for n = 4, the number of binary strings of length 4 that do not contain two consecutive 0's is 8: 1111, 1110, 1101, 1011, 1010, 0111, 0110, 0101 For this problem, your method needs to return only the number of such strings, not the strings themselves. HINT: The number of such strings is the number of strings that start with a 1 plus the number of strings that start with 01. Determine the complexity.

Explanation / Answer

(1 pts) Consider a puzzle Jump that consists of a row of positive integers, except the rightmost number, which is always a zero. A peg is placed on the leftmost number. At each step, you may move the peg either left or right a distance equal to the number under the peg, but not off either end of the row of numbers. The goal is to move to the rightmost number. For example,

There may be more that one solution. But not all puzzles are solvable. In the following example, you jump back and forth between the two 3s and you never reach the other numbers.

Write a recursive method canSolve that has two parameters, an array of integers and an integer for the starting index. The method should return true if the puzzle can be solved, and false otherwise. You may assume that the integers in the array are positive, except the rightmost one, which is zero, and the start index is not out of bounds.

To avoid repeated looping among 2 or more positions, when you move to a position, change the number at that position to an invalid number (such as -1) so you can recognize that you have been at that position before. For example, in the unsolvable puzzle above, you would start at position 0 and change its value to -1, move to position 3 and change its value to -1, try to move to position 6 (non existing) and then try position 0. Since position 0 has a -1, you have visited it before and the path traveled so far will not lead you to a solution (see below).

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.