Click here to Skip to main content
11,705,208 members (56,296 online)
Rate this: bad
good
Please Sign up or sign in to vote.
See more: C++
I want print array A with this form:
F(A)=F(odd)+F(even) if n>1 // “+” means merge
F(A)=A if n==1
For example:
F([1,2,3,4])=F([1,3])+F([2,4])
F([1,3])=F([1])+F([3])=[1]+[3]=[1,3]
F([2,4])=F([2])+F([4])=[2]+[4]=[2,4]
F([1,2,3,4])=F([1,3])+F([2,4])=[1,3]+[2,4]=[1,3,2,4]
Thus I write a recursive function. But my code is correct for max 4 element.
But if enter 5 element is wrong.
For example:
Result of F([1,2,3,4,5]=[1,5,5,2,4] and this wrong . result should be [1,5,3,2,4]
My code is:
void EvenOdd::F(int *a,int n)  // F is in EvenOdd class
  {
	if (n==1)
	{
		cout <<a[n] << " ";
	       return   ;
	}
	else
	{
		if(n%2==0 )
		{
                        CreatOdd(a,odd,n);
			 F(odd,n/2);
			CreatEven(a,even,n);
			 F(even,n/2);
			
		}
		else
		{
			CreatEven(a,even,n);
			 F(even,(n/2)+1);
			CreatOdd(a,odd,n);
			 F(odd,n/2);
		}
	}
}
//*************************************************************************
 void EvenOdd::CreatOdd( int *Aptr,int *oddptr,int n)
{
	int j=1;
	for (int i=1 ;i<=n ; )
	{
		oddptr[j]=Aptr[i];
		j++;
		i=i+2;
	}
}
//***************************************************************************
  void EvenOdd::CreatEven(int *Aptr,int *evenptr,int n)
{
    int j=1;
	for (int i=2 ;i<=n ; )
	{
		evenptr[j]=Aptr[i];
		j++;
		i=i+2;
	}
}
thanks


[edit]code block added[/edit]
Posted 24-Nov-12 23:51pm
homa sh284
Edited 28-Nov-12 22:40pm
v3
Comments
Nelek at 25-Nov-12 5:58am
   
[quote] Result of F([1,2,3,4,5]=[1,5,5,2,4] and this wrong . result should be [1,5,3,2,4] [/quote]

Should not be [1,3,5,2,4] ???
Mohibur Rashid at 25-Nov-12 23:43pm
   
the result should be 1,5,3,2,4. the function is talking about position

F[1,2,3,4,5]=F[1,3,5]+F[2,4]=F[1,5]+F[3]+F[2,4]=F[1]+F[5]+F[3]+F[2]+F[4]
homa sh at 26-Nov-12 10:38am
   
yes I want exactly function print this numbers..
Do you know that where is wrong in my code ?
thanks
Stefan_Lang at 29-Nov-12 4:55am
   
The second and third line in your example don't adhere to the formula you gave initially. This is not a recursive problem at all.
Mohibur Rashid at 29-Nov-12 5:49am
   
its not TRUE, you can solv it with recursive function
Stefan_Lang at 29-Nov-12 6:59am
   
Maybe, but not with the formula that was provided: It separates a list of numbers into odd and even numbers. Performing that same step on either of the two sub-lists accomplishes nothing. That means the described algorithm is not recursive.

(and besides, solving this problem recursively would be needlessly complex, but if you just want to train your skills in recursive programming that's fine.)
Stefan_Lang at 29-Nov-12 7:30am
   
Ah, I just read another comment of yours - now I get that 'odd' and 'even' does not refer to the stored values, but the array index values. Now, that wasn't really obvious from the description - good job for your finding out!
Rate this: bad
good
Please Sign up or sign in to vote.

Solution 1

Your mistake in the case (n%2!=0) is because you invert the CreateOdd and CreateEven function.

I think your code should be :
if(n%2==0 )
{
                CreatOdd(a,odd,n);
     F(odd,n/2);
    CreatEven(a,even,n);
     F(even,n/2);
 
}
else
{
    CreatOdd(a,odd,n);
     F(odd,(n/2)+1);
    CreatEven(a,even,n);
     F(even,(n/2));
}
because when you have an odd number of elements, you will have 1 more element at an odd position.
F[1,2,3,4,5] = F[1,3,5] + F[2,4] : 3 elements in odd and only 2 in even

You can simplify your code with :
CreateOdd(a,odd,n);
F(odd, (n/2)+n%2);
CreateEven(a,even,n);
F(even,(n/2));

The second mistake must be to use "global" variables (even and odd array) in a recursive function. I do not see in your code sample any declarations for even and odd.

And my last remark, will be in C++ the arrays usually start at index 0:
int a[1];
a[0]=1; //first element in a
a[1]=2; //element out of the array !
  Permalink  
Comments
Stefan_Lang at 29-Nov-12 7:03am
   
Personally, I think it would be easier to read if you wrote n-n/2 rather than (n/2)+n%2. But otherwise I agree with your solution. Good work!
Pascal-78 at 29-Nov-12 17:48pm
   
Let's take an example for n/2+n%2
n=4 => n/2 + n%2 = 4/2 + 4%2 = 2 + 0 = 2 = n/2 (n%2==0)
n=5 => n/2 + n%2 = 5/2 + 5%2 = 2 + 1 = 3 = n/2 + 1 (n%2==1)
with the same formula, you can use the same code when n is odd or even, and you don't need to test n%2.

Concerning my remark on C++ array, don't take it personnaly, it was just a remark. I understood you starts your array at index 1, and it may be easier to understand that CreateOdd function want to put odd-indexed items in odd array (with the usual convention 1st item will have index=0 and 0 is not odd :) )
homa sh at 29-Nov-12 12:45pm
   
i think base in my recursive code is wrong . but i don't know improve it.
Pascal-78 at 29-Nov-12 18:18pm
   
In recursive code, you MUST use local variables (in your case : odd and even must be local arrays)
Try to write the content of odd array at each step :
step 1 odd=[1,3,5]
step 2 (CreateOdd on odd) odd=[1,5] (but last five still in memory so [1,5,5]
step 3 (CreateOdd on odd (as [1,5]) odd=[1] displays 1
step 4 (CreateEven on odd (as [1,5]) even=[5] display 5
step 5 (CreateEven on odd (with 3 items)) even=[5] you expect 3 but remember odd is [1,5,5] when you call CreateEven at this level
homa sh at 3-Dec-12 6:09am
   
thanks Pascal-78
you told true,when I used local variables , solved my problem.

and thanks everybody :D
Rate this: bad
good
Please Sign up or sign in to vote.

Solution 2

Try this:
#include <iostream>
#include <vector>
using namespace std;
 
void oddeven(vector <int> & inv, vector <int> & outv)
{
    if (inv.size() > 1)
    {
        vector <int> odd;
        vector <int> even;
        auto it = inv.begin();
        while (it != inv.end())
        {
            odd.push_back(*it);
            it++;
            if ( it == inv.end()) break;
            even.push_back(*it);
            it++;
        }
        oddeven(odd, outv);
        oddeven(even, outv);
    }
    else
        outv.push_back(inv[0]);
}
 

void dump_vector(vector <int> v)
{
    cout << "{ ";
    for (auto a : v)
    {
        cout << a << " ";
    }
    cout << "}" << endl;
}
 
int main()
{
    vector <int> v,w;
    v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);
    dump_vector(v);
    oddeven(v,w);
    dump_vector(w);
}
  Permalink  
v2
Comments
Mohibur Rashid at 29-Nov-12 20:14pm
   
Even though its a good solution but op would have hard time to understand this. as i have understood he is still learning
CPallini at 30-Nov-12 3:25am
   
I thought about it (and you are probably right). However, I suppose the recursive approach results more clean (and perhaps easier to understand) using std::vector.
homa sh at 3-Dec-12 6:19am
   
thanks CPallini ;
your code is very good :D but it was difficult for understand.
CPallini at 3-Dec-12 7:52am
   
You are welcome. If you find yourself in troubles while understanding any part of the code, don't hesitate asking me.
Member 9586495 at 3-Dec-12 10:31am
   
Solution 2 is an excellent answer to the recursive problem above.

I suppose the new and very compact "auto" functionality like

for (auto a : v)
cout << a << " ";

is only supported by C++11 compilers.

Users of older ones (like me) can code

for (vector::iterator it = v.begin(); it != v.end(); it++)
cout << *it << " ";

and get the same results.

Best regards

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
0 Sergey Alexandrovich Kryukov 535
1 OriginalGriff 244
2 ppolymorphe 116
3 CPallini 82
4 Inimicos 60
0 OriginalGriff 8,988
1 Sergey Alexandrovich Kryukov 8,272
2 CPallini 5,189
3 Maciej Los 4,726
4 Mika Wendelius 3,606


Advertise | Privacy | Mobile
Web03 | 2.8.150819.1 | Last Updated 29 Nov 2012
Copyright © CodeProject, 1999-2015
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100