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

Question

0.00/5 (No votes)

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:

C++

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 sh

Updated 28-Nov-12 22:40pm

v3

Add a Solution

Comments

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!

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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

Pascal-78 · Accepted Answer · 2012-11-28T23:48:00

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 :

C++

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 :

C++

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:

C++

int a[1];
a[0]=1; //first element in a
a[1]=2; //element out of the array !

Posted 28-Nov-12 23:48pm

Pascal-78

Comments

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

CPallini · Accepted Answer · 2012-11-29T11:36:00

Solution 2

Try this:

C++

#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);
}

Posted 29-Nov-12 11:36am

CPallini

Updated 29-Nov-12 11:38am

v2

Comments

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.

sja63 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<int>::iterator it = v.begin(); it != v.end(); it++)
cout << *it << " ";

and get the same results.

Best regards