CareerCup

people don't actually cover "why".
Consider F(N) is number of ways to get to the Nth step.
there are only two steps you can get there from: N-1 and N-2
All the ways you can get to the step (N-1) + the number of ways to get to the step N-2 will give you the total number of ways.
F(n) = F(n-1) + F(n-2).
And this looks like Fibonachi sequence.
This can be expanded to 3 ways of stepping leading into more complex problem

It will be f(n) i.e. Fibonacci series....

It will be f(n+1)....(n+1)th fibonacci number..
Check for yourself..
for 1 stair no. of ways = 1 = f(2)
for 2 = 2 = f(3) = f(2) + f(1)
for 3 = 3 = f(4) = f(3) + f(2)
for 4 = 5 = f(5) = f(4) + f(3)
for 5 = 8 = f(6) = f(5) + f(4)
for 6 = 13 =f(7) = f(6) + f(5)
:
:
for n = f(n+1)

so in this way you can do and find out...

it will be the sum of this series
1+C(n-1,1)+C(n-2,2)+C(n-3,3)+......C(n-x,x) where x<n/2;
exaplanation:
there is 1 way when only one step is taken each time for n times to climb up.
next we take a double(2) step and all other single(1) steps, in dis case total number of times i need to take steps will be n-1.
do this recusively increasing the number of double steps taken and arraging those.

t will be the sum of this series
1+C(n-1,1)+C(n-2,2)+C(n-3,3)+......C(n-x,x) where x<n/2;
exaplanation:
there is 1 way when only one step is taken each time for n times to climb up.
next we take a double(2) step and all other single(1) steps, in dis case total number of times i need to take steps will be n-1.
do this recusively increasing the number of double steps taken and arraging those.

N'th Fibonacci number: F(n) = [phi ^ n / sqrt(5) + 1/2] where [a] = floor of a and phi is the golden ratio:(1+sqrt(5))/2.
The problem resumes to calculate a^n. This can be done in O(log n) if you use the formula: a^n = a * a^(n/2) * a^(n/2) if n is odd; a^n = a^(n/2) * a^(n/2) - if n is even.

I’m guessing that all my blog readers know what the Fibonacci sequence is. For the uninitiated, it is:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34…. ad infinitum.

Each number is the sum of the preceding 2 numbers. That is,

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

where,
F(0) = 0
F(1) = 1

void main()
{
int n,k;
printf("Enter no. of stairs: ");
scanf("%d",&n);
k=fibo(n);
}

int fibo(int n)
{
if(n==0)
return 0;

if (n==1)
return 1;
else
return(fibo(n-1)+fibo(n-2));


}

I don't think Fibo is the correct answer. You're assuming that a series of 3 steps 1,1,1 is different from another series 1,1,1. Since if you have to climb 4 stairs using a combination of 1 and 2, i think there's 7 ways.
1,1,1,1,1
1,2,2
2,1,2
2,2,1
2,1,1,1
1,1,1,2
1,1,2,1

Am I missing something?

The possible answer to this question is:
There is only one case for climbing stairs up taking 1 step at a time. After that we can take any number of 2 steps from 1 to n/2.
So, 1+ C(n/2,1)+C(n/2,2)+...........+ C(n/2,n/2) = 1+ (2^(n/2)-1)= 2^(n/2)

The possible answer to this question is:
There is only one case for climbing stairs up taking 1 step at a time. After that we can take any number of 2 steps from 1 to n/2.
So, 1+ C(n/2,1)+C(n/2,2)+...........+ C(n/2,n/2) = 1+ (2^(n/2)-1)= 2^(n/2)

//i think below cide gives no of ways for given n steps;



#include<stdio.h>
int stair(int n)
{
if(n==0)
{

return 0;
}
else if(n==1)
{
return 1;
}

else
{
return(stair(n-2)+stair(n-1)+2);
}
}
main()
{
int n;
scanf(" %d",&n);

printf("\nno of ways to climb up is %d",stair(n));
}

It is easier to refer to the how may steps are being skipped.
For example: 1 step at the time is equivalent to 0 skips over steps.
2 steps at a time is equivalent to 1 skip over steps.
3 steps is 2 skips ... and so on and so forth.
How many options are there for 0 skips = 1 or C(0, n-1) = 1
How many options available for 1 skip out of (n-1) = n-1 or C(1,n-1)=n-1
Total ways either 0 or 1 skips (1 step or 2 steps) = n

For all the possibilities = C(0,n-1)+C(1,n-1)+C(2,n-1)+...+ C(n-1,n-1) = 2 ^ (n-1)

Here is what I think...

Original Problem: Person can take only 1 or 2 steps

At every step, you can take either one step or you can take two steps.
So two possibilities at each step.And there are n steps.

So f(1) +f(2) ....+ f(n) = 2 + 2 + 2 ..... + 2 = 2n

Modified Problem: Person can take step from 1 to m at any time

So f(1) +f(2) ....+ f(n) = m + m + m ..... + m = mn

This means mn is the upper bound function.

I do not think its Fibo series.

the answer to that is the formula
2^n-1 as u see if there are 6 stairs there will be 2^6-1=2^5=32

i think fib(n) is not exact since fib(2)=1 but no of ways for 2 steps is 2

It is essentially the Fibonacci sequence, i.e. for 'n' steps the number of ways of the top with either 1 or 2 steps would be equal to fib(n+1), considering fib(0) = 0, and fib(1) = 1.
NOTE: fib(n) = fib(n-1) + fib(n-2)
ex.
n = 1 #1 i.e 1 step
n = 2 #2 i.e. 1+1 steps, and 2-step
n = 3 #3 i.e. 1+1+1 steps, 2+1 steps, 1+2 steps
.
.
.

int sum1(list<int> steps)
{
	int sum = 0;
	for (list<int>::iterator it=steps.begin();it!=steps.end();it++)
	{
		sum+=*it;
	}
	return sum;
}
void permuteSteps(int n, list<int> steps)
{
	int sum = 0;
	sum=sum1(steps);
    cout << "Call for n=" << n<< " ; ";
	cout << "sum: " << sum << endl;
	if ( sum == n)
	{
		for (list<int>::iterator it=steps.begin();it!=steps.end();it++)
		{
			cout << *it <<" ";
		}
		cout << endl;
		return;
	}
	else if (sum > n) return;

	for (int i=1;i<=3;i++)
	{
		steps.push_back(i);
		permuteSteps(n, steps);
		steps.pop_back();
	}
}

int main()
{
    int ar1[]={2,12,14,34,36};
    int ar2[]={1,3,6,7,15,74};

    list<int> steps;
    permuteSteps(5, steps);
	cout << "\n";
	return 0;
}

How do u make it for n steps so that it is constrained to move only 1,2 or 3 steps at a time...
I tried making it using brute programming... but it goes into a very long loop and doesnot return any value except for zero stairs..

How do u make it for n steps so that it is constrained to move only 1,2 or 3 steps at a time...
I tried making it using brute programming... but it goes into a very long loop and doesnot return any value except for zero stairs..

#include<stdio.h>
using namespace std;


int multiply( int mat1[2][2], int mat2[2][2] )
{
	int i, j, k, l;
	i = mat1[0][0] * mat2[0][0] + mat1[0][1] * mat2[1][0];
	j = mat1[0][0] * mat2[0][1] + mat1[0][1] * mat2[1][1];
	k = mat1[1][0] * mat2[0][0] + mat1[1][1] * mat2[1][0];
	l = mat1[1][0] * mat2[0][1] + mat1[1][1] * mat2[1][1];
	
	mat1[0][0] = i;
	mat1[0][1] = j;
	mat1[1][0] = k;
	mat1[1][1] = l;
	return 0;
}

int power( int F[2][2], int n )
{
	if( n <= 1 )
		return 0;
	power( F, n/2 );
	multiply( F, F );
	if( n % 2 == 1 )
	{
		int M[2][2] = { {1, 1},{1, 0} };
		multiply( F, M );
	}
	return 0;
}

int noOfWays( int n )
{
	if( n <= 1 )
		return 0;
	int F[2][2] = { {1, 1},{1, 0} };
	power( F, n );
	return F[0][0];
}

int main()
{
	int n;
	scanf("%d", &n );
	if( n == 0 || n ==1 )
		printf("No. of Ways: %d", n );
	else
		printf("No. of Ways: %d\n", noOfWays( n ));	
	return 0;
}

In python

# Given n stairs, how many number of ways can you climb if u use either 1 or 2 at a time?

# fib is f(n) = f(n-1) + f(n-2)
def stairCombInOneOrTwoStepsAtATime(steps):
	if steps == 0:
		return 0

	# init our n-1 and n-2 vars
	prev = 1
	curr = 1

	# iterate steps, setting current as the sum of the previous 2 vars
	for x in range(1, steps):
		temp = curr
		curr = curr + prev
		prev = temp

	return curr

for y in range(30):
	print "%d:%d" % (y, stairCombInOneOrTwoStepsAtATime(y))

package koustav;

public class Tree
{
  public static void main(String args[])
  {
    System.out.println(printNoWays(6));
  }

  public static int printNoWays(int sum)
  {
    if (sum == 0)
      return 1;
    if (sum < 0)
      return 0;
    return printNoWays(sum - 1) + printNoWays(sum - 2);
  }

  public static void printArray(Object obj)
  {
    Class cls = obj.getClass();
    Object obj1[] = (Object[]) cls.cast(obj);
    if (cls.getComponentType().isArray())
    {
      for (Object obj2: obj1)
      {
        printArray(obj2);
      }
    }
    else
    {
      System.out.print("\n");
      for (int i = 0; i < obj1.length; i++)
      {
        System.out.print(obj1[i]);
      }
    }
  }
}

Seems like complete binary tree , 2+4+8.....2powerN....

Can you please help me understand the logic : When n is reached from (n-2) step and taking a leap of 2 step, why are we not considering that last step (2 step leap)?
ways(n) = [ways (n-1) +1] + [ways(n-2)+1]
I worked out on a paper and the result looks like we shouldn't be using +1. But, can you please explain me the logic of not considering the +1?