WaytoSteps

[ashish]

One boy has to climb steps. He can climb 1 or 2 steps at a time. Write
a function that will returns number of way a boy can climb the steps.
Int WaytoSteps(int n)

(eg:- suppose number of steps is n=4 ,the function will return 5 (one-
one-one-one ,one-one-two, one-two-one-,two-one-one, two-two)

[Ajinkya]

I am working on the code...
My logic is :

1.The possible combinations of 2 & 1 will be found which include 0
nos. of 2s 1 no. of
2s ...etc.

2.On getting the possible combinations we have to calculate the
permutations of each
of the combination obtained.

What do you all think?

Ciao,
Ajinkya.

[Amaj Nash (Suhas)]

#include <stdio.h>
#include <conio.h>

int main()
{
int TotalSteps=0,NoOfTwoSteps,NoOfOneSteps,TotalWays=1;
int i;

printf ("\nPlease enter the number of steps: ");
scanf ("%d",&TotalSteps);

NoOfTwoSteps=TotalSteps/2;

for (i=1;i<=NoOfTwoSteps;i++)
{
int Factorial1,Factorial2,Factorial3;
int TotalStep,j;
NoOfOneSteps = TotalSteps - i * 2;

Factorial1=Factorial2=Factorial3=1;

for (j=2;j<=NoOfOneSteps+i;j++)
Factorial1*=j;

for (j=2;j<=NoOfOneSteps;j++)
Factorial2*=j;

for (j=2;j<=i;j++)
Factorial3*=j;

TotalStep = Factorial1/(Factorial2*Factorial3);
TotalWays+=TotalStep;
}

printf("\nTotal Ways are: %d",TotalWays);

getch();
return 0;
}

[khashya]

i think ur solution is pretty inefficient in time
there is a way for such problems in combinatories
our problem is similar to find no. of integer solutions to x+2y=4
and there is a general formula for it in combinatories which i dont
remember now.
if anybody find it or remember it plz post it

[nico_heinze]

I don't know the formula that Khashya mentioned, but IMO the easiest
way to dramatically improve the runtime behaviour of this algorithm is
to set up an array of long values containing the factorials. You set
up this array at the beginning of main(), and later on you simply
retrieve the factorials from that array.
What do you think?

Regards,
Nico

[ajinkya kale]

Please illustrate a bit on your solution....an example if possible.

[nico_heinze]

On Apr 18, 12:11 pm, "ajinkya kale" <kaleajin...@gmail.com> wrote:
> Please illustrate a bit on your solution....an example if possible.

No problem, here's the largest portion of the code:

#define MAX_FCTR_IND 13
/* Factorial(13) is beyond 2^32, so using 32-bit integers the array
can at most hold indexes 0 to 12. */

int main()
{
int TotalSteps=0,NoOfTwoSteps,NoOfOneSteps,TotalWays=1;
int i;

long factorials [MAX_FCTR_IND]; /* more don't fit into 32-bit
integer range anyway. */

factorials [0] = 1;
for (i = 1; i < MAX_FCTR_IND; i++)
factorials [i] = factorials [i - 1];

printf ("\nPlease enter the number of steps: ");
scanf ("%d",&TotalSteps);

NoOfTwoSteps=TotalSteps/2;

for (i=1;i<=NoOfTwoSteps;i++)
{
int Factorial1,Factorial2,Factorial3;
int TotalStep,j;
NoOfOneSteps = TotalSteps - i * 2;

Factorial1 = factorials [NoOfOneSteps];
Factorial2 = factorials [NoOfOneSteps];
Factorial3 = factorials [i];

TotalStep = Factorial1/(Factorial2*Factorial3);
TotalWays+=TotalStep;
}

printf("\nTotal Ways are: %d",TotalWays);

getch();
return 0;

} /* main() */

Regards,
Nico

[Ajinkya]

Nico you got it wrong there....
Your code just finds the possible combinations in which the no of
steps can be split.

eg: for n=5 your code gives total no of ways = 3
ie 1+1+1+1+1,
1+1+1+2,
1+2+2.

Now we have to find the permutaions of each of the above
combination
ie 11111,1112, 1211, 1121, 2111, 122, 212, 221

Cheers,
Ajinkya.

[ajinkya kale]

Please reply in the same thread where the ques was posted so that it makes it readable and easy for new members to read earlier posts and the solutions.

 

Ajinkya.

 

On 4/29/07, Chepa <chevi...@gmail.com> wrote:

the problem is quite easy...

consider a function F(n) which gives the number of ways to climb 'n'
steps.
now, the boy can go to the 'n'th step either from (n-1)th step, by
taking one step up.. or from (n-2)th step, by taking 2 steps up..
because only 2 choices are available at any step.

in other words, number of ways to reach nth step is nothing but the
summation of number of ways to reach (n-1)th step and the number of
ways to reach (n-2)th step..

mathematically,

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

and, this is nothing but the Fibonacci series :) .. so guys, the
simple formula to find 'i'th fibonacci number which we can use here...

#include<stdio.h>
#include<math.h>

int WaystoSteps(int n){
float ph,phb;
int nWays;
ph=(1+sqrt(5))/2;
phb=(1-sqrt(5))/2;
nWays=(int)((pow(ph,n+1)-pow(phb,n+1))/sqrt(5));
return nWays;
}

I have written all the intermidiate variables so that it will be more
clear... :)

[Chepa]

[muhaha]

chepa .. that is ok ... but you are supposed to PRINT all the
combinations:)

[Chepa]

huh ? .. did I misinterpret the prob stmt... I don't think so.. Ashish
has stated that we should write a function to find the number of ways
and NOT the actual combinations...

> > clear... :)- Hide quoted text -
>
> - Show quoted text -

[mailt...@gmail.com]

arey wht i think is recursive logic will b vry easy...

jst hv a luk thru d followin logic...

void print(int n) {
if(n > 0) {
if(1 == n) {
pf("1");
return;
}
else {
if(n-1 >= 0) {
pf("1");
print(n-1);
}
if(n-2 >= 0) {
pf("2");
print(n-2);
}
}
}
}

howz it?

[Chepa]

nope... recursion will always take more time than the simple
mathematical formula which 've stated above...
and 'm still not getting why U R printing "1"s and "2"s ... it is
clearly stated in the problem statement that we are supposed to find
out the number of ways and NOT to print those cobinations..

[muhaha]

@chepa
SUPPOSE it is said that print the combinations .... assume that its
a new problem:P !!

@manish (right?)
well ... i think this will just print garbled 1s and 2s .... it won't
actually LIST them .... right?
what I mean is ... it will print smthing like (havn't tested it
though!!)
1 2 1 2 1 2 1 2 1 1 1 1 1 2 1 2 1 1 1 1 1 2 1 2 1 2 2 2 .........

[Chepa]

@muhaha...
if it's a new prob.. fine.. here's the solution...

#include<stdio.h>
#include<conio.h>
#include<string.h>

typedef struct Ways{
char **dt;
int N;
}Ways;

void Copy(Ways *a, Ways *b){
int j;

for(j=0;j<a->N;j++)
free(a->dt[j]);
free(a->dt);

a->dt=(char **)malloc(sizeof(char *)*(b->N));
for(j=0;j<b->N;j++){
a->dt[j]=(char *)malloc(sizeof(char)*(strlen(b->dt[j])+1));
strcpy(a->dt[j],b->dt[j]);
}
a->N=b->N;
}

int main(void){
int a,i,j,k;
Ways n1,n2,nn;

clrscr();
scanf("%d",&a);

n1.dt=(char **)malloc(sizeof(char *));
n1.dt[0]=(char *)malloc(sizeof(char));
strcpy(n1.dt[0],"");
n1.N=1;

n2.dt=(char **)malloc(sizeof(char *));
n2.dt[0]=(char *)malloc(2*sizeof(char));
strcpy(n2.dt[0],"1");
n2.N=1;

for(i=0;i<(a-1);i++){
nn.dt=(char **)malloc((n1.N+n2.N)*sizeof(char *));
k=0;
for(j=0;j<n1.N;j++){
nn.dt[k]=(char *)malloc(sizeof(char)*(strlen(n1.dt[j])+3));
strcpy(nn.dt[k],"2 ");
strcat(nn.dt[k],n1.dt[j]);
k++;
}

for(j=0;j<n2.N;j++){
nn.dt[k]=(char *)malloc(sizeof(char)*(strlen(n2.dt[j])+3));
strcpy(nn.dt[k],"1 ");
strcat(nn.dt[k],n2.dt[j]);
k++;
}
nn.N=k;

Copy(&n1,&n2);
Copy(&n2,&nn);

for(j=0;j<nn.N;j++)
free(nn.dt[j]);
free(nn.dt);
}

for(i=0;i<n2.N;i++)
printf("\n%s",n2.dt[i]);

printf("\nNo.of Ways : %d",n2.N);

for(i=0;i<n1.N;i++)
free(n1.dt[i]);
free(n1.dt);

for(i=0;i<n2.N;i++)
free(n2.dt[i]);
free(n2.dt);

return 0;
}

sorry, but the prog is a bit lengthy due to dynamic mem allocation...
The main funda is, to find the no. of ways for 'n'th step, we will
just take one step from each possible way to (n-1)th step.. and, 2
steps from each possible way to (n-2)th step...

> > > howz it?- Hide quoted text -

[happy]

hey, chk out dis...

#include <stdio.h>
#include <conio.h>
#include <alloc.h>

char *buff;

int print(int n) {
static int i, cnt;
int j;
if(n > 0) {
if(n - 1 >= 0) {
buff[i++] = 1;
print(n - 1);
i--;
}
if(n - 2 >= 0) {
buff[i++] = 2;
print(n - 2);
i--;
}
}
else {
for(j = 0; j < i; j++)
printf("%d ", buff[j]);
printf("\n");
cnt++;
}
return cnt;
}

int main() {
int n;

clrscr();
printf("Enter n : ");
scanf("%d", &n);
buff = (char *) malloc(sizeof(char) * n);
n = print(n);
printf("No of ways : %d", n);
getch();
free(buff);

return 0;
}

cheers,
-MANish