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
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); } void addJumpToSolution(solution_t *solution, int jump) { 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; } addJumpToSolution(newSolution, jump); if (newSolution->steps < totalSteps) { solutionTable = getSolutionTable(solutionTable, solutionCounter, newSolution, totalSteps); } else { solutionTable = addSolutionToTable(solutionTable, solutionCounter, newSolution); 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; }