Thread: Divide and Conquer: array in the reverse order

  1. #1
    Registered User
    Join Date
    Mar 2004
    Posts
    5

    Divide and Conquer: array in the reverse order

    Hi!

    I'm having a problem with a divide and conquer algorithm. The function dac must return an array in the reverse order. What the function does is splitting the array, and make two recursive calls. We supose the problem known for each of the two halfs, and then, we combine the solution depending on if the array is even or odd.
    Well, a classic divide and conquer problem.

    I'll put the code here. It compiles correctly, but it doesn't work. (1,2,3,4,5,6) array, in the reverse order, according to the executable file is: (6,0,4,3,2,1).

    I'd be grateful if someone helped. Thanks.

    Code:
    #include <stdio.h>
    
    
    void daq (int *v, int begin, int end);
    
    int main()
    {
    	int i,k;     //iterators
    	int *v=(int*)malloc(6*sizeof(int));
    	//int v[6];
    	for (i=0; i<7; i++)
    	{
    	printf(" v[%d]: ", i);
    	scanf("%d", &v[i]);
    	}
            printf("\nThe array is:\n");
    	for (k=0; k<7; k++)
    	{
    	printf("v[%d]= %d ", k, v[k]);
    	}
    	printf("\n");
    	dac(v,0,6);   //first call
    	printf("The array, in the reverse order, is:\n");
    	for (k=0; k<7; k++)
    	{
    	printf("v[%d]= %d ", k, v[k]);
    	}
    	printf("\n");
        free(v);
    	return 0;
    }
    
    
    void dac (int *v, int beg, int enn)
    {
    
    	//base: size==1
    	if (fin==ini);  //don't do anything
    
    
    	else
    	{
    	int mid=(beg+end)/2;
    	int j;
    	dac(v, beg, mid);
    	dac(v, mid+1, end);
    	if (mid%2==0)   //size is even
    	{
    	int g=0;
    	for (j=beg; j<=mid; j++,g++)
    	{
    		int aux=v[j];
    		v[j]=v[g+mid+1];
    		v[g+mid+1]=aux;
    	}
    	}
    
    	else {     //odd
              int h,aux2,g;
    	  g=1;
    	  for (h=beg+1; h<=mid; h++,g++)
    	  {
    	  aux2=v[h];
    	  v[h]=v[mid+g];
    	  v[mid+g]=aux2;
    	  }
    	  int z;
    	  for (z=beg; z<mid; z++)
    	  {
    	  int aux3;
    	  aux3=v[z];
    	  v[z]=v[z+1];
    	  v[z+1]=aux3;
    	  }
    	}
    	}
    
    }

  2. #2
    Registered User
    Join Date
    Mar 2004
    Posts
    5
    I've just realized I made a mistake: line 4, wrote "daq" instead of "dac" (divide and conquer)

    ... and line 34, enn instead of end

  3. #3
    Registered User linuxdude's Avatar
    Join Date
    Mar 2003
    Location
    Louisiana
    Posts
    926
    do you have to call a recursion? Why are you using malloc instead of int v[6];?? where is fin and ini. You also have 2 elses you should use if else. You are also declaring variables in the middle of your program they should all be at the beginning of your function. Besides that I can't really help you with the recursion part I would have to write it myself. They way you did it hurts my head Someone better will figure out what is wrong with it

  4. #4
    Registered User
    Join Date
    Mar 2004
    Posts
    5
    Yes, I forgot to "translate" some names of variables from Spanish to English (my "find and replace" didn't work ).

    I am not very good at C, I prefer C++, and I didn't know I had to declare all the variables at the beginning of the function.

    And I TOTALLY AGREE that it hurts any head

  5. #5
    Registered User
    Join Date
    Mar 2004
    Posts
    5
    I found my mistake. I don't know what the heck I was thinking about, but I used the variable mid to chek if the size was odd or even, which does not make any sense at all.

    I declared a new variable int size=end-beg+1 to check that, and it's done.

    Btw, I don't know why, but Dev compiler obliges you to declare all the variables at the begining of the function, while a gcc compiler on a unix system lets me declare them at any point.

  6. #6
    Registered User
    Join Date
    Mar 2004
    Posts
    12
    Originally posted by Steamer

    Btw, I don't know why, but Dev compiler obliges you to declare all the variables at the begining of the function, while a gcc compiler on a unix system lets me declare them at any point.
    In pure 'C' you have to declare variables in the beginning of a function, but if you use using g++ on a unix system then you are actually calling the c++ compiler and not the C compiler and thus you can declare variables when you need them in the function. (to put it in simple very terms)
    Life is a piece of chocolates

  7. #7
    Registered User
    Join Date
    Dec 2002
    Posts
    19
    Btw, I don't know why, but Dev compiler obliges you to declare all the variables at the begining of the function, while a gcc compiler on a unix system lets me declare them at any point.
    is this correct?
    since ansi C99 standard initializations after expressions are allowed! c89 didn't do that? correct?

    bye
    wudmx

  8. #8
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > since ansi C99 standard initializations after expressions are allowed! c89 didn't do that? correct?
    Yes.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  9. #9
    Registered User
    Join Date
    Mar 2004
    Posts
    12
    So you can declare variables anywhere in a function ?
    Life is a piece of chocolates

  10. #10
    Registered User
    Join Date
    Dec 2002
    Posts
    19
    Originally posted by gautamn
    So you can declare variables anywhere in a function ?
    yes, if you don't use it before the declaration!

  11. #11
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Originally posted by wudmx
    yes, if you don't use it before the declaration!
    I'm not sure your meaning. Naturally you have to declare a variable before you can use it. However, you may be referring to variable names. In which case, this is legal:
    Code:
    {
        int foo = 1;
        {
            int foo = 2;
            {
                int foo = 3;
                printf("foo is %d\n", foo );
            }
            printf("foo is %d\n", foo );
        }
        printf("foo is %d\n", foo );
    }
    Quzah.
    Hope is the first step on the road to disappointment.

  12. #12
    Registered User
    Join Date
    Mar 2004
    Posts
    12
    My question was more towards this type of declaration.

    Code:
    int func()
    {
        int a, b, c, d;
         
        // do something
        a = 5;
        d = 10;
    
         int e = d;
    }
    Life is a piece of chocolates

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. divide and conquer
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 06-13-2002, 09:52 AM