sortieralgorithmus ohne for, while, goto

Skym0sh0

mh wo wir grad bei dem thema sind

kann man ohne computer c++ programmieren?

junge warum?

caybot

Sollte ich vielleicht die Aufgabe falsch verstanden haben???

Laden Sie sich die Datei herunter und implementieren Sie die Funktion
minimumIndex, so dass sie den Index des kleinsten Elements des übergebenen Arrays zurückliefert. Beachten Sie auch hier die folgende Einschränkung: In dieser Aufgabe dürfen die Schlüsselwörter for, while und goto nicht verwendet werden! Bei Bedarf dürfen Sie weitere Funktionen defnieren, nicht jedoch die Funktionen main, printArray oder readIntArray verändern. Es dürfen auch keine Sortierungs-Bibliotheksfunktionen verwendet werden. Testen und kommentieren Sie Ihre Funktion.

Hier das Programm:
# include <iostream >
using namespace std ;
int readIntArray ( int ** array ) {
cout <<" Bitte geben Sie die Anzahl der zu sortierenden Zahlen ein : ";
int size ;
cin >> size ;
* array = new int [ size ];
for ( int i =0; i< size ; ++i) {
cout <<" Bitte geben Sie die " <<i<<". Zahl ein : ";
cin > >(* array )[i];
}
return size ;
}
void printArray ( int array [], int size ) {
for ( int i =0; i< size ; ++i) {
cout << array [i]<<" ";
}
cout << endl ;
}
int minimumIndex ( int array [], int size ) {
// hier ergaenzen
}
int main (){
int * array = 0;
int size = readIntArray (& array );
printArray (array , size );
cout << " Index des kleinsten Elements : ";
cout << minimumIndex (array , size ) << endl ;
printArray (array , size );
delete [] array ;
}

drakon

Ich würd mal sagen, dass du da ganz gut was mit Rekursion machen kannst.

Der Hinweis weisst da eigentlich drauf..

btw:
Bitte benutz cpp-Tags, damit man den Code auch lesen kann..

Tanren

Also sortieren sollst du ja gar nicht. In der Aufgabenstellung steht du sollst den index des kleinsten Elements finden.
Stichwort: Rekursion

caybot

Hab mal ein wenig rumgefummelt...

int minimumIndex (int array [], int size ) {
    int i=0;
    if (array[i] < array[i+1]) {
        return array[i];
    } 
    return (array[i+1]);
}

... doch noch klappts nicht
Ich denke mal, dass das daran liegt, dass ich "i" anfangs immer wieder auf 0 setze???
Und wie bekomme ich es hin, dass er mir nicht den Wert des Felds im Array ausgibt, sondern den Index?

Hier der komplette bereits veränderte Quelltext:

# include <iostream>
using namespace std;

int readIntArray (int ** array ) {
	cout <<" Bitte geben Sie die Anzahl der zu "
			"sortierenden Zahlen ein: ";
	int size ;
	cin >> size ;
	* array = new int[ size ];
	for ( int i=0; i< size ; ++i) {
		cout <<" Bitte geben Sie die " <<i<<". Zahl ein: ";
		cin >> (* array )[i];
	}
	return size ;
}

void printArray (int array [], int size ) {
	for ( int i=0; i< size ; ++i) {
		cout << array [i]<<" ";
	}
	cout << endl ;
}

int minimumIndex (int array [], int size ) {
    int i=0;
    if (array[i] < array[i+1]) {
        return array[i];
    }
    return (array[i+1]);
}
int main () {
	int * array = 0;
	int size = readIntArray (& array );
	printArray (array , size );
	cout << " Index des kleinsten Elements : ";
	cout << minimumIndex(array , size) << endl;
	printArray(array , size);
	system("pause");
	delete [] array ;
	return 0;
}

drakon

Ich denke mal, dass das daran liegt, dass ich "i" anfangs immer wieder auf 0 setze???

Kannst dich glücklich schätzen. Dafür gibts sogar ein Schlüsselwort. static.

Und wie bekomme ich es hin, dass er mir nicht den Wert des Felds im Array ausgibt, sondern den Index?

Wie meinst du ausgeben? Und wo?

caybot

drakon schrieb:

Ich denke mal, dass das daran liegt, dass ich "i" anfangs immer wieder auf 0 setze???

Kannst dich glücklich schätzen. Dafür gibts sogar ein Schlüsselwort. static.

Also ersetze ich "int i=0" durch "int i"???

Und wie bekomme ich es hin, dass er mir nicht den Wert des Felds im Array ausgibt, sondern den Index?

Wie meinst du ausgeben? Und wo?

Nicht in der Funktion ausgeben, sondern an die Main-Fkt übergeben.
Und da wirds dann in Zeile 36 ausgegeben?!?

drakon

Indem du i zurückgibst?!

Im übrigen sehe ich bei dir noch keine Rekursion..

caybot

int minimumIndex (int array [], int size ) {
    int i;
      if (array[i] <= array[i+1]) {
      return i;
    }
    return (i+1);
}

So sollte es besser klappen, aber noch nicht gut genug, da ich nur schaue ob die erste Zahl <= der Zweiten ist. Wenn das der Fall ist wird der Rest nicht berücksichtigt. Richtig? Wenn ja: Wie kann ich das Problem sinnvoll lösen?

Tanren

Du musst Rekursion benutzen d.h. eine Funktion die sich immer wieder selber aufruft.

Hier mal als kleine Hilfestellung. Den Rest solltest du jetzt eigentlich selber rausfinden.

int findmin(int* array, int size, int ind, int currMinInd){
    /*??*/
    if(/*??*/){
        return currMinInd;
    }else{
        return findmin(array, size, ++ind, currMinInd);
    }

}

int minimumIndex ( int array [], int size ) {
    return findmin(array, size, 0, 0);
}

caybot

Ok. Hab nochmal ein wenig rumgefummelt:

i
int findmin(int* array, int size, int ind, int temp, int currMinInd){   //initialisierung der Rekursion
    if(ind <= size){  // wenn der Index der ind-ten Position im Array kleiner/gleich size ist:
        if(array[ind] <= temp){ // wenn der ind-te Eintrag im Array kleiner/gleich temp ist: 
        return findmin(array, size, ++ind, temp==array[ind], currMinInd==ind); // erhöhe den Wert ind um eins, gib array und size zurück, setze temp gleich dem Wert von array[ind], setze currMinInd gleich ind, dann wiederhole die Rekursion
        }
        else return findmin(array, size, ++ind, temp, currMinInd);  // sonst erhöhe den Wert ind um eins, gib array, size, temp und currMinInd zurück, dann wiederhole die Rekursion
         }
   else return currMinInd;        // sonst gib currMinInd zurück
}

int minimumIndex ( int array [], int size ) {
    return findmin(array, size, 0, 32767,0); // ruft Rekursion auf
}

Fand es irgendwie logischer, currMinInd anfangs auf 32767 zu setzen und dann das kleinste Element zu suchen... funktioniert jedoch immer noch nicht richtig

pumuckl

Gehs doch mal so an, indem du dir eine rekursive Definition dafür überlegst, was ein Array ist:
Ein Array der Länge n>0 ist entweder ein einzelnes Element (n == 1), oder es ist ein Arrayelement, gefolgt von einem Array der Länge n-1

Was ist nun das Minimale Element eines Arrays und dessen Index?
für n=1 ist die Lösung einfach: das Minimum ist das Element selbst, der Index ist 0
für n > 1 ist es entweder das erste Element und Index 0, oder es ist das Minimum des Restarrays und dessen Index im Restarray plus 1

also (schon etwas verallgemeinert):

template <class InputIterator>
InputIterator minIter(InputIterator first, InputIterator last)
{
  InputIterator pos1 = first++; //first zeigt jetzt auf das Restarray
  if (first==last) return pos1; //Restarray ist leer, gibt nur ein Element
  InputIterator restmin = minIndex(first, last); 
  return (*restmin < *pos1) ? restmin : pos1;
}

//Benutzen um kleinste Zahl im int-Array zu finden:
int minimum(int* arr, size_t arr_size)
{
  return *(minIndex(arr, arr + arr_size));
}

//um den index zu finden:
class index_not_found : public std::exception {};

template <class InputIterator>
std::size_t indexOf(InputIterator iter, InputIterator seq_begin, InputIterator seq_end = InputIterator())
{
  if (iter == seq_end || seq_begin == seq_end) throw index_not_found();
  return (iter == seq_begin) ? 0 : 1+ index_of(iter, ++seq_begin, seq_end);
}

//im int-Array
std::size_t minIndex(int* arr, size_t arr_size)
{
  return indexOf(minIter(arr, arr  +arr_size), arr, arr + arr_size);
}

//...
int is[] = {0, -12, 44, 315}
int mini = minimum(is, 4); //-12
std::size_t index = minIndex(is, 4); //1

ungetestet und ohne Gewähr