größter Wert eines Array

[Gerhard H. (gerhardh)]

Hallo, kann mir bitte jemand sagen wo bzw was in dieser Funktion nicht 
richtig ist?


Mein Ziel ist es, den größten Wert des Array auszugeben, welcher 
mindestens 2x vorkommt.

Das Array ist bereits aufsteigend sortiert.
Habe das Programm schon bis aufs Letze gekürzt um es übersichtlich zu 
halten. Leider bekomme ich keine Ausgabe

uint8_t find_max_value (char feld[],  uint8_t min,  uint8_t max_val)
{
  
  uint8_t i, j, counter=0;
  
  for (i = 1; counter < min; i++)
  {
    counter = 0;
    max_val = feld[((sizeof feld)-i)];
    
    for (j=0; j < sizeof(feld); j++)
    {
      if (feld[j] == max_val)
      {
        counter++;
      }
    }
  }
  
  return max_val;
  
}



int main(void)
{
  char feld [] = { 1, 2, 3, 4, 5, 6, 7, 8, 8, 9};
    uint8_t min = 2;
    uint8_t max_val = 0;


max_val = find_max_value (char feld[],  uint8_t min,  uint8_t max_val);
 

 //LCD Ausgabe
  char row2[16];
  sprintf(row2, "%d",max_val);
  LCDWRITE(row2, 2, 1);
  
  
    while (1) 
    {
    }
}

Beste Grüße

[Stefan F. (Gast)]

Dein Fehler ist, dass du nicht das ganze Programm gezeigt hast. Der 
Fehler ist mit Sicherheit im nicht gezeigten Teil.

> sprintf(row2, "%d",max_val);
> LCDWRITE(row2, 2, 1);

Damit wandelst du max_val in einen String um, und gibst ihn aus. Es ist 
aber nicht erkennbar, wie die Variable deklariert ist und wie sie 
beschrieben wird. Zudem sehe ich keinen Aufruf deiner Funktion 
find_max_value(), die inhaltlich noch nicht geprüft habe.

[Joe F. (easylife)]

sizeof(feld) liefert dir nur innerhalb von main() die Anzahl der 
Elemente zurück.
An find_max_value() übergibst du einen Pointer auf das erste Element des 
Arrays.
Du könntest es auch so schreiben, dann wäre es klarer was passiert:

uint8_t find_max_value (char *feld,  uint8_t min,  uint8_t max_val)

Innerhalb von find_max_value() liefert dir sizeof(feld) die Größe des 
Pointers (4 Bytes vermutlich).

[MikeH (Gast)]

Wenn das Array schon aufsteigend sortiert ist, dann iterierst du von 
hinten solange bis zwei Elemente gleich sind


int i, max;
for(i = sizeof(feld)-2; i >= 0 && (feld[i+1] != feld[i]); --i);

if(i >= 0)
   max = feld[i];

[Gerhard H. (gerhardh)]

Stefanus F. schrieb:
> Dein Fehler ist, dass du nicht das ganze Programm gezeigt hast. Der
> Fehler ist mit Sicherheit im nicht gezeigten Teil.
>
>> sprintf(row2, "%d",max_val);
>> LCDWRITE(row2, 2, 1);
>
> Damit wandelst du max_val in einen String um, und gibst ihn aus. Es ist
> aber nicht erkennbar, wie die Variable deklariert ist und wie sie
> beschrieben wird. Zudem sehe ich keinen Aufruf deiner Funktion
> find_max_value(), die inhaltlich noch nicht geprüft habe.


tut mir leid, da ist eine Zeile untergegangen.
Wurde editiert.

Beste Grüße

[Joe F. (easylife)]

Du solltest unbedingt auch den Fall behandeln, dass in deinem Array kein 
Wert 2x vorkommt...

Vorschlag:

int find_max_value (char feld[], uint8_t elements, uint8_t min_occurences)
{
  int i, j, cnt;

  for (i=(elements-1); i>=0; i--)
  {
    cnt = 1;
    for (j=(i-1); j>=0 ; j--)
    {
      if (feld[i] == feld[j])
        cnt++;
      else
        break;
    }
    if (cnt >= min_occurences)
      return (feld[i]);
  }
  
  return -1;
}


(...)

val = find_max_value(feld, sizeof(feld), 2);

liefert -1 zurück, wenn kein Wert ausreichend oft gefunden wurde.

[Gerhard H. (gerhardh)]

Joe F. schrieb:
> Du solltest unbedingt auch den Fall behandeln, dass in deinem Array kein
> Wert 2x vorkommt...
>
> Vorschlag:
>
>

> int find_max_value (char feld[], uint8_t elements, uint8_t 
> min_occurences)
> {
>   int i, j, cnt;
> 
>   for (i=(elements-1); i>=0; i--)
>   {
>     cnt = 1;
>     for (j=(i-1); j>=0 ; j--)
>     {
>       if (feld[i] == feld[j])
>         cnt++;
>       else
>         break;
>     }
>     if (cnt >= min_occurences)
>       return (feld[i]);
>   }
> 
>   return -1;
> }
> 
> 
> (...)
> 
> val = find_max_value(feld, sizeof(feld), 2);
> 
>

>
> liefert -1 zurück, wenn kein Wert ausreichend oft gefunden wurde.



Oh, danke für den Hinweis. Diesen Fall hatte ich tatsächlich nicht 
berücksichtigt.

DANKE vielmals an ALLE!
Schönes Wochenende

[Rolf M. (rmagnus)]

Gerhard H. schrieb:
> tut mir leid, da ist eine Zeile untergegangen.
> Wurde editiert.

Ich glaube dir nicht, dass du das so ausgeführt hast.

[c++ (Gast)]

MikeH schrieb:
> Wenn das Array schon aufsteigend sortiert ist, dann iterierst du von
> hinten solange bis zwei Elemente gleich sind
>
>
> int i, max;
> for(i = sizeof(feld)-2; i >= 0 && (feld[i+1] != feld[i]); --i);
>
> if(i >= 0)
>    max = feld[i];

Wenn anzahl gleicher Elemente immer zwei ist, gibt es was fertiges aus 
der STL:

int array[] = {1,3,5,6,7,9,10,10,12};
auto resultIt = std::adjacent_find(std::rbegin(array), std::rend(array));
if (resultIt == std::rend(array)) {
  //no element found
}
int resultValue = *resultIt;

[leo (Gast)]

c++ schrieb:
> Wenn anzahl gleicher Elemente immer zwei ist, gibt es was fertiges aus
> der STL:

Was haben die wohl genommen, um fuer ein Nicht-Problem eine Loesung zu 
finden.

leo

[Joe F. (easylife)]

c++ schrieb:
> Wenn anzahl gleicher Elemente immer zwei ist, gibt es was fertiges aus
> der STL:

Dazu muss dann aber das Array absteigend sortiert sein. Sonst bekommst 
du den kleinsten Wert, der 2x vorhanden ist zurück.

[Rolf M. (rmagnus)]

Joe F. schrieb:
> Dazu muss dann aber das Array absteigend sortiert sein.

Nein, es muss aufsteigend sortiert sein, genau wie man es in dem Code 
sieht.

[Carl D. (jcw2)]

Joe F. schrieb:
> c++ schrieb:
>> Wenn anzahl gleicher Elemente immer zwei ist, gibt es was fertiges aus
>> der STL:
>
> Dazu muss dann aber das Array absteigend sortiert sein. Sonst bekommst
> du den kleinsten Wert, der 2x vorhanden ist zurück.

Container kann man auch rückwärts durchlaufen.
Beachte: rbegin()/rend()

[Rainer V. (a_zip)]

Also rein logisch betrachtet, mußt du doch nur jedes Element im Array 
mit allen anderen vergleichen. Da ist es egal, ob das Array sortiert ist 
und es ist egal, ob du "vorn" oder "hinten" anfängst. Wenn sicher ist, 
dass es nur ein Paar im Array geben kann, dann liefert die Suche 
entweder "kein Paar" oder das Paar. Wenn es mehrere Paare geben kann, 
kommen alle Paare als Suchergebnis. Prinzipiell liefert so eine Funktion 
natürlich beliebig lange Tupel, also nicht nur Paare. Das alles läuft in 
zwei verschachtelten Schleifen ab, in denen du die verschiedenen, 
möglichen Ergebnisse verarbeitest.
Da ich außer Python keine Hochsprache wirklich beherrsche, verkneife ich 
mir einen Beispielcode :-)
Gruß Rainer

[Joe F. (easylife)]

Rainer V. schrieb:
> Also rein logisch betrachtet, mußt du doch nur jedes Element im Array
> mit allen anderen vergleichen. Da ist es egal, ob das Array sortiert ist

Mit der Größe des Arrays steigt der Aufwand bei dieser Methode aber 
exponentiell.
Gute Sortieralgorithmen leisten da schon mal eine effiziente Vorarbeit.
Wenn man sich nach dem Sortieren von der größten Zahl nach "vorne" 
durcharbeitet, ist die Wahrscheinlichkeit recht hoch, hier nicht mehr 
lange suchen zu müssen.

[Rofl-Tier (Gast)]

Gerhard H. schrieb:
> ...
>

max_val = find_max_value (char feld[],  uint8_t min,  uint8_t max_val);

> ...


Kann ja nix bei rauskommen. Es wird nicht mal kompiliert. Poste doch mal 
den Code den du tatsächlich benutzt und nicht diesen Rotz.

[Rainer V. (a_zip)]

Joe F. schrieb:
> Mit der Größe des Arrays steigt der Aufwand bei dieser Methode aber
> exponentiell.

Du hast natürlich recht, aber in diesem Fall hier, sehe ich keinen 
Vorteil einer Sortierung. Du mußt doch immer noch jede Zahl des Arrays 
mit allen anderen vergleichen oder?! Natürlich kann es "Rand"bedingungen 
zum Aufbau des Arrays geben, die eine andere Suche sinnvoller als das 
komplette Vergleichen machen. Jedenfalls war die Angabe zum Array 
lediglich, dass Zahlen mindestens doppelt vorkommen können und damit 
macht das Vorsortieren keinen Sinn mehr...du mußt jede Zahl des Arrays 
mit allen anderen vergleichen. Oder habe ich gerade einen Knoten im Kopf 
:-)
Gruß Rainer

[Joe F. (easylife)]

Rainer V. schrieb:
> Du mußt doch immer noch jede Zahl des Arrays
> mit allen anderen vergleichen oder?!

Nein. Sortieralgorithmen versuchen genau dies zu verhindern, da der 
Aufwand exponentiell steigen würde.
Bei dem Beispiel hier mit nur 10 Array-Elementen spielt das keine Rolle, 
aber lass es mal tausende von Werten werden.
Nach dem Sortieren beschränkt sich das Vergleichen auf die Anzahl der 
Elemente im Array, da immer nur mit den direkten Nachbarn verglichen 
werden muss (der Aufwand steigt dann also nur linear mit der Anzahl der 
Array-Elemente).

Wenn sich der Wertebereich im Array auf char beschränkt, gäbe es noch 
eine sehr schnelle, aber etwas speicherintensivere Lösung:
Man nimmt ein Hilfsarray mit 256 Einträgen, und inkrementiert den Wert 
in diesem Hilfsarray jedesmal bei dem Index, der dem Wert im 
(unsortierten) Daten-Array entspricht.
Für jeden theoretisch im Daten-Array vorkommenden Wert steht im 
Hilfsarray dann die Anzahl der gefundenen Werte.
Anschließend durchsucht man dieses Hilfsarray von hinten anfangend 
(Wert=255) nach unten, bis das Suchkriterium (Mindestanzahl der 
Vorkommnisse) erfüllt ist.
Der Rechenaufwand ist entsprechend gering und steigt quasi linear mit 
der Größe des zu durchsuchenden Arrays:
Anzahl der Elemente im Daten-Array + 255 (max.)

[Rainer V. (a_zip)]

OK, habs kapiert. Danke für die Erklärung!
Gruß Rainer und gute Nacht...