CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 3 of 3
  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.
    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
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    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. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++23 Compiler: Microsoft VS2022 (17.6.5)

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