Thread: what is the best method of tracing this code on paper..

  1. #1
    Banned
    Join Date
    Oct 2008
    Posts
    1,535

    what is the best method of tracing this code on paper..

    it has loop one inside the other
    which calls recursive of itself
    many parameters.

    its a nightmare to get the output on your own by pen and paper

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
     
    int what1(int **arr, int m, int n); 
    int what2 (int **arr, int row, int col, int m, int n);
    int main()
    {
    	int ** arr=(int**)malloc(6*sizeof(int*));
    	 
    
    	*arr = malloc(5*sizeof(int));
        *(arr+1) = malloc(5*sizeof(int));
        *(arr+2) = malloc(5*sizeof(int));
        *(arr+3) = malloc(5*sizeof(int));
        *(arr+4) = malloc(5*sizeof(int));
        *(arr+5) = malloc(5*sizeof(int));
    
    	arr[0][0]=0;
    	arr[0][1]=1;
    	arr[0][2]=1;
    	arr[0][3]=0;
    	arr[0][4]=1;
    	
        arr[1][0]=0;
    	arr[1][1]=0;
    	arr[1][2]=1;
    	arr[1][3]=0;
    	arr[1][4]=0;
    
    	 arr[2][0]=0;
    	arr[2][1]=0;
    	arr[2][2]=1;
    	arr[2][3]=1;
    	arr[2][4]=1;
    
     arr[3][0]=0;
    	arr[3][1]=1;
    	arr[3][2]=0;
    	arr[3][3]=0;
    	arr[3][4]=0;
    
     arr[4][0]=1;
    	arr[4][1]=0;
    	arr[4][2]=0;
    	arr[4][3]=1;
    	arr[4][4]=1;
    
     arr[5][0]=1;
    	arr[5][1]=0;
    	arr[5][2]=1;
    	arr[5][3]=1;
    	arr[5][4]=0;
    
    what1(arr,6,5) ;
    	return 0;
    }
    
    int what1(int **arr, int m, int n){
    int i, j, tmp, stam=0;
    
    for(i=0; i<m; i++)
    for(j=0; j<n; j++){
       tmp = what2(arr,i,j,m,n);
       if (tmp>stam) 
             stam = tmp;
    }
    return stam;
    }
    
    int what2 (int **arr, int row, int col, int m, int n){
    int i,j,tmp, stam=0;
    
    if (row < 0 || row >= m || col < 0 || col >= n) return 0;
    if (arr[row][col] == 0) return 0;
     
    
    arr[row][col] = 0;
    for(i=-1; i<2; i++)
    	for(j=-1; j<2; j++){
    		if(!i && !j) continue;
    tmp = 1 + what2(arr, row+i, col+j, m, n);	
    if (tmp > stam)  stam = tmp;
    	}
    arr[row][col] = 1;
    
    return stam;
    }

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Why exactly would I want to write that out on paper?


    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    because i am asked to do that?

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Grab a pen and paper, and draw it out then. If you're supposed to do it on pen and paper, then do so. I'm not sure why you're really asking the question.


    Quzah.
    Hope is the first step on the road to disappointment.

  5. #5
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    603
    What you need to do is to break this down in its most simplest form. You know that you are allocating memory for a 6 x 5 array...right? So then you are needing to populate data into each of these int's that this matrix holds. This is accomplished with your for loops in your non-recursive call to your what1(). This function in tow does call the recursive function for what2().

    1. Analyze what your for loops are trying to do.

    2. Inspect your conditional statements, what constraints are they placing on the data?

    3. Start by tracing the logic and writing down some pseudo code of this.

    4. You may need to review recursive calls and how they place data on the stack...FILO

  6. #6
    Banned ಠ_ಠ's Avatar
    Join Date
    Mar 2009
    Posts
    687
    use a pencil
    ╔╗╔══╦╗
    ║║║╔╗║║
    ║╚╣╚╝║╚╗
    ╚═╩══╩═╝

  7. #7
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    "What does it look like what1() does? "
    it find the maximal member of all what what2() returns.

    "What does it look like what2() does?"
    it put 0 in the given cell
    then i runs threw the close surrounding of the given cell
    and does some recursive operation
    and finds the maximal

    Code:
           if(!i && !j) continue;
    tmp = 1 + what2(arr, row+i, col+j, m, n);   
    if (tmp > stam)  stam = tmp;
      
    return stam;
    "Can you break what2() into smaller, easier to understand pieces? "
    Code:
    if (row < 0 || row >= m || col < 0 || col >= n) return 0;
    if (arr[row][col] == 0) return 0;
    this is the end conditions

    Code:
    arr[row][col] = 0;
    for(i=-1; i<2; i++)
       for(j=-1; j<2; j++){
          if(!i && !j) continue;
    tmp = 1 + what2(arr, row+i, col+j, m, n);
    it puts 0 into the original cell,and checks the surrounding of the cell
    and does some recursive operation.

    Code:
    if (tmp > stam)  stam = tmp;
       }
    arr[row][col] = 1;
    
    return stam;
    then we find the biggest tmp
    put 1 in the original cell and return the biggest tmp.

    "In what cases does it return 0? In what cases does it return nonzero?"
    it returns 0 if the given cell is zero and when the indexes go beyond the array sizes.

    so you whould just go like a debugger ??
    or do some tree diagram??

    the debugger method is too long i cant see how to make shortcuts in this proccess using these answered questions :
    Code:
    what1(arr,6,5) 
      |for(0<6)
      |for(0<5){
      |tmp = what2(arr,0,0,6,5);   //temp=0;
                   |if (arr[row][col] == 0) return 0;
    etc..
    }
    till n=4 and m=5 which is 30 times writing the proccess i did
    and this the short return
    there could be recursive calles to what2 itself
    and all that for 30 times..

    how to make shortcuts
    ??

  8. #8
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    I haven't been to school but am surprised to witness that you guys do not have at least one normalized method for doing this stuff. Use a pencil indeed! I think you should carve your answer into stone and coming running down a mountain with it to reveal the unique nature of your revelations! There should be a system.

    But seriously, as I tried to suggest last time you asked this question, remember that a recursive function ALWAYS MUST have a finalizing case, where it returns an actual number or whatever (in the OP, it's 1+0) and not another call to itself. It is much easier to start with this final case and work backward than it is to start at the beginning and try to "keep count" or something (because really, the final case is what will happen "first", then the returns cascade back to the initial call).
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  9. #9
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    what is the final case here?

  10. #10
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by transgalactic2 View Post
    what is the final case here?
    Okay, I really DO NOT want to work this out on paper, so don't expect too much BUT I would say it is 0+1 because:
    Code:
    int what2 (int **arr, int row, int col, int m, int n){
    int i,j,tmp, stam=0;
    
    if (row < 0 || row >= m || col < 0 || col >= n) return 0;
    if (arr[row][col] == 0) return 0;
     
    
    arr[row][col] = 0;
    for(i=-1; i<2; i++)
    	for(j=-1; j<2; j++){
    		if(!i && !j) continue;
    tmp = 1 + what2(arr, row+i, col+j, m, n);	
    if (tmp > stam)  stam = tmp;
    	}
    arr[row][col] = 1;
    
    return stam;
    }
    I have not at all tried to figure the meaning of the Magenta part, but I would now guess that m and n are the size limits of the matrix, and that the return value MAY be meaningless except in so far as it controls the progress of the recursion.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  11. #11
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    so you would do this debugging method that i did
    but not actually going to every function call
    ??

    its still 30 general calls at least

  12. #12
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    i cant see how you start solving this?

  13. #13
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by transgalactic2 View Post
    so you would do this debugging method that i did
    but not actually going to every function call
    ??

    its still 30 general calls at least
    Well, if there were a problem and you did run it through a debugger, the order of events would be as I described.

    Can these questions be "trick" in the sense of containing much legitimate (eg. not error producing) but pointless code? Because this one definitely does...

    In fact, I think nothing will be done in the end anyway because:
    Code:
    if (arr[row][col] == 0) return 0;  /* ie, will never change a zero to a 1 */
    [then in effect "else"]
    arr[row][col] = 1;      /* must have been one already! */
    Since those numbers were all either 0 or 1 to start with, I do not think this program actually does anything. But I could be wrong!
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  14. #14
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    regarding this code:
    Code:
    for(i=-1; i<2; i++)
    	for(j=-1; j<2; j++){
    		if(!i && !j) continue;
    tmp = 1 + what2(arr, row+i, col+j, m, n);
    i know that it checks the 8 surrounding cells
    i know that the value of tmp will be at least 8
    i cant what is the role of tmp

    i dont know when what2 will return a value other then 0

    ??

  15. #15
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    It will return a value other than zero if stam becomes other than zero, and since that will happen when this statement is true: if (tmp > stam) stam = tmp; (stam is already zero when we start the function, so any greater value will result in a change). Since tmp is 1 + the result of what2() called again, it will be at least 1.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Newton Raphson method code
    By taebin in forum C Programming
    Replies: 2
    Last Post: 10-17-2004, 02:44 AM
  2. Newton Raphson method code
    By taebin in forum C++ Programming
    Replies: 2
    Last Post: 10-16-2004, 03:07 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Interface Question
    By smog890 in forum C Programming
    Replies: 11
    Last Post: 06-03-2002, 05:06 PM
  5. Replies: 4
    Last Post: 01-16-2002, 12:04 AM