Ein Lösungsversuch - RFC
Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Klausur 09/2001
7.a)
anzahl = bis - von
b)
Muss es hier nicht “mitte = (von + bis) / 2 + von” heißen?
anzahl = bis - von
8.a)
i) nein: Einfügen, Löschen, Suchen
ii) nein: Einfügen, Suchen
iii) ja
iv) Löschen?
v) Einfügen?, Löschen?
b)
4, 2, 6, 1, 3, 5, 7
Call by value:
[m]Zeile y reihung[1] reihung[2] a b
1 1 1 2 1 1
2 1 1 2 2 1
3 1 1 2 2 3
4 2 1 2 2 3
0 2 1 2 - -
5 2 1 100 - -[/m]
Call by reference:
[m]Zeile y reihung[1] reihung[2] a b
1 1 1 2 1 1
2 2 1 2 2 1
3 1 3 2 2 3
4 2 3 2 2 3
0 2 3 2 - -
5 2 3 100 - -[/m]
Was ist Call by name?
10.a)
public void add(Poly p)
{
int grad1 = grad();
int grad2 = p.grad();
int grad = Math.max(grad1, grad2);
Poly sum = new Poly(grad);
for (int n = 0; n <= grad; n++)
sum.setKoeff(n, getKoeff(n) + p.getKoeff(n));
this = sum; // diese Zeile wird wohl nicht funktionieren :(
}Ich hab leider keinen Plan, wie ich das Array vergrößern soll… ohne dass alles draus verschwindet. Und das Poly bietet keine Methode, das Array selbst auszulesen…
b)
public double evaluate(double x)
{
double val = 0;
for (int n = 0; n <= grad(); n++)
val += getKoeff(n) * Math.pow(x, n);
return val;
}c)
public Poly derive()
{
Poly der = new Poly(grad() - 1);
for (int n = 1; n <= grad(); n++)
der.setKoeff(n - 1, n * getKoeff(n));
return der;
}d)
class Poly implements Comparable
{
// ...
public int compareTo(Object o)
{
// o sollte ein Poly-Objekt sein!
int n = Math.max(grad(), o.grad());
while (getKoeff(n) == o.getKoeff(n));
if (getKoeff(n) > o.getKoeff(n)) return 1;
if (getKoeff(n) = o.getKoeff(n)) return 0;
if (getKoeff(n) < o.getKoeff(n)) return -1;
}
}Für die anderen beiden Aufgaben muss ich erst lernen. Kommen morgen vielleicht.
Hi Leute,
dann geb ich auch mal meinen Senf dazu:
10.a)
Warum machst du nicht einfach:
koeffizienten=sum;
Der alte Speicherbereich, auf den koeffizienten gezeigt hat, wird dann ja von der Garbage collection aufgesammelt, da ja kein Verweis mehr drauf existiert.
b)
Alternative Lösung : Mit Horner-Schema (dann braucht man das pow nicht)
double evaluate(double x)
{
int i;
double buffer=0;
for(i=grad();i>=1;i--)
{
buffer+=getKoeff(i)*x;
}
buffer+=getKoeff(0);
return buffer;
}
d)
Darfst du das so machen? greifst du da nicht auf ein nicht existierendes Array-Element zu?
Und in der While-Schleife sollte vielleicht irgendwo ein n–; sein, und vielleicht sollte man auch überprüfen ob n schon die null erreicht hat und dann auch abbrechen.
Meine Lösung ist nicht ganz so kurz:
public int compareTo (Object o)
{
Poly p= (Poly) o;
if(grad() >p.grad())
return grad()-p.grad();
int i;
for(i=grad();i>=0;i--)
{
if(getKoeff(i)>p.getKoeff(i)) return 1;
if(getKoeff(i)<p.getKoeff(i)) return -1;
}
return 0;
}
Ciao,
Leonidas
7.b)
ich denke das (von+bis)/2 stimmt schon.
8a)
I) suchen ist o(n) (muss man die ganze liste durchsuchen)
löschen: Wenn das zu löschende Item durch Pointer gegeben ist o(1), sonst muss ich erst suchen
einfügen: o(1), Element einfach an den Kopf anhängen
also: nein, nur suchen hat grösseren Aufwand
II)
suchen ist eigentlich o(n/2), das ist aber effektiv o(n), und worst case sowiso.
löschen: Wie unsortierte Liste
einfügen: muss ich erst die richtige Position suchen
also: nein, suchen und einfügen hat grösseren Aufwand
III)
suchen: o(1)
löschen o(1)
einfügen o(1)
also, ja, alle operationen haben höchstens o(logn)
IV)
ist das ein “ausgeglicherner” (oder wie hiess das nochmal) Baum?
suchen: O(log n), aber worst case (bei nicht ausgeglichenem Baum) ist das o(n), wie liste
löschen : prinzipiell o(1), aber wenn ich den Baum danach wieder ausgleichen muss kann sehr aufwendig werden
einfügen: prinzipiell auch o(1), aber muss ich das danach ausgleichen?
nachdem nix dasteht, nehm ich an dass es nicht ausgeglichen ist:
also, nein, suchen hat mehr aufwand
v) ist das nicht die gleiche Situation wie beim normalen Baum?
hier noch mein MergeSort:
void mergesort(int von, int bis)
//zuSortieren[von] bis zuSortieren[bis] werden sortiert
{
//if there's only one element in the list, we're already done
if(von==bis) return;
//if there are two elements in the list, bring them in order and return
if(von+1==bis)
{
if(zuSortieren[von]>zuSortieren[bis])
{
int buffer=zuSortieren[bis];
zuSortieren[bis]=zuSortieren[von];
zuSortieren[von]=buffer;
}
return;
}
//if there are more elements in the list, then make two lists
//and sort each one with merge sort
int middle=(bis+von)/2;
mergesort(von,middle);
mergesort(middle+1,bis);
int[] buffer=new int[bis-von+1];
//now merge the two lists
int first=von;
int second=middle+1;
int index=0;
while(first<=middle || second <=bis)
{
if(first>middle)
{
//first list is already finished, just
//copy the second list
buffer[index]=zuSortieren[second];
second++;
index++;
}
else if(second>bis)
{
//first list is already finished, just
//copy the second list
buffer[index]=zuSortieren[first];
first++;
index++;
}
else
{
if(zuSortieren[first]<zuSortieren[second])
{
buffer[index]=zuSortieren[first];
index++;
first++;
}
else
{
buffer[index]=zuSortieren[second];
second++;
index++;
}
}
}
for(index=von;index<=bis;index++)
{
zuSortieren[index]=buffer[index-von];
}
}
und mein Parser:
class GrammarRuleException extends Exception
{
GrammarRuleException(){}
}
public class Parser
{
public static void main(String[] args)
{
Parser p=new Parser();
try
{
p.syntaxAnalyse(new String("a+a+(a+a)+a\n"));
}
catch(GrammarRuleException e)
{
System.out.println("Wort gehört nicht zur Sprache");
}
}
protected String s;
int CurrentPos;
public void syntaxAnalyse(String ss) throws GrammarRuleException
{
s=ss;
CurrentPos=0;
S();
if(s.charAt(CurrentPos)!='\n') throw new GrammarRuleException();
}
protected void S() throws GrammarRuleException
{
//check first part of rule
A();
//now see if there's more
if(s.charAt(CurrentPos) == '+')
{
CurrentPos++;
S();
}
else if (s.charAt(CurrentPos) =='\n') return;
}
protected void A() throws GrammarRuleException
{
if(s.charAt(CurrentPos) == 'a')
{
CurrentPos++;
return;
}
else if(s.charAt(CurrentPos)== 'b')
{
CurrentPos++;
return;
}
else if(s.charAt(CurrentPos)=='(')
{
CurrentPos++;
S();
if(s.charAt(CurrentPos)==')')
{
CurrentPos++;
return;
}
else throw new GrammarRuleException();
}
throw new GrammarRuleException();
}
}
Sollte man bei der Aufgabe mit der Komplexität nicht immer Worst Case annehmen?
liste: einfügen n
suchen (worst case: am ende der liste) n
löschen (erst suchen = n) n
liste2: dasselbe wie bei liste
hashtable(mit sondierung, oder?)
einfügen: worst case: alles voll, muss n mal neuen platz berechnen: n
suchen: worst case erfolglose suche: n
löschen erst suchen: n
binärbaum: einfügen: worst case: baum ist wie liste aufgebaut: n
suchen (baum wie oben): n
löschen = suchen +1 = n
AVL Baum: stets (mehr oder weniger) ausgeglichen
einfügen,löschen,suchen logn
(rotationen soll man vernachlässigen denke ich)
Ach ja und Yves, kannst du mir bitte mal das mit “Call by referecnce/value/name” erklären? Checkdes halt null. Thnx
Kann das sein dass das nicht funzt? Wenn ein array kleiner ist als das andere, versucht er ja getKoef(x) mit x > grad() aufzurufen und da sollte es ja dann einen Fehler geben.
Müsste man nicht erst von 0 bis min(grad(),p.grad()) addieren, und dann je nachdem welches polynom den höheren grad hat, den rest addieren?
Glaub das haut so nicht hin, weil du praktisch ax + bx + c*x … + z rausbekommt. Am besten macht mans rekursiv:
double eval(double x, int i){
if(i==0){
return getKoef(i);
}
else return getKoef(i) + x * eval(x, i-1);
}
double evaluate(double x){
eval(x, grad());
}
beim parser und der A() methode:
diese + A macht man am besten mit while schleife:
while(s.charAt(i) == ‘+’){
i++;
A();
}
und das ‘\n’ sollte (da es am Ende der Regel steht) auch in syntaxAnalyse stehen.
void syntaxAnalyse(String abc) throws GrammarRuleException{
String s = abc;
int i = 0;
s();
if(charAt(i) != ‘\n’) throw new GrammarRuleException;
}
hast recht str1ch444,
ich wollte eigentlich schreiben:
buffer=(buffer+getKoeff(i))*x;
Aber in deiner Lösung rechnest du glaub ich falsch rum. Koeffizient mit index null wird ganz oft mit x multipliziert, dabei müsste es laut Angabe eigentlich der koeffizient mit dem höchsten index sein.
@str…
wegen dem Parser:
aber das \n steht doch in meiner syntaxAnalyse ?!
ziemlich genauso wie in deinem Code auch, nur irgendwie sind meine Anführungszeichen zu ' geworden, deswegen schaut das jetzt ein bisschen komisch aus, weiss auch nicht warum.
Stimmt, muss natürlich von 0 nach hinten laufen, aber dann muss noch ne abfrage rein, d.h. wenn i == grad return getkoeff(i) oder so,
Das mit dem ‘\n’ finde ich nur komisch in s(), da gehört das glaube ich gar nicht rein.
Dann überpfüfst du es ja beim s() aufruf und dann nochmal im syntaxAnalyse aufruf oder nicht?
Ich blick des im moment nicht mehr so ganz, bin schon völlig verwirrt von dem ganzen Java zeuch
interessant, wieviele Bugs man noch in Programmen findent die man eigentlich für richtig hält…
@str…
Das mit den “\n” gehört natürlich nicht in s(). Andererseits macht es aber auch nix (wird keine exception geworfen falls es nicht da ist etc.). Das ist noch ein überbleibsel von der ersten Version des Programms, dann hab ich die Überprüfung auch in syntaxanalyse(), und da ist es immer noch.
zu den uebergabe zeugs, habt ihr das (call by value, name, reference) jetzt dieses jahr gemacht oder nicht
Also Yves hat anscheinend (mehr oder weniger) Ahnung davon bzw. davon gehört. Aber ich hab null Plan davon und im Script steht glaub ich auch nichts…
Hab Unterlagen von 2001:
Call by Value:
Der tatsächliche Parameter (ein beliebiger Ausdruck) wird ausgewertet. Der resultierende Wert, eine Konstante, wird an den formalen Parameter gebunden. Der formale Parameter verhält sich ansonsten wie eine prozedurlokale Variable. Daher haben Wertzuweisungen an den formalen Parameter im Prozedurrumpf keine Auswirkungen auf die tat. Parameter ausserhalb der Prozedur.
Call by Reference:
Die Adresse des tat. Parameters (eine Variable) wird ermittelt und an den entsprechenden formalen Parameter gebunden. Der formale Parameter fungiert als ein weiterer Name für den tatsächlichen. Das gilt insbesondere bei Wertzuweisungen an den formalen Parameter im Prozedurrumpf, die sich direkt auf den tatsächlichen Parameter ausserhalb der Prozedur auswirken.
Call by Name:
Der tatsächliche Parameter (ein Ausdruck) ersetzt den entsprechenden formalen Parameter quasi textuell im gesamten Prozedurrumpf, d.h. bei jedem Zugriff auf den formalen Parameter im Prozedurrumpf wird der tat. Parameter neu ausgewertet. Wertzuweisungen an den formalen Parameter wirken sich direkt auf den tat. Parameter ausserhalb der Prozedur aus, wenn der tatsächliche Parameter eine Variable bezeichnet( z.B. a[i+3])
Ich hoffe das hilft 
Und sowas geht in einer Compiler-Sprache?
hmm, da ich das array ja direkt und vollständig übergebe (nicht nur einen ausschnitt dessen), muss IMO der anfang ‚von‘ (der ja auch mal > 0 ist) noch drauf addiert werden. sonst würde ich ja über die hälfte des arrays nie herauskommen. das is was anderes bei dem rekursiven mergesort (werd ich nachher vergleichen…), wo immer nur der zu betrachtende teil des arrays übergeben wird. hier isses aber immer alles.
edit: mir fällt grade auf, dass da (bis + von) steht, nicht (bis - von). dann isses natürlich richtig :wand:
nochmal zu der datenstruktur-aufgabe:
ich denke, str… hat mit allem recht (z. b. worst case einer hashtable ist eine lineare liste, bloss eins stimmt nicht:
das einfuegen eines elements in der UNsortierten einfach verketteten liste hat konstanten aufwand o(1), weil man es einfach am anfang dranhaengen kann. ansonsten stimm ich komplett mir dir ueberein…