Pyramid program

Question

One person is standing above the pyramid having 100 steps.He can take 1 or 2 steps at a time to come down.So there are how many possible ways he can come down? I want to solve this problemin c programming language Please Help to solve this problem

Answer 1

Look up Fibonacci.

Answer 2

This is a simple one; all you have to do is analyze the problem for 1 step, 2 and then with more, and check for a rule.

1 |
2 | |        (1+1 or 2)
3 | | |      (1+1+1, 1+2, 2+1)
5 | | | |    (1+1+1+1, 1+2+1, 2+1+1, 1+1+2, 2+2+1)
8 | | | | |  (5 ways to walk to the 4th step + 1, and 3 ways to walk to the 3rd step + 2)

Let S(n) be the solution to the problem with n steps; then S(n) = S(n-1) + S(n-2)

The nth step of the problem has the answer of fib(n+2) (+2 comes from beginning with the second 1 in the fibonacci sequence)

The answer for 100 is here

Answer 3

Alternatively, start with a sequence of 100 1s, i.e. 111...11. Now, try to preserve the sum you have to replace two 1s with a 2. There is 99 places you can insert this 2, i.e. 99 occurrences of the string "11" in the original string. Now for each of these, you have to insert one more 2. How many ways can you that in*? Multiply by 99. Repeat until you have replaced the entire string with 2s.

• Hint- not all of these 99 strings will contain the "11" you are looking for

Answer 4

Below is a naive C implementation, just for the illustration. Don't use it, even if the implementation is very simple and lightweight, it is way too slow and will take forever to run (algorithmic complexity).

When confronted with such problems you should not go for whatever programming language, it's irrelevant. Use your brain to find a suitable method (and maybe some math). Other posters proposed fine possible methods.

EDIT: and also if it could stop before the end of the universe the answer wouldn't be right as it does not fit inside an int. If you really want to implement this using C you'll have to use some bigint library (or manage long overlow by yourself).

#include <stdio.h>

int count = 0;

void f(int stairs){
   // finished ?
    if (stairs <= 0){
        // avoid solutions going one step into earth 
        if (stairs == 0){
            count++;
        }
        return;
    }
    // try adding one step
    f(stairs-1);
    // try adding two steps
    f(stairs-2);
}

int main(){
    f(100);
    printf("number of possible paths is %d\n", count);
}

Answer 5

Imagine you are on the 100th step. You could only have got to it from the 99th step (by taking one step) or the 98th step (by taking two steps.

The number of ways to get to the 100th step is therefore the sum of the number of ways to get to the 99th step and the number of ways to get to the 98th step.

To generalise:

number_of_ways_to_get_to_step(n) = number_of_ways_to_get_to_step(n - 1) + number_of_ways_to_get_to_step(n - 2)

Also:

number_of_ways_to_get_to_step(1) = 1 
number_of_ways_to_get_to_step(2) = 2    (two steps of one or one step of two).

That's all you need to solve the question, but there are still two issues:

1. the naive implementation will take a very long time to compute

2. using either 32 bit or 64 bit integers, the answer is too big to compute.