Robot program

Sup am a beginner in progrramming and i came a cross this question. Give me an idea of going about it

[code]A robot that has beenprogrammed by a student can take steps of 1 meter or 2 meters. write a pseudocode to calculate the number of ways that this robot can walk N meters.
For example
Distance Sequenceof steps Number o fways to walk
1 1 1
2 1,1 and 2 2
3 1,1,1 or 1,2 or 2,1 3
[/code]

Comments

  • Well, you could use a programming method called "backtracking" for generating some coefficients for the steps starting with 0. Lets say k1 is the coefficient for the number of steps of size 1 and k2 for the number of steps of size 2, and if (k1+2*k2) = N then you have a solution. For your problem you can use only two nested for-s like this:
    [code]
    for( k1=0;k1<=N;++k1)
    for(k2=0;k2<=N;++k2)
    if......
    [/code]
    But if you are asked to solve the same problem for 20 types of steps , you need to use backtraking properlly, the recursive or the iterative version.
    If you are asked to compute only one solution you could use the method called "dynamic progaramming"(something similar to the knapsack problem) which is faster than the first method.
Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

In this Discussion