Fibonacci Sequence and More

[Edward_Nelson]

I am trying to self learn C++, and I bought a tutorial book. Right now, I am on a section about recursives. I got the first example, one to output the Fibonacci sequence, but I am stumped on the second one. The exercises do not come with answers, and that is why I am asking.

I have a ladder with 6 rungs. I can climb up 1 rung, 2 rungs, or 3 rungs at a time. The goal is to find every way I can climb up 10 rungs. For example, the program should output the paths I could take. {1 2 3 4 5 6} , {3.6}. {2 3 4 6}. etc.

I have absolutely no idea how to approach it other than I should probably use an array. If someone could give me part of the code, an outline of the code, or something to point me in the right direction, that'd be great. Don't just want the entire code because that would defeat the purpose.

It is much tougher than the fibonacci code I wrote.

#include <iostream.h>

int print(int i) {
if (i < 1) {
return 0;}
 else if (i == 1 || i == 2) {
return 1;
} else {
return print(i-1) + print(i-2);
}
}

int main() {

int n = 10;

for (int i = 1; i <= n; i++) {
cout << fib(i) << " ";
}

cout << endl;
}

[VernonDozier]

Well, do you have ten rungs or six?

I have a ladder with 6 rungs. I can climb up 1 rung, 2 rungs, or 3 rungs at a time. The goal is to find every way I can climb up 10 rungs.

One way to do it is to split the job in two. The first part is to find all the ways that you can add up to 6 using only 1's, 2's and 3's. Order counts, so:

{1,1,1,1,2} is different from {2,1,1,1,1}. Then you need a helper function to turn these into the actual rung numbers:

{1,1,1,1,2} turns into {1,2,3,4,6}.
{2,1,1,1,1} turns into {2,3,4,5,6}.

One general way is to do this. Everything adds to 6. Your first number is 1, 2, or 3. The remaining numbers will add to 5, 4, or 3 respectively.

Define S(i) as the set of sets of numbers (1 to 3) that add to i:

S(5) = {{1,1,1,1,1}, {1,1,1,2}, {1,1,3}, {3,1,1}, etc.}
S(4) = {{1,1,1,1}, {1,1,2}, {2,1,1}, {2,2}, {1,3}, etc.}
S(3) = {{1,1,1}, {1,2}, {2,1}, {3}}

Define S(i, j) as the set of sets of numbers (1 to 3) that up to i, where j is the first number.

So S(i) = the union of S(i,1), S(1,2), and S(i,3)
S(i,1) = Stick a 1 in front of all sets in S(i-1)
S(i,2) = Stick a 2 in front of all sets in S(i-2)
S(i,3) = Stick a 3 in front of all sets in S(i-3).

You can easily change things so you stick a 1, 2, or 3 in the BACK of the list rather than the FRONT, and that might be helpful. Use linked lists or vectors, I would imagine.