Kleinsten und größten Wert suchen?

[bandchef]

Hi Leute!

Ich soll folgende Übungsaufgabe machen. Die Aufgabe seht ihr im Link auf diesem Bild.
Ich habe schon mal irgendwie Verständnisschwierigkeiten mit der Aufgabe. Was soll denn das mit dem oberen und unteren Teil des long-Ergebniswertes gemeint sein? Ein Long hat 32Bit. Gut aber und da soll jetzt quas in Bit 31-16 das größte Element des short-Wertes drinstehen und in den Bits 15-0 das kleinste Element des Arrays sein, oder wie? Und das alles soll ich Rekursiv lösen.

Mein bisheriger Ansatz lautet so:

#include<iostream>
#include<stdlib.h>
using namespace std;

int minmax(short array)
{
	int len;
	len = sizeof(array);

	for(int i=0; i<3; i=i+1)
	{
		short array_neu[i] = array[i];
	}

	return minmax(array);
}

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

	minmax(array[6]);

system("pause");
return 0;
}

Leider seht ihr ja, dass da noch so einiges fehlt und noch nicht so wirklich funktioniert...

Könnt ihr mir vielleicht ein bisschen weiterhelfen?

[bandchef]

Sorry, hab da wohl den Linkm zur Aufgabe vergessen: http://img842.imageshack.us/i/unbenanntfbm.jpg/

[Paul Müller]

bandchef schrieb:

Die Aufgabe seht ihr im Link auf diesem Bild.

Welches Bild?

#include<stdio.h>    // C ?
#include<stdlib.h>
//using namespace std;  // C ?

int minmax(int len, short * array) // Zeiger auf das Feld, sonst kopierst du nur den ersten Wert
{
	int len;
	//len = sizeof(array); // geht nur mit statischen Feldern

	for(int i=0; i<3; i=i+1)
	{
		short array_neu[i] = array[i];
	}

	return minmax(len, array);
}

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

	minmax(array); // hier übergibst du das sechste Element (gibt es auch gar nicht)

system("pause");
return 0;
}

Ich hab dir den Quelltext mal soweit korrigiert und die Gründe genannt. Ohne Aufgabe kann man aber zum Ablauf nichts sagen.

[Paul Müller]

Da wir deine Vorlesung nicht kennen, kennen wir auch deinen Algorithmus nicht. Wenn ich aber mal raten darf, dann dient der long-Wert einfach nur dazu, um zwei Werte zurück geben zu können.

[bandchef]

Die Sache mit der iostream ist folgende: Ich nutze das nur weil die ausgaben einfacher zu bewerkstelligen sind. Was machst du da mit dem zeiger? Der Zeiger zeigt wahrscheinlich auf die erste Adresse des arrays, oder? Ich hab grad gelesen, dass man die Länge eines Arrays in C zur Laufzeit des Programms nicht bestimmen, das simmt doch oder? D.h. doch jetzt man könnte diese variable len, bei der Funktionsübergabe und in der funktion weglassen, oder? Das würde dann jetzt alles so aussehen:

#include<iostream>
using namespace std;

int minmax(short *array)
{
	for(int i=0; i<3; i=i+1)
	{
		short array_neu[i] = array[i];
	}

	return minmax(array);
}

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

	minmax(array);

system("pause");
return 0;
}

Die aufgabe hab ich oben jetzt mit nem link eingefügt. sorry nochmal dafür. Mein VS2010 zeigt mir aber jetzt noch einen fehler in der forschleife beim variablen index i des arrays "array_neu".

Wie soll ich denn nun eigentlich weitermachen? Ich weiß bei der aufgabe irgendwie so gar nicht wie ich rangehen soll! Ich hab eigentlich schon das probelm, dass ich nicht weiß wie ich am besten das array mit den 6 werten in zwei gleich große teile aufteile. Wenn ich nun dafür for-schleifen bemühe, dann muss ich ja zählegrenzen definieren. und genau da hab ich doch dann das problem, wenn ich ein neues 3 elemente array habe, dass ich ja das dann beim rekursionsschritt wieder teilen muss (damit ich auf diese elementaren einheiten komme so betiteln wir das in der VL). in dieser zweiten teilung passen dann aber die zählergrenzen nicht mehr... Keine ahnung wie ich an das Probleme herangehe!

danke für deine /eure hilfe!

[Paul Müller]

bandchef schrieb:

Die Sache mit der iostream ist folgende: Ich nutze das nur weil die ausgaben einfacher zu bewerkstelligen sind.

Kann ich jetzt nicht nachvollziehen und ich würde es auch sinnvoller finden, wenn man C lernen will, nicht C++ in C zu programmieren. Auch scheint mir C von VS eher Stiefmütterlich behandelt zu werden, für ordentliche Resultate würde ich lieber den gcc nutzen.

bandchef schrieb:

Was machst du da mit dem zeiger? Der Zeiger zeigt wahrscheinlich auf die erste Adresse des arrays, oder?

Ist soweit korrekt. Wenn du aber die Menge teilen willst, musst du auch mal die Mitte als erste Adresse annehmen.

bandchef schrieb:

Ich hab grad gelesen, dass man die Länge eines Arrays in C zur Laufzeit des Programms nicht bestimmen, das simmt doch oder?

Ein Array ist einfach nur ein Bereich im Speicher. Bei einem statischen Array kennt der Compiler die Größe und gibt sie dir auch mit sizeof. Die Größe eines dynamischen Arrays wird aber erst zur Laufzeit bekannt.

bandchef schrieb:

D.h. doch jetzt man könnte diese variable len, bei der Funktionsübergabe und in der funktion weglassen, oder?

Ich kann deine Schlussfolgerung nicht nachvollziehen, genau das Gegenteil ist der Fall, du benötigst zwingend die Größe.

bandchef schrieb:

Mein VS2010 zeigt mir aber jetzt noch einen fehler in der forschleife beim variablen index i des arrays "array_neu".

Lies dir mal laut deine Anweisung vor, ich denke du kommst selber drauf.

bandchef schrieb:

Ich hab eigentlich schon das probelm, dass ich nicht weiß wie ich am besten das array mit den 6 werten in zwei gleich große teile aufteile.

Glaube ich dir nicht, du hast die Lösung doch schon selber genannt. Um ein Array zu übergeben nutzt du die Anfangsposition, beim teilen halbierst du einfach die Größe und fertig.

short array[6];

int len = sizeof(array) / sizeof(short); // sizeof liefert immer Bytes

short * linke_haelfte = &array[0];
int len_linke_haelfte = len / 2;

short * rechte_haelfte = &array[len_linke_haelfte]; // sprich die zweite Hälfte beginnt da, wo die erste aufhört
int len_rechte_haelfte = len / 2;

Aufpassen musst du natürlich, wenn len kein ganzzahliges vielfaches von 2 ist. Es muss immer gelten:

len_linke_haelfte + len_rechte_haelfte == len

[Wutz]

bandchef schrieb:

#include<iostream>
#include<stdlib.h>
using namespace std;

int minmax(short array)
{
	int len;
	len = sizeof(array);

	for(int i=0; i<3; i=i+1)
	{
		short array_neu[i] = array[i];
	}

	return minmax(array);
}

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

	minmax(array[6]);

system("pause");
return 0;
}

Du vermischt C und C++.
Wenn du dich entschieden hast, musst du auch einen C bzw. C++ Compiler einsetzen.
Wenn du dich für C entschieden hast und einen ANSI C Compiler verwendest sieht eine standardkonforme Lösung z.B. so aus:

#include <assert.h>
#include <stdio.h>
#include <limits.h>

#ifdef __cplusplus
#error ich versuche gerade, mit C++ zu compilieren
#endif

unsigned long minmax(short array,size_t arraygroesse)
{
  size_t i;
  short smin=SHRT_MAX;
  short smax=SHRT_MIN;

  for(i=0;i<arraygroesse;++i)
  {
    if( array[i]<smin ) smin=array[i];
    if( array[i]>smax ) smax=array[i];
  }

  printf("\nmax: %d\n min: %d",smax,smin);

  return smax<<16 | smin;
}

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

  /* hier prüfen, ob die int-Typen auch die geforderten Größen besitzen */
  assert(sizeof(long)>=4);
  assert(sizeof(short)==2);

  minmax(array,sizeof array/sizeof*array);

  return 0;
}

Wie du beim Durchdenken des o.g. Beispiels vielleicht erkennen wirst, kann man die Größe eines Arrays bei Übergabe als Parameter an eine Funktion in der Funktion nicht mehr bestimmen, deshalb musst du sie zuvor berechnen und extra mitgeben.

[bandchef]

@Paul Müller:

Folgendes hab ich jetzt mal in meinem Code gemacht:

#include <stdlib>

int minmax(short *array)
{
	int len = sizeof(array);

	short *links = &array[0];
	int len_links = len / 2;

	short *rechts = &array[len_links];
	int len_rechts = len / 2;

	return minmax(array);
}

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

	minmax(array);

system("pause");
return 0;
}

Ich hab dazu noch eine Frage:

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?

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...

Desweiteren fuckt das Programm wenn ich es "richtig" ausführe. Ich denke das liegt an den Zeigern. Ich weiß aber nicht so wirklich warum. Ich übergebe doch der *links durch den Kaufmannsund-Operator die Adresse des arrays an der Stelle 0 im Speicher, oder? Genauso verfahre ich mit *rechts...

[jlkjljk]

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

[kljjkl]

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...

[guckst du hier]

_-- 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){

[Paul Müller]

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