1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

coding help for this problem

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

  1. sumedh yadav

    sumedh yadav New Member

    Joined:
    Aug 18, 2012
    Messages:
    17
    Likes Received:
    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. louies89

    louies89 New Member

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

    louies89 New Member

    Joined:
    Oct 4, 2012
    Messages:
    4
    Likes Received:
    0
    Trophy Points:
    0
    if you got the answer ........... please share it.........
     
  4. DRK

    DRK New Member

    Joined:
    Apr 13, 2012
    Messages:
    44
    Likes Received:
    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);
    }
    
    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;
    }
     

Share This Page