Kleinsten und größten Wert suchen?

[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

[__--]

ach seh schon

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

[Paul Müller]

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