CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2
  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,449

    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.
    Don't post on multiple forums. I asked you on the other forum as to what debugging have you done.

    Regards,

    Paul McKenzie

Posting Permissions

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





Click Here to Expand Forum to Full Width

Featured