Combinations Help

[BAC Sun]

I need to find all the possible ways to walk up a flight of stairs using a recursive function. Each step is allowed to be large, or small, with a large step traveling up 2 stairs at once, and a small step traveling up a single stair.

I have the user input steps in main, then pass that number as x.

For instance if a staircase of three steps can be climbed in three different ways: via three small strides or one small stride followed by one large stride or one large followed by one small.

BUT! My code doesn't allow for order, so the latter two examples get counted as a single possibility. Any help on how to adjust my code to find the correct answer?

 int CountWays(int x, int largestIndex){
	int stepSize[] = { 1, 2 };
	while (stepSize[largestIndex] > x) largestIndex--;
	if (x == 0 || largestIndex == 0) return 1;

	int numWays = 0;
	int numSteps = 0;

	while (numSteps <= x / stepSize[largestIndex]){
		int amountLeft;
		amountLeft = x - numSteps * stepSize[largestIndex];

		numWays = numWays + CountWays(amountLeft, largestIndex - 1);

		numSteps++;
	}

[dhayden]

I think you're making this more complicated than it is. When solving a recursive function, ask youself:
1. What is the base case of the recursion?
2. How can I solve it recursively?

In this case, the base case is when there are only 0 or 1 stairs left. There is exactly 1 way to climb a stair case with 0 or 1 stairs.

Now how about the recursive solution? Well that's easy: To climb a staircase with 10 steps, you can start with 1 step, leaving 9, or you can start with 2 steps, leaving 8. So the total number of ways to climb 10 steps = (number of ways to climb 8 steps) + (number of ways to climb 9 steps). Using this algorithm, I got the following results for stair cases with 0 to 10 steps:

Steps   #ways
0       1
1       1
2       2
3       3
4       5
5       8
6       13
7       21
8       34
9       55
10      89

See if you can code the algorithm. Use my results to check your own.

[BAC Sun]

Thanks for the help. I was able to get it working properly! I couldn't think of any way other than to modify the MakeChange() function in my book, but your verbage pushed me onto the right track.

Also, Fibonacci.

[anup30]

@dhayden, 0 steps has 0 ways. (for 1 way passenger have to give a step of length 0, while he can only give of length 1 or 2.)

[dhayden]

That's a good point anup30. I think my code was:

int countSteps(unsigned steps)
{
  if (steps<=1) return 1;
  return countSteps(steps-1) + countSteps(steps-2);
}

Doing it properly it's:

int countSteps(unsigned steps)
{
  switch(steps) {
  case 0: return 0;
  case 1: // fallthrough
  case 2: return 1;
  default: return countSteps(steps-1) + countSteps(steps-2);
}

[anup30]

now 10 -> 55
entire result column downs 1 row!

[anup30]

#include <iostream>
using namespace std;

int g=0;
void func(int n, int p=0){
	if(n<1) return;
	if(n==p) {g++; return; }		
	if(n<p) return;		
	func(n, p+1);	
	func(n, p+2);
}

int main(){	
freopen("out.txt","w",stdout);
	for(int i=-5; i<=10; i++){	
		g=0;
		func(i);
		cout << i << " " << g << "\n";
	}
	
return 0;
}

output:

-5 0
-4 0
-3 0
-2 0
-1 0
0 0
1 1
2 2
3 3
4 5
5 8
6 13
7 21
8 34
9 55
10 89

can it be done without global variable?

[dhayden]

can it be done without global variable?

The function should return the number of steps

#include<iostream>

int countSteps(unsigned steps)
{
    switch(steps) {
    case 0: return 0;
    case 1: return 1;
    case 2: return 2;
    default: return countSteps(steps-1) + countSteps(steps-2);
    }
}

int
main()
{
    std::cout << "stairs\ttotal steps\n";
    for (unsigned i = 0; i <= 10; ++i) {
        std::cout << i << '\t' << countSteps(i) << '\n';
    }
}

$ ./foo
stairs  total steps
0       0
1       1
2       2
3       3
4       5
5       8
6       13
7       21
8       34
9       55
10      89