12,243,058 members (47,441 online)
Rate this:
See more:
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

Posted 25-Nov-12 0:51am
homa sh296
Edited 28-Nov-12 23:40pm
v3
Nelek 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 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 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 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 29-Nov-12 5:49am

its not TRUE, you can solv it with recursive function
Stefan_Lang 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 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:

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 !```
Stefan_Lang 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 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 29-Nov-12 12:45pm

i think base in my recursive code is wrong . but i don't know improve it.
Pascal-78 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 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:

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);
}```
v2
Mohibur Rashid 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 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 3-Dec-12 6:19am

thanks CPallini ;
your code is very good :D but it was difficult for understand.
CPallini 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 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

Top Experts
Last 24hrsThis month
 OriginalGriff 255 Richard MacCutchan 240 Matt T Heffron 203 Jochen Arndt 160 Dave Kreskowiak 146
 OriginalGriff 10,213 F-ES Sitecore 5,138 Jochen Arndt 4,548 Dave Kreskowiak 4,479 Richard MacCutchan 4,261