Search Second Largest Element

Bei Postings zu Aufgabe Nr. x = 1..4 lassen Sie Ihr Betreff bitte mit "x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Aufgabe Nr. x = 1..4 lassen Sie Ihr Betreff bitte mit "x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!
Induktionsbeweis
Neuling
Neuling
Beiträge: 7
Registriert: 6. Sep 2016 21:49

Search Second Largest Element

Beitrag von Induktionsbeweis » 14. Sep 2016 15:30

Hallo Leute :)

ich versuche gerade die Nabla-Programmieraufgabe "Search Second Largest Element" zu Lösen. Eine verbindliche Anforderung an die Implementation ist "Die Anzahl der compare-Aufrufe darf n nicht überschreiten."
Ich weiß nicht, wie ich vorgehen soll, um diese Anforderung zu erfüllen. Hat evtl. jmd einen Denkanstoß?

Sabrina
Neuling
Neuling
Beiträge: 3
Registriert: 27. Aug 2016 13:23

Re: Search Second Largest Element

Beitrag von Sabrina » 14. Sep 2016 20:43

public void searchSecondLargestElement() {
int i = 0;
setLargest(0);
setSecLargest(-1);
Comparator<T> c = getComp();
for(int i=0; i <= get.length(); i++) {
if (c.compare(getLargest(), getElement(i))) > 0 {
if(c.compare(getSecLargest(),getElement(i))) >= 0 {
}
else { //(c.compare(getSecLargest(),getElement(i)))<0
setSecLargest(getElement(i));
}
}
else if (c.compare(getLargest(), getElement(i))) < 0 {
setSecLargest(getLargest());
setLargest(getElement(i));
}
else { //(c.compare(getLargest(), getElement(i))) == 0
if (c.compare(getSecLargest(),getElement(i))) < 0 {
setSecLargest(getElement(i));
}
else { //(c.compare(getSecLargest(),getElement(i))) == 0
}
}
}
return getSecLargest();
}

Sabrina
Neuling
Neuling
Beiträge: 3
Registriert: 27. Aug 2016 13:23

Re: Search Second Largest Element

Beitrag von Sabrina » 14. Sep 2016 20:44

Code: Alles auswählen

public void searchSecondLargestElement() {
	int i = 0;
	setLargest(0);
	setSecLargest(-1);
	Comparator<T> c = getComp();
	for(int i=0; i <= get.length(); i++) {
		if (c.compare(getLargest(), getElement(i))) > 0 {
			if(c.compare(getSecLargest(),getElement(i))) >= 0 {
			}
			else {	//(c.compare(getSecLargest(),getElement(i)))<0
				setSecLargest(getElement(i)); 
			}	
		}
		else if (c.compare(getLargest(), getElement(i))) < 0 {
			setSecLargest(getLargest());
			setLargest(getElement(i));
		}
		else {	//(c.compare(getLargest(), getElement(i))) == 0 
			if (c.compare(getSecLargest(),getElement(i))) < 0 {
				setSecLargest(getElement(i));
			}
			else {	//(c.compare(getSecLargest(),getElement(i))) == 0 
			}
		}
	}
	return getSecLargest();
}

Induktionsbeweis
Neuling
Neuling
Beiträge: 7
Registriert: 6. Sep 2016 21:49

Re: Search Second Largest Element

Beitrag von Induktionsbeweis » 14. Sep 2016 22:16

Vielen Dank für die Antwort, allerdings vergleichst du in deinem Code ja über n mal :?

kci
Windoof-User
Windoof-User
Beiträge: 24
Registriert: 21. Apr 2016 20:54

Re: Search Second Largest Element

Beitrag von kci » 14. Sep 2016 23:54

wenn ich mir das array [10,1,2,3,4,5,6,7,8,9] vorstelle fällt mir auch kein weg ein wie ich mit n Vergleichen hinkomme

dieser code besteht den Test mit den maximalen Nutzungen von compare, vielleicht siehst du ja warum :lol:

Code: Alles auswählen

{
int length=getLength();
if(length>1){
    int j=0;
    while(getElem(j)==null){
        j++;
    }
    int k=j+1;
        while(getElem(k)==null){
        k++;
    }
    if(k<length){
    if(getComp().compare(getElem(j),getElem(k))>=0){
         setLargest(j);
         setSecLargest(k);
    }
    else{
         setLargest(k);
         setSecLargest(j);        
    }
    for(int i=k+1;i<length;i++){
        if(getElem(i)!=null){
        if(getComp().compare(getElem(getLargest()),getElem(i))<0){
            setSecLargest(getLargest());
             setLargest(i);
             }else if(getComp().compare(getElem(getSecLargest()),getElem(i))<0){
                setSecLargest(i); 
             
        }
        
    }
    } 
}
}
}
Zuletzt geändert von kci am 15. Sep 2016 00:26, insgesamt 1-mal geändert.

Induktionsbeweis
Neuling
Neuling
Beiträge: 7
Registriert: 6. Sep 2016 21:49

Re: Search Second Largest Element

Beitrag von Induktionsbeweis » 15. Sep 2016 00:09

Danke :D

vielleicht ist auch in der Aufgabenstellung ein Fehler, mittlerweile bin ich nämlich ziemlich skeptisch, ob es überhaupt möglich ist, das Problem mit n(oder weniger) Vergleichen zu lösen.

Antworten

Zurück zu „AuD: Programmieraufgaben“