Hallo ich setze mich grade mit folgendem Problem auseinander:

Gegeben sei eine Folge von n Elementen. Sie haben ein Verfahren, mit dem Sie je zwei Elemente auf Gleichheit oder Ungleichheit testen ko ̈nnen, und Sie wissen, dass ein Element echt mehr als n/2 mal in dem Feld vorkommt. Dieses Element gilt es zu bestimmen.

Dafür fehlt mir noch der naive Algorithmus, ich habe überlegt es so zu machen, das erste Element zu wählen und jedesmal wenn es vorkommt, einen Counter um 1 hochzählen zu lassen, nach dem die Folge durchlaufen wurde, das zweite Element nehmen, gucken ob es mit dem vorigen übereinstimmt, und falls nicht einen weiteren Counter erstellen.
Das ganze erscheint mir einerseits Laufzeitmäßig sehr schwach, und zum anderen glaube ich das es Lücken gibt, wenn ich zu viele verschiedene Elemente habe.

Ich habe nun die Frage ob jemand nen Tipp hat wie man diesen naiven Ansatz besser angehen kann.

Cheers
Ralf

Mit Quicksort sortieren und dann einfach das Element in der Mitte (also an der Stelle n/2) nehmen

Da ist der 2. Teil der Aufgabe, mittels Teile und Herrsche, das habe ich schon, hier soll ich einen "naiven" Ansatz finden, deswegen macht es das ja so schwer

Zitat von bRainLaG

Da ist der 2. Teil der Aufgabe

Wo denn?

Und was ist für dich ein "naiver" Ansatz?
Das soll wohl eher alternativ heißen...

Und deine beschriebene Vorgehensweise ist alles andere als "Teile und Herrsche", wie du es nennst und dazu noch ziemlich sicher langsamer als meine Variante.
Laufzeit=O((n/2)*(n+1))=O((n^2+n)/2)
Laufzeit bei meiner Art wahrscheinlich: O(n*logn)

Alternativer Ansatz...so zB?
Laufzeit auch O(n*logn)
Programmiert in C, array und n sollten Selbsterklärend sein.

Code cpp:

1 2 3 4 5 6 7 8 9 10

int i,e,a; e=n; do {     if(e==0){/*Kein zutreffendes Element drinnen*/}     e/=2;a=0;     for(i=0;i<n;i++)         if(array[i]==array[e])             a++; }while(a<=(n/2));

(Habs jetzt nicht selber getestet.)

Immer ein bestimmtes Element nehmen und prüfen, ob es mehr als n/2 Mal vorkommt.
Das Element ist zuerst das mittlere (n/2), dann n/4, n/8 usw...
Wenn das Vorkommen vom gesuchten Element wirklich >n/2 ist, muss es da irgendwo dabei sein.

Sry hab mich etwas doof ausgedrückt den Teilen und Herrschen Teil habe ich schon, deswegen nicht aufgeführt. Ich sollte zu Anfang noch einen naiven Ansatz finden, den ich jetzt damit begründet habe, das ich jedes ELement bis n durchlaufe, und prüfe ob es n/2 vorkommt, falls nicht wird es verworfen und falls doch lasse ich es mir ausgeben, danke trotzdem für die Hilfe

Ich merk gerade, dass ich teilweise ziemlichen Blödsinn geschrieben hab.
Vergiss meinen Code

Zitat von bRainLaG

Dafür fehlt mir noch der naive Algorithmus, ich habe überlegt es so zu machen, das erste Element zu wählen und jedesmal wenn es vorkommt, einen Counter um 1 hochzählen zu lassen, nach dem die Folge durchlaufen wurde, das zweite Element nehmen, gucken ob es mit dem vorigen übereinstimmt, und falls nicht einen weiteren Counter erstellen.
Das ganze erscheint mir einerseits Laufzeitmäßig sehr schwach, und zum anderen glaube ich das es Lücken gibt, wenn ich zu viele verschiedene Elemente habe.

Ein naiver Ansatz zeichnet sich meistens dadurch aus, dass er in Laufzeit und/oder Speicherverbrauch nicht optimal ist. Das sollte dich also nicht stören. Deine Idee ist schon nicht schlecht, allerdings brauchst du nur einen Zähler:

Code c:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

int a[] = { 1, 2, 5, 3, 5, 4, 5, 5, 5 }; int n = sizeof(a) / sizeof(a[0]); int i, j, element, count;   // Alle Elemente durchlaufen for (i = 0; i < n; ++i) {   element = a[i];   // Vorkommnisse von element in a zählen   count = 0;   for (j = 0; j < n; ++j) {     if (a[j] == element) count++;   }   // Ausgabe und Abbruch falls element mehr als n/2 mal vorkommt   if (count > n/2) {     printf("%d", element);     break;   } }

\edit: @sheel: Um die Elemente zu sortieren, müsste eine Ordnung auf ihnen definiert sein. In der Aufgabe steht aber nur, dass man auf (Un-)Gleichheit testen kann.

Grüße,
Matthias