# coding help for this problem

Discussion in 'C' started by sumedh yadav, Sep 3, 2012.

Joined:
Aug 18, 2012
Messages:
17
0
Trophy Points:
0
Two frogs are sitting at the bottom of a flight of 10 steps and debating in how many ways then can jump up the stairs. They can jump one, two or three steps at once. For example, they can cover the 10 steps by jumping (3,3,3,1) or (2,3,2,1,2) or other suitable combinations of steps. Their mathematics is not very strong and they approach you for help in order to find out the total number of possibilities they have to reach the top. Note that the order of the steps is important here, i.e., (3,3,3,1) is treated distinct from (1,3,3,3) for example. Write a program that takes input the number of steps of flight to be covered.
Output:
Number of total ways to reach to the top in the first line
followed by all the solutions (one solution in one line).

INPUT
Number of steps to be covered: 4
OUTPUT
Total number of solutions: 7
1 1 1 1
1 2 1
1 1 2
2 1 1
1 3
3 1
2 2

2. ### louies89New Member

Joined:
Oct 4, 2012
Messages:
4
0
Trophy Points:
0
This is a very complex problem man............

3. ### louies89New Member

Joined:
Oct 4, 2012
Messages:
4
0
Trophy Points:
0

4. ### DRKNew Member

Joined:
Apr 13, 2012
Messages:
44
3
Trophy Points:
0
Code:
```#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct solution_s
{
int *jumpTable;
int jumpCounter;
int steps;
} solution_t;

solution_t *createSolution(void)
{
solution_t *solution = malloc(sizeof(solution_t));
solution->jumpTable = NULL;
solution->jumpCounter = 0;
solution->steps = 0;
return solution;
}

solution_t *copySolution(const solution_t *solution)
{
solution_t *newSolution = createSolution();
if (solution != NULL)
{
newSolution->jumpCounter = solution->jumpCounter;
newSolution->steps = solution->steps;
if (newSolution->jumpCounter > 0)
{
newSolution->jumpTable = malloc(newSolution->jumpCounter * sizeof(int));
memcpy(newSolution->jumpTable, solution->jumpTable, newSolution->jumpCounter * sizeof(int));
}
}
return newSolution;
}

void showSolution(const solution_t *solution)
{
int i;
for (i = 0; i < solution->jumpCounter; ++i)
{
if (i > 0)
{
printf(" ");
}
printf("%d", solution->jumpTable[i]);
}
puts("");
}

void destroySolution(solution_t *solution)
{
if (solution->jumpTable != NULL)
{
free(solution->jumpTable);
}
free(solution);
}

{
solution->jumpTable = realloc(solution->jumpTable, (solution->jumpCounter + 1) * sizeof(int));
solution->jumpTable[solution->jumpCounter] = jump;
solution->jumpCounter += 1;
solution->steps += jump;
}

solution_t **addSolutionToTable(solution_t **solutionTable, int *solutionCounter, solution_t *solution)
{
solutionTable = realloc(solutionTable, (*solutionCounter + 1) * sizeof(solution_t *));
solutionTable[*solutionCounter] = solution;
*solutionCounter += 1;
return solutionTable;
}

solution_t **getSolutionTable(solution_t **solutionTable, int *solutionCounter, solution_t *solution, int totalSteps)
{
solution_t *newSolution = NULL;
int jump, created = 0;
if (solution == NULL)
{
solution = createSolution();
created = 1;
}
for (jump = 1; jump <= 3 && solution->steps + jump <= totalSteps; ++jump)
{
if (jump > 1 || newSolution == NULL)
{
newSolution = copySolution(solution);
created = 1;
}
if (newSolution->steps < totalSteps)
{
solutionTable = getSolutionTable(solutionTable, solutionCounter, newSolution, totalSteps);
}
else
{
newSolution = NULL;
}
}
if (created == 1)
{
destroySolution(solution);
}
return solutionTable;
}

int main(int argc, char **argv)
{
solution_t **solutionTable = NULL;
int i = 0, totalSteps = 0, solutionCounter = 0;
printf("Number of steps to be covered: ");
scanf("%d", &totalSteps);
if (totalSteps > 0)
{
solutionTable = getSolutionTable(NULL, &solutionCounter, NULL, totalSteps);
printf("Total number of solutions: %d\n", solutionCounter);
for (i = 0; i < solutionCounter; ++i)
{
showSolution(solutionTable[i]);
destroySolution(solutionTable[i]);
}
free(solutionTable);
}
return 0;
}```