Funktion mittels Rekursion erstellen

Mr. Bit

Hallo Zusammen,

Habe folgende Aufgaben zu lösen und komme bei der letzten Aufgabe nicht weiter..
Würdet ihr die Aufgabe 4 auch so angehen, oder ist der Ansatz schon komplett falsch?

Die Aufgaben:

1. Funktion 1 (mittels Iteration): void input(int n, int
array[])
Einlesen von n Elementen in den Array von der Tastatur

2. Funktion 2 (mittels Iteration): void output(int n, int
array[])
Formatierte Ausgabe des Arrays aus n Elementen auf dem
Bildschirm

3. Funktion 3 (mittels Iteration): void copy(int quelle[],
int quelle_laenge, int anfang, int anzahl, int
ziel[], int ziel_anfang, int ziel_laenge)
Es soll ein Abschnitt des Arrays quelle (Gesamtlänge
quelle_laenge, Anfang anfang, Anzahl anzahl) in das
Array ziel kopiert werden (überschreibend, ab Element
ziel_anfang, Gesamtlänge ziel_laenge).

4. Funktion 4 (mittels Rekursion): void mischen(int
quelle1[], int quelle1_laenge, int quelle2[],
int quelle2_laenge, int ziel[])
Die Elemente zweier aufsteigend sortierter Arrays quelle1 und
quelle2 sollen zusammengemischt und in einem Array ziel
aufsteigend gespeichert werden.

Idee: Maximum aus quelle1 und quelle2 bestimmen und ans
Ende des Arrays ziel kopieren, dann rekursiv weitermachen
und dabei den Array in dem das Maximum gefunden wurde um
ein Element (das Element am Ende, da die Arrays aufsteigend
sortiert sind) verkürzen, indem der Parameter
quelle1_laenge bzw. quelle2_laenge um 1 vermindert
wird.

Der Code:

# include <iostream>

using namespace std;

int input(int const limit, int arr[])
{
int n;

cout << " Wie viele Elemente wolle Sie einlesen ( maximal "<< 25 <<" ) ? " << endl;
cin >> n;
cout << "" << endl;

	while ( n > limit)
	{
	cout << " Es koennen nur maximal 25 Elemente eingelesen werden.\n" << endl; 
	cout << " Wie viele Elemente wolle Sie einlesen ( maximal "<< 25 <<" ) ? " << endl;
	cin >> n;
	cout << "" << endl;
	}
		for (int i = 0; i < n ; i++)
		{
		cout << " Bitte geben Sie Element Nummer "<< i+1 << " ein."<<endl;
		cin >> arr[i];
		}

cout << "" << endl;

return n;
}
void output(int n, int arr[])
{
for(int i = 0; i < n; i++)
    for(int j = i+1; j < n ; j++)
{
        if (arr[i] > arr[j])
		{
            int temp;
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
}
cout << " Die Zahlen sortiert: \n" << endl;
for(int x = 0; x < n; x++)
    {
        cout << arr[x] << " ";	
    }
cout << "\n" << endl;

}
void copy(int quelle[],int quelle_laenge, int anfang, int anzahl, int ziel1[], int ziel_anfang, int ziel_laenge)
{
int temparr[3]={};

	for (int i = anfang, j = 0; i < anzahl, j < anzahl; i++, j++)
	{
		temparr[j] = quelle[i];
	}
			for (int l = ziel_anfang-1, k = 0; l < anzahl, k < anzahl; l++, k++)
			{
				ziel1[l] = temparr[k];
			}
					cout << " Die Zahlen eingefuegt: \n" << endl;
					for(int x = 0; x < ziel_laenge; x++)
					{
						cout << ziel1[x] << " ";	
					}
						cout << "\n" << endl;

}
int mischen(int quelle1[], int  quelle1_laenge, int quelle2[], int  quelle2_laenge, int ziel[])
{
	for( int k = 11; k >= 0; k--)
	{
		if(quelle1[quelle1_laenge] == quelle2[quelle2_laenge])
			{	
			for(int i = 0; i < quelle1_laenge; i++)
			for(int j = i+1; j < quelle1_laenge ; j++)
				{
				if (quelle1[i] > quelle1[j])							// quelle1 sortieren
					{
					int temp;
					temp = quelle1[i];
					quelle1[i] = quelle1[j];
					quelle1[j] = temp;
					}
				}
						ziel[k] = quelle1[quelle1_laenge];
						return quelle1_laenge-1;
			}
		else
		{
		if(quelle1[quelle1_laenge] > quelle2[quelle2_laenge])
		{
			for(int i = 0; i < quelle1_laenge; i++)
			for(int j = i+1; j < quelle1_laenge ; j++)
				{
				if (quelle1[i] > quelle1[j])							// quelle1 sortieren
					{
					int temp;
					temp = quelle1[i];
					quelle1[i] = quelle1[j];
					quelle1[j] = temp;
					}
				}
						ziel[k] = quelle1[quelle1_laenge];
						return quelle1_laenge-1;
		}
		else
		{
			for(int i = 0; i < quelle2_laenge; i++)
			for(int j = i+1; j < quelle2_laenge ; j++)
				{
				if (quelle2[i] > quelle2[j])					// quelle2 sortieren
					{
					int temp;
					temp = quelle2[i];
					quelle2[i] = quelle2[j];
					quelle2[j] = temp;
					}

				}
						ziel[k] = quelle2[quelle2_laenge];
						return quelle2_laenge-1;
		}
		}	

	}
	cout << " Die Zahlen zusammengefuegt und sortiert: \n" << endl;
	for(int x = 0; x < 11; x++)
	{
	cout << ziel[x] << " ";				// ziel ausgeben
	}
	cout << "" << endl;
}
int main ()
{
int const limit = 25;
int arr[limit];
int n = 0;

int quelle[6] = {1,2,3,4,5,6};
int quelle_laenge = 6;

int anzahl = 3;
int anfang = 2;

int ziel1[12] = {};
int ziel_anfang = 2;
int ziel_laenge = 12;

int quelle1_laenge = 5;
int quelle1[5] = {99,88,77,66,55};
int quelle2_laenge = 6;
int quelle2[6] = {88,77,66,55,44,33}; 
int ziel[11] = {};

				//Funktionen

				cout << "Aufgabe 1:\n" << endl;
				n = input(limit, arr);

				cout << "Aufgabe 2:\n" << endl;
				output(n, arr);

				cout << "Aufgabe 3:\n" << endl;
				copy(quelle, quelle_laenge, anfang, anzahl, ziel1, ziel_anfang, ziel_laenge);

				cout << "Aufgabe 4:\n" << endl;
				mischen(quelle1, quelle1_laenge, quelle2, quelle2_laenge, ziel);

system ("pause");
return 0;
}

Danke euch!

Bitte ordentlich Einrücken, sonst schaut sich niemand deinen Code an!

krümelkacker

Was das Sortieren in der mischen-Funktion zu suchen hat, frage ich mich. Ich hätte die Aufgabe so verstanden, dass mischen schon sortierte Quellen bekommt und einfach "mergen" soll.

pittbull

krümelkacker schrieb:

Was das Sortieren in der mischen-Funktion zu suchen hat, frage ich mich. Ich hätte die Aufgabe so verstanden, dass mischen schon sortierte Quellen bekommt und einfach "mergen" soll.

sieht so aus. ist aber kein guter anwendungsfall für rekursion. wer denkt sich solche blödsinnsaufgeben aus?

volkard

pittbull schrieb:

sieht so aus. ist aber kein guter anwendungsfall für rekursion. wer denkt sich solche blödsinnsaufgeben aus?

Wird wohl auf Mergesort hisnauslaufen, wo dann Rekursion durchaus angemessen ist. Diese Merge-Funktion müßte halt dann ausgetauscht werden durch eine iterative.

Sone

Wer sagt es denn, volkard ist zurück!

Bevor du dich an die Rekursion wagst, solltest du doch erstmal die einfachen Sachen richtig machen.

1. Input
Du hast den Prototypen der Funktion bekommen. Die hat keinen (void) Rückgabewert.
Also fragt die Funktion auch nicht ab, wieviel Werte eingelesen werden sollen. Das bekommt si mitgeteilt.

2. Output.
Die Ausgabe soll formatiert erfolgen und nicht sortiert.
Durch Leerzeichen getrennt ist eher nicht formatiert.

3. Copy
Die einzige Stelle wo du ziel_laenge verwendest, ist bei der Ausgabe (und die hat in dieser Funktion gar nichts zu suchen).
Was soll das temparr mit nur 3 Elementen? (beantworte dir selbst die Frage, nicht mir)
Du must vorher checken, ob durch die Angaben der Start- und Zielindices und der Länge irgendwo die Grenzen der Arrays überschritten werden und dann die Angaben entsprechend ändern.
Dann bleibt eine Schleife ohne Hilfsvariablen über.

4. Mischen mittels Rekursion
Rekursion bedeutet wiederholter Aufruf der Funktion aus sich selber.
Keine Schleifen.

Als Inspiration zum Mergesort: http://www.youtube.com/watch?v=XaqR3G_NVoo

volkard

DirkB schrieb:

Als Inspiration zum Mergesort: http://www.youtube.com/watch?v=XaqR3G_NVoo

Hab da Mergesort eher nicht erkannt.

Der da sagt mir zu.
http://www.youtube.com/watch?v=EeQ8pwjQxTM

Mr. Bit

Zur zweiten Aufgabe:

Was ist denn für dich formatiert?

Sone

Mr. Bit schrieb:

Was ist denn für dich formatiert?

Sauber strukturiert und geordnet.

Rekursion bedeutet wiederholter Aufruf der Funktion aus sich selber.

Das muss nicht wiederholt sein.

Mr. Bit

Sone schrieb:

Sauber strukturiert und geordnet.

Also nur als Ausgabe 1 2 3 4 5 oder was??? Tolle Aufgabe...

Sone

Mr. Bit schrieb:

Also nur als Ausgabe 1 2 3 4 5 oder was???

So ungefähr, ja.
Das erreichst du schon mit

std::copy( arr, arr + n, std::ostream_iterator<int>(std::cout, " "));

Und das Einlesen durch

std::copy_n( std::istream_iterator<int>(std::cin), n, arr );

Aber die Aufgabe will ja, dass du die Schleife explizit schreibst.

Tolle Aufgabe...

Das ist nicht der Grund, warum die Aufgaben Blödsinn sind.

Mr. Bit schrieb:

Also nur als Ausgabe 1 2 3 4 5 oder was??? Tolle Aufgabe...

Formatiet kann auch

oder

Das  1. Elemnet ist:   30
Das  2. Elemnet ist:  110
..
Das 25. Elemnet ist:    3

bedeuten.
(Achte auf die Ausrichtung der Zahlen)

Mr. Bit

Naja da würde ich sagen lasse ich es beim Leerzeichen...

So bis jetzt regelkonform?

void output(int n, int arr[])
{
cout << " Die Zahlen formatiert: \n" << endl;
for(int x = 0; x < n; x++)
    {
        cout <<"" << arr[x] << " ";	
    }
cout << "\n" << endl;

}
void copy(int quelle[],int quelle_laenge, int anfang, int anzahl, int ziel1[], int ziel_anfang, int ziel_laenge)
{
	for (int i = anfang-1, j = ziel_anfang-1; i < anzahl, j < (ziel_anfang-1+anzahl); i++, j++)
	{
		ziel1[j] = quelle[i];
	}
}

volkard

Mr. Bit schrieb:

So bis jetzt regelkonform?

Ich nehme an, Du menutzt den Microsoft-Compiler?

Dann Drücke Alt+A (alles markieren) und dann Alt+F8 (alles automatisch einrücken) vor dem Posten.

Nein.

Du weißt nicht, was i < anzahl, j < (ziel_anfang-1+anzahl) macht.

Außerdem läßt du vollkommen quelle_laenge und ziel_laenge außer acht.
Und bist du dir bei den -1 sicher?

Da in C der Index bei Arrays bei 0 anfängt, würde ich auch eine 0 für anfang angeben, wenn die Quelleu und /oder das Ziel ganz am Anfang ist.
Aber das ist Definitionssache, die du aber dokumentiern musst.

Mr. Bit

Wie soll ich denn hier die längen verwenden? Die werden doch in der main bestimmt. Wozu brauche ich die in der Funktion?

Würdest du das kopieren in einer oder mehreren Schleifen machen?

Bei meinem geposteten Code hat die Ausgabe gestimmt.

Mr. Bit schrieb:

Wie soll ich denn hier die längen verwenden? Die werden doch in der main bestimmt. Wozu brauche ich die in der Funktion?

Würdest du das kopieren in einer oder mehreren Schleifen machen?

Bei meinem geposteten Code hat die Ausgabe gestimmt.

Ja, für dein spezielles Beispiel.
Dann setze anzahl mal auf 6 und ziel_anfang auf 10.
Und dann noch anfang auf 4.
(Bei den Angaben beziehe ich mich auf dein Eröffnungspost)

Mr. Bit

Wie soll ich denn hier die längen verwenden? Die werden doch in der main bestimmt. Wozu brauche ich die in der Funktion?

Würdest du das kopieren in einer oder mehreren Schleifen machen?

Damit du nicht über die Grenzen des Arrays schreibst/liest.^*

War mein Beispiel nicht deutlich?

Wieviel Schleifen willst du denn nehmen? Und warum?

^*Die Funktion kann aus den Array allein nicht mehr die Größe bestimmen.
Und du greifst auf die Arrays in der Funktion zu. Da nützt es nichts wenn die Größen in der main bekannt sind.