Problem in Algorithm Recursive?
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 3 of 3

Thread: Problem in Algorithm Recursive?

  1. #1
    Join Date
    May 2013
    Posts
    2

    Problem in Algorithm Recursive?

    Hello friends, I have a problem to implement a recursive version of an algorithm that I made, I get different values, I hope you can help me, here are the code so Iterative (OK) and Recursive code form that is not OK.

    The data sets do not give equal:

    The algorithm is given two source and target positions on a board, find the number of paths between them...

    Input Example: 5
    2 3
    4 4
    Output Example:

    5



    I hope its not help that I'm wrong!!!

    Iterative Algorithm ( OK )
    Code:
    #include <iostream>
    #include <stdio.h>
    #include <cmath>
    #include <algorithm>
    #include <string.h>
    #include <vector>
    #include <queue>
    
    using namespace std;
    int n , dp [1000][1000], x, y, xx, yy;
    bool mark [1000][1000];
    
    struct Punto
    {
        int x;
        int y;
    };
    
    Punto inicio, fin , aux;
    queue < Punto > lista;
    int direcciones[3][2] = { {0,1}, {1,0}, {1,1} }; 
    
    void BFS()
    {
        lista.push(inicio);
        dp[ inicio.x ][ inicio.y ] = 1;
        while( !lista.empty() )
        {
            aux = lista.front();
            lista.pop();
            x = aux.x;
            y = aux.y;
            for(int i=0 ; i<3 ; i++) 
            {
                xx = direcciones[i][0]+x;
                yy = direcciones[i][1]+y;
                if( xx>0 && xx <= n && yy > 0 && yy <= n ) 
                {
                    dp[xx][yy] += dp[x][y]; 
                    if(!mark[xx][yy])
                    {
                        mark[xx][yy] = true;
                        aux.x = xx;
                        aux.y = yy;
                        lista.push( aux );
                    }
                }
            }
        }
    }
    
    int main()
    {    
        cin>>n;
        cin>>x>>y;
        inicio.x = x;
        inicio.y = y;
        cin>>x>>y;
        fin.x = x;
        fin.y = y;
        BFS(); 
        cout<< dp[fin.x][fin.y] <<endl;
        system("pause");
        return 0;
    }
    Recursive Algorithm ( not OK )
    Code:
    #include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <algorithm>
    #include <vector>
    #include <cmath>
    #include <queue>
    #include <map>
    #include <iostream>
    #include <string>
    #include <stack>
    using namespace std;
    int n , dp [1000][1000], x, y, xx, yy;
    bool mark [1000][1000];
    
    struct Punto
    {
        int x;
        int y;
    };
    
    Punto inicio, fin , aux;
    queue < Punto > lista;
    int direcciones[3][2] = { {0,1}, {1,0}, {1,1} }; 
    
    void BFS(Punto aux){
    	x=aux.x;
    	y=aux.y;
    	for(int i=0;i<3;i++){
    		xx=direcciones[i][0]+x;
    		yy=direcciones[i][1]+y;
    		if( xx>0 && xx <= n && yy > 0 && yy <= n )
    		{
    			dp[xx][yy] += dp[x][y]; 
    			if(!mark[xx][yy])
    			{
    				mark[xx][yy] = true; 
    				aux.x = xx;
    				aux.y = yy;
    				BFS( aux );
    			}
    		}
    	}
    }
    
    int main()
    {
        cin>>n;
        cin>>x>>y;
        inicio.x = x;
        inicio.y = y;
        cin>>x>>y;
        fin.x = x;
        fin.y = y;
       
        dp[ inicio.x ][ inicio.y ] = 1;
        BFS(inicio);
      
        cout<< dp[fin.x][fin.y] <<endl; 
        system("pause");
        return 0;
    }
    I hope its not help that I'm wrong!!!
    cronos

  2. #2
    Join Date
    Apr 1999
    Posts
    27,426

    Re: Problem in Algorithm Recursive?

    Quote Originally Posted by carburo View Post
    Hello friends, I have a problem to implement a recursive version of an algorithm that I made, I get different values, I hope you can help me, here are the code so Iterative (OK) and Recursive code form that is not OK.
    So what debugging have you done? Where does the recursive function make the wrong decision? What have you discovered by debugging?

    Or are you waiting for a professional or expert programmer to debug your program? (which would be considered cheating if this is some sort of school or homework assignment)

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; May 19th, 2013 at 11:51 PM.

  3. #3
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,335

    Re: Problem in Algorithm Recursive?

    Before writing the code, you have produced program designs for both the iterative and recursive versions - and walked through them on paper to make sure the designs were correct haven't you? So either you have not coded correctly the working design or your design is wrong. When confronted with a problem such as this, it is very important that a proper program design is produced before coding. You just can't start coding without having a proven program design first. Debugging as suggested by Paul in post #2 will either suggest that your design is correct but your coding is wrong - or your design itself is wrong. If its just coding of the design implementation that's wrong, it should be fairly easy to spot with the debugger. However, if debugging indicates that it's the design itself that's wrong, then IMO I would revisit the design and correct that first rather than trying to fix the design problem as part of the code debugging. Once the design is corrected, then re-code from the modified design.
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center