Kleinsten und größten Wert suchen?

bandchef schrieb:

Dieses &array[0] bei der Stelle wo ich quasi auf den Speicherinhalt von "rechts" zeige, sieht ja quasi so aus wie ich es dir in diesem Bild aufgemalt habe: http://img809.imageshack.us/i/80237326.jpg/ Meine Vorstellung dürfte doch richtig sein, oder?

Aber mit &array[0] wird die Variable namens links befüllt. Zusätzlich hat man mit len_links die Länge dieses Bereichs. Der rechte Bereich beginnt dann dort, wo der linke aufgehört hat und wird daher mit &array[len_links] beschrieben.

bandchef schrieb:

Noch eine Frage zu sizeof Operator. Der gibt mir nur die Bytegröße zurück. ich brauche aber doch die Elementanzahl, oder? Wenn ich mir das jetzt aber im Debugger von VS2010 anschaue, dann steht da in "len" eine 4 drin. 4 Elemente hat aber dieses Array auf den ich den sizeofe-Operator anwende nicht; es hat 6 Elemente. Ich verstehe deshalb nicht wie ich mit diesem Operator arbeiten soll...

Mit sizeof ermittelt man die Größe in Bytes. Es wird im oberen Code zunächst die Größe des gesamten Arrays berechnet. Anschließend wird die gesamte Größe durch die Größe eines einzelnen Elements geteilt. Das Ergebnis sollte also die Anzahl der Elemente im Array sein.

Dein Programm ist fehlerhaft, denn es läuft in eine Endlosschleife und stürzt daher nach kurzer Zeit ab.

_--

long minmax(short *a,size_t l){
	long ret;
	if(l==1){
		short A = a[0];
		ret = (A<<16) | A;
	}else{
		size_t ll = l/2;
		long A = minmax(a,ll);
		long B = minmax(a+ll,l-ll);
		if((B & 0xFFFF0000) > (A & 0xFFFF0000)){
			A ^= B;
			B ^= A;
			A ^= B;
		}
		if((B & 0xFFFF) < (A & 0xFFFF)){
			A ^= A & 0xFFFF;
			A |= B & 0xFFFF;
		}
		ret = A;
	} 
	return ret;
}

bandchef

int len_links = len / 2;

Wenn ich nun hiermit die Anzahl der Elemente berechne, dann kann da aber trotzdem was nicht stimmen. Ich hab ein Array mit 6 Elemente und hat laut erstmaliger Berechnung eine Größe von 4Bytes. Wenn ich nun nach der Teilung des arrays das nun durch 2 teile, dann komm ich ja auf 2 Elemente... Ich hab aber doch im linken wie im rechten Teil nach der ersten Teilung 3 Elemente...

bandchef

Ich glaub ich bin jetzt auf meinen Fehler selbst gekommen. Ich lass mir die größe des arrays das in der main Deklariert wird schon noch in der main berechnen und übergebe dann len an die Funktion.

Hier mein Code:

#include<stdlib.h>

int minmax(int len, short *array)
{
	short *links;
	links = &array[0];		//Startadresse von "array" linker Teil
	int len_links = len / 2;

	short *rechts;
	rechts = &array[len_links];		//Startadresse von "array" rechter Teil
	int len_rechts = len / 2;

	return minmax(len, array);
}

int main()
{
	int len;
	short array[6] = {3,2,7,8,9,1};

	len = sizeof(array) / sizeof(short);

	minmax(len, array);

system("pause");
return 0;
}

Genau, das ist der Fehler gewesen. Schön, dass du ihn selbst gefunden hast.

Anstatt diesen Code

len = sizeof(array) / sizeof(short);

kannst du auch folgendes schreiben:

len = sizeof(array) / sizeof(*array);

Ist weniger fehleranfällig, falls man mal den Typ ändert...

bandchef

Wenn ich nun mal den Debuger durchführe und die Werte hier aufschreiben darf, dann sieht das jetzt so aus:

links = 3 -> diese 3 ist klar, da es die "Startadresse" des arrays ist...
len_links = 3 -> 3 Elemente für den linken Teil, klar...
rechts = 8 -> Wie kommt die 8 zustande? Das ist doch eigentlich die Startadresse des neuen rechten Arrays, nicht?
len_rechts = 3 -> 3 Elemente für den rechten Teil, klar...

Nun hab ich schon genau das Problem, dass wenn ich nun quasi einen Rekursionsschritt machen möchte, dass ich dann bei der wiederholten Berechnung von len_links bzw. len_rechts kein ganzzahliges Vielfaches von 2 mehr bekomme. Wie geh ich jetzt da weiter vor? Vor allem wie bring ich da jetzt einen Rekursionsschritt rein? Ich muss ja jetzt quasi eine neue Instanz mit veränderten Übergabeparametern starten und auch noch irgendwie der Rekursion sagen wann sie die rückführenden Rekursionschritte machen soll... So wie's jetzt ist wäre es ja noch eine Endlosschleife! Das überfordert mich jetzt noch irgendwie...

_-- schrieb:

long minmax(short *a,size_t l){
	long ret;
	if(l==1){
		short A = a[0];
		ret = (A<<16) | A;
	}else{
		size_t ll = l/2;
		long A = minmax(a,ll);
		long B = minmax(a+ll,l-ll);
		if((B & 0xFFFF0000) > (A & 0xFFFF0000)){
			A ^= B;
			B ^= A;
			A ^= B;
		}
		if((B & 0xFFFF) < (A & 0xFFFF)){
			A ^= A & 0xFFFF;
			A |= B & 0xFFFF;
		}
		ret = A;
	} 
	return ret;
}

bandchef

Ich denke ich muss da jetzt irgendwie mit if-Abfragen arbeiten. Vor allem: Ich muss ja auch den Fall berücksichtigen wenn nach dem ersten Mal schon der linke und rechte Teil nur noch ein Elemente besitzt, sprich das Ausgangsarray mit nur 2 Elementen deklariert wurde...

Das stell ich mir grad so noch vor:

int minmax(int len, short *array)
{
	short *links;
	links = &array[0];		//Startadresse von linkem Teil des Arrays
	int len_links = (len / 2);

	short *rechts;
	rechts = &array[len_links];		//Startadresse von rechtem Teil des Arrays
	int len_rechts = (len / 2);

	if((len_links == 1) && (len_rechts == 1))
	{
			int a = array[0];
			int b = array[1];

			if(a < b)
			{
				int min = a;
				int max = b;
			}
			else
			{
				int min = b;
				int max = a;
			}
	}

	return minmax(len, array);
}

Problem: Ich weiß jetzt nicht recht wie, wo und welchen return-Wertzurüchgeben soll..

@bandchef vorschlag, namensänderung zu wasserträger :xmas1:

statt

if((B & 0xFFFF0000) > (A & 0xFFFF0000)){

reicht auch

if(B > A){

Ich hatte auch eine Lösung anzubieten.

http://codepad.org/pkbJfg92

Paul Müller schrieb:

Ich hatte auch eine Lösung anzubieten.

http://codepad.org/pkbJfg92

was geht da bei len = 1

ach seh schon

min = MIN(array[0], array[0]);
max = MAX(array[0], array[0]);

__-- schrieb:

Paul Müller schrieb:

Ich hatte auch eine Lösung anzubieten.

http://codepad.org/pkbJfg92

was geht da bei len = 1

min = MIN(array[0], array[len - 1]); // len - 1 = 0