Forum: Knobelecke

Hallo,

aus aktuellem Anlass hier ein neues Rätsel:

Gegeben sind n unterschiedliche Zahlen. Gesucht sind die größte und die zweitgrößte Zahl.

Wer findet dafür das effizienteste Verfahren?

Viel Spass,
Philip

--
The C Programming Quiz - bitte Fragen einreichen :)

 

Hmm... seid ihr noch am Knobeln?
Ist das Rätsel zu leicht?
Zu schwer?

Gruss,
Philip

--
The C Programming Quiz - bitte Fragen einreichen :)

 

Hallo Philip,

vom Gefühl her würde ich per Schleife durch den Zahlenhaufen iterieren und jeweils prüfen, ob die aktuelle Zahl die größte oder zweitgrößte Zahl ist.
Aber wie ich dich kenne, gibt es da wieder einen Haken.
Effizient wäre daher imho, den Zahlenhaufen aufsteigend zu sortieren um anschließend die letzten beiden Zahlen als Ergebnis zu verwenden.
Ich würde hierfür die Funktion qsort verwenden.

Gruß,
Patrick-Oliver

--
To follow the path: look to the master, follow the master, walk with the master, see through the master, become the master.

 

Bei Verwendung eines Divide and Conquer Ansatzes kommt man auf 3N/2 - 2 benötigte Vergleiche.

 

#include <stdio.h>
#include <stdlib.h>


int sort(const void *a, const void *b)
{
 // aufsteigend
 return *(int *)a - *(int *)b;

 // absteigend
 // return *(int *)b - *(int *)a;
}


int main()
{
 int arr[] = {3,5,4,7,9,1,8,2,6};
 int s = sizeof arr / sizeof *arr;
 int i = 0;
 int *groesste, *zweitgroesste;

 // Sortiert das Array arr aufsteigend
 qsort(arr, s, sizeof *arr, sort);

 groesste      = &arr[s-1];
 zweitgroesste = &arr[s-2];

 // Kontrolle
 //for (; i<s; i++)
 //{
 // printf("%i ", arr[i]);
 //}

 printf("Groesste: %d, zweitgroesste: %d\n", *groesste, *zweitgroesste);
 return EXIT_SUCCESS;
}

Nachtrag:
Ich gehe mit meiner Lösung davon aus, dass sich mindestens zwei Zahlen im Zahlenhaufen befinden.

Nachtrag 2:
Und hier die Lösung zu meinem "Bauchgefühl".

#include <stdio.h>
#include <stdlib.h>


int main()
{
 int arr[] = {3,5,4,7,9,1,8,2,6};
 int s = sizeof arr / sizeof *arr;
 int i = 1;

 // Das erste Element im Array wird anfaenglich je als Groesstes und Zweitgroesstes angenommen.
 int *groesste = arr;
 int *zweitgroesste = arr;


 for (; i<s; i++)
 {
  // Ist das aktuelle Element im Array arr groesser oder gleich dem groessten, gespeicherten Wert?
  if (*groesste <= arr[i])
  {
   zweitgroesste = groesste;
   groesste = &arr[i];
  }
  // Oder ist das aktuelle Element im Array arr groesser als das Zweitgroesste?
  else if (*zweitgroesste < arr[i])
  {
   zweitgroesste = &arr[i];
  }
 }

 printf("Groesste: %d, zweitgroesste: %d\n", *groesste, *zweitgroesste);
 return EXIT_SUCCESS;
}

--
To follow the path: look to the master, follow the master, walk with the master, see through the master, become the master.