ArrayList insert at position

derDaniel
Mausschubser
Mausschubser
Beiträge: 76
Registriert: 2. Mai 2012 15:25

ArrayList insert at position

Beitrag von derDaniel »

Hallo,

ich komme stets beim Durchegehn meiner Beispiele in der Methode insert at Position auf ArrayListen auf den gleichen Fehler.

Folgendes Beispiel:

ArrayList:

Code: Alles auswählen

[n = 7]         [n = 4]         [n = 10]
                
  [X]             [x]             [x]
  [X]             [x]             [x]
  [X]             [x]             [x]
  [X]             [x]             [x]
  [X]             [ ]             [x]
  [X]             [ ]             [x]
  [X]             [ ]             [x]
  [ ]             [ ]             [x]
  [ ]             [ ]             [x]
  [ ]             [ ]             [x]
  [ ]             [ ]             [ ]
  [ ]             [ ]             [ ]
insert at position 12

l = 12


1. Schleifendurchlauf:

sum = 0;
pointer p = first;

sum + p.n < l <=> 0 + 7 < 12 ist erfüllt
=> sum = sum +p.n -> sum = 7
=> p = p.next



2. Schleifendurchlauf

sum = 7
p = "2. array"

sum + p.n < l <=> 7 + 4 < 12 ist erfüllt
=> sum = 7+4 = 11
=> p = p.next


3. Schelifendurchlauf

sum = 11
p = "3. array"

sum + p.n < l <=> 11 + 10 < 12 ist nicht mehr erfüllt
=> ist das 3. array voll? NEIN!
=> gilt l - sum > p.n? <=> 12 - 11 > 10 GILT NICHT
=> somit wird m als l - sum + 1 definiert, was 12 - 11 + 1 = 2 entspricht

in Schritt 5 wird nun an der Stelle m, also an der Stelle 2, der Wert K eingesetzt

Je nachdem ist es aus Arrayansicht jedoch 2 Stellen, wenn man bei null anfängt zu zählen, und 1 Stelle, wenn man bei eins anfängt zu zählen, zu viel.

Wo liegt da mein Denkfehler?

Wiki Seite:
https://hermes.algo.informatik.tu-darms ... t_position

unter Induktionsschritt

lulu
Windoof-User
Windoof-User
Beiträge: 24
Registriert: 26. Okt 2011 17:20

Re: ArrayList insert at position

Beitrag von lulu »

Hallo,

schau dir mal hier die Methode Insert at position an, da steht es, dass das neue Element in der position l+1 bzw. nach der position l eingefügt wird.
https://hermes.algo.informatik.tu-darms ... r_sequence

und hier wird betont, dass erste position 1 ist und nicht 0.
https://hermes.algo.informatik.tu-darms ... _sequences

ich habe aber eine andere Frage zu dieser Methode. Als zweite Invarinate ist geschrieben:
sum = n1 + n2 + ... + ni-1, es sollte aber doch ni sein oder?

Grüße

derDaniel
Mausschubser
Mausschubser
Beiträge: 76
Registriert: 2. Mai 2012 15:25

Re: ArrayList insert at position

Beitrag von derDaniel »

OK das hilft weiter :)

Ich habe auch noch eine weitere Frage:

In der Implementation des Induction Steps steht:

If sumBild.nBild

und weiter unten gibt es eine Bedingung die heißt:

IfBild

In welchem Fall ist diese zweite Bedingung erfüllt. Ich konnte mir keinen konstruieren :/

Es würde ja gelten:

sum+p.n>l (damit man in das otherwise kommt)
und l-sum>p.n

löst man die erste Ungleichung nach p.n auf kommt man auf p.n>l-sum
soll nun auch im Algorithmus die zweite Bedingung relevant sein muss p.n gleichzeitg größer und kleiner l-sum sein, wie soll das gehen wenn Gleichheit ausgeschlossen ist?

lulu
Windoof-User
Windoof-User
Beiträge: 24
Registriert: 26. Okt 2011 17:20

Re: ArrayList insert at position

Beitrag von lulu »

wenn sum+p.n>=l ist landen wir auf die Nr.2, und d.h. position l ist im aktuellen Array.
in 2.1. prüfen wir ob das Array voll ist, und wenn ja splitten wir das Array in zwei Arrays, bzw. die zweite hälfte wird zu einem neuen Array (mit p´gezeigt) rübergeschoben. und n wird für die beide Arrays neu gesetzt. :idea: da wir in einem vollen Array kein neues element einfügen können

in 2.2 prüfen wir ob l nun im ersten oder zweiten Teil des gesplitteten Arrays ist.
und daher dem vergleich l-sum>p.n

derDaniel
Mausschubser
Mausschubser
Beiträge: 76
Registriert: 2. Mai 2012 15:25

Re: ArrayList insert at position

Beitrag von derDaniel »

Achsooooo jetzt hab ich gerafft :)

derJan2
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 23. Mai 2012 21:37

Re: ArrayList insert at position

Beitrag von derJan2 »

Lulus Frage sollte nicht untergehen:
lulu hat geschrieben:ich habe aber eine andere Frage zu dieser Methode. Als zweite Invarinate ist geschrieben:
sum = n1 + n2 + ... + ni-1, es sollte aber doch ni sein oder?
Ich denke auch, dass die Summe bis ni gehen sollte, denn führt man den Algorithmus durch, ohne dass die Abbruchbedingung eintritt, dann ist sum nach i=1 Iterationen n1, nach 2 Iterationen n1+n2 usw. Der Denkfehler könnte vielleicht von der Abbruchbedingung sum+p.n>=l stammen, da hier sum und p.n addiert werden. p zeigt jedoch nach Invariante 1 auf die Position i+1, somit ist sum+p.n = sum + ni+1. Auch hier macht es wieder Sinn, dass sum bis ni geht.
Kann das vielleicht jemand (Offizielles) bestätigen?

Gruß, derJan2

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: ArrayList insert at position

Beitrag von Prof. Karsten Weihe »

derJan2 hat geschrieben:Lulus Frage sollte nicht untergehen:
lulu hat geschrieben:ich habe aber eine andere Frage zu dieser Methode. Als zweite Invarinate ist geschrieben:
sum = n1 + n2 + ... + ni-1, es sollte aber doch ni sein oder?
Ich denke auch, dass die Summe bis ni gehen sollte, denn führt man den Algorithmus durch, ohne dass die Abbruchbedingung eintritt, dann ist sum nach i=1 Iterationen n1, nach 2 Iterationen n1+n2 usw. Der Denkfehler könnte vielleicht ...
Ist das wirklich ein Denkfehler?

Im Prinzip kann man doch beides implementieren: eine Schleife, bei der \(sum=n_1+\ldots+n_{i-1}\) gilt, oder auch eine Schleife, bei der \(sum=n_1+\ldots+n_{i-1}+n_i\) gilt. Ich habe ersteres gewählt, weil dann die Initialisierung schön einfach wird.

Beides geht, aber in beiden Fällen muss dann die gesamte Schleife inkl. Abbruch konsistent auf die jeweilige Formulierung der Invariante abgestimmt sein, daher Frage zurück: Ist da eine Inkonsistenz?

KW

lulu
Windoof-User
Windoof-User
Beiträge: 24
Registriert: 26. Okt 2011 17:20

Re: ArrayList insert at position

Beitrag von lulu »

derJan2 hat geschrieben:Lulus Frage sollte nicht untergehen:
Danke :)
Prof. Karsten Weihe hat geschrieben:daher Frage zurück: Ist da eine Inkonsistenz?
meiner Meinung nach ja.

wenn ich dieses Beispiel habe:
N=8, l=10
(n=3) [x][x][x][ ][ ][ ][ ][ ]
(n=5) [x][x][x][x][x][ ][ ][ ]
(n=6) [x][x][x][x][x][x][ ][ ]
(n=8) [x][x][x][x][x][x][x][x]

Laut Wiki:
Induktionsbasis: p=first, sum=0

Induktionsschritt:
1. Iteration:
0+3<10 ==> sum=3 , p=first.next

2. Iteration:
3+5<10 ==> sum=8 , p=first.next.next

3. Iteration:
8+6>10 ==> hier wird das Element auf der Position 10-8+1=3 des aktuellen Arrays eingefügt.

wenn ich nun wie in der Klausuraufgaben zeigen will, dass nach der Iteration i=2 die 2. Schleifeninvariante erfüllt ist:
laut Schleifeninvariante sollte sum = n1 + n2-1 sein. das stimmt aber nicht, weil nach der 2.Iteration sum=n1+n2 ist.

habe ich was übersehen oder falsch verstanden??
Danke

lulu
Windoof-User
Windoof-User
Beiträge: 24
Registriert: 26. Okt 2011 17:20

Re: ArrayList insert at position

Beitrag von lulu »

Für eine Antwort wäre ich echt dankbar :)

Capono
Windoof-User
Windoof-User
Beiträge: 35
Registriert: 27. Okt 2011 16:01

Re: ArrayList insert at position

Beitrag von Capono »

lulu hat geschrieben:
derJan2 hat geschrieben:Lulus Frage sollte nicht untergehen:
Danke :)
Prof. Karsten Weihe hat geschrieben:daher Frage zurück: Ist da eine Inkonsistenz?
meiner Meinung nach ja.

wenn ich dieses Beispiel habe:
N=8, l=10
(n=3) [x][x][x][ ][ ][ ][ ][ ]
(n=5) [x][x][x][x][x][ ][ ][ ]
(n=6) [x][x][x][x][x][x][ ][ ]
(n=8) [x][x][x][x][x][x][x][x]

Laut Wiki:
Induktionsbasis: p=first, sum=0

Induktionsschritt:
1. Iteration:
0+3<10 ==> sum=3 , p=first.next

2. Iteration:
3+5<10 ==> sum=8 , p=first.next.next

3. Iteration:
8+6>10 ==> hier wird das Element auf der Position 10-8+1=3 des aktuellen Arrays eingefügt.

wenn ich nun wie in der Klausuraufgaben zeigen will, dass nach der Iteration i=2 die 2. Schleifeninvariante erfüllt ist:
laut Schleifeninvariante sollte sum = n1 + n2-1 sein. das stimmt aber nicht, weil nach der 2.Iteration sum=n1+n2 ist.

habe ich was übersehen oder falsch verstanden??
Danke
die schleifeninvariante2 gilt ja bei der iteration 3 weil sum = n1 + n2 ist
bei der 2. Iteration wäre bei invariante 2 sum = n1 richtig/was jedoch hier nicht gilt weil mgl weise die Position noch nicht gefunden wurde.

Es ist ja so das die Invariante besagt das etwas teils fertig oder komplett fertig ist.

Invariante 1 wäre denke ich bei Iteration 2 ja gegeben da der Pointer auf den nächsten Array zeigt.(was bei iteration 3 ja nicht stimmt)

Ich denke bei Implementation 1. gilt Schleifeninvariante 1 und bei Implemtation 2 die Schleifeninvariante 2.

lulu
Windoof-User
Windoof-User
Beiträge: 24
Registriert: 26. Okt 2011 17:20

Re: ArrayList insert at position

Beitrag von lulu »

Dass die 2. Schleifeninvariante nur nach dem die Abbruchbedingung erfüllt ist stimmt, ist mir auch aufgefallen. Und genau das ist mein Problem, weil soweit ich weiss, sollten alle schleifeninvarianten nach jeder Iteration erfüllt sein.

nah
Windoof-User
Windoof-User
Beiträge: 33
Registriert: 30. Okt 2011 11:46

Re: ArrayList insert at position

Beitrag von nah »

Ich würde mich auch über ein weiteres Statement dazu freuen.
In der 2. Invariant wird auch noch "nj" erwähnt... wo kommt das denn her??
Kann mir schwer vorstellen, dass euch bei dem ganzen diskutieren das nicht aufgefallen ist.
Wäre froh wenn mich jemand aufklärt.

Grüße

derJan2
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 23. Mai 2012 21:37

Re: ArrayList insert at position

Beitrag von derJan2 »

nah hat geschrieben:In der 2. Invariant wird auch noch "nj" erwähnt... wo kommt das denn her??

"nj is the value of the component n of the array list item at the position j element of {1,...,i-1}"
Etwas weniger formal ausgedrückt heißt das, nj ist der Füllstand des j-ten Arrays der Arraylist, gibt also an, wie voll das Array, das sich an der j-ten Position der Arraylist befindet, ist.
Capono hat geschrieben:Ich denke bei Implementation 1. gilt Schleifeninvariante 1 und bei Implemtation 2 die Schleifeninvariante 2.
Dass die 1. Invariante nach Iteration 3 streng genommen nicht gilt, halte ich für nicht so tragisch, da hier ja bereits die Abbruchbedingung (am Anfang der 3. Iteration) gilt. Aber die 2. Invariante hat meiner Meinung nach einen Off-by-One-Error, deshalb wäre ich über einen Kommentar von Prof. Weihe dankbar. Hier nochmal ein Beispiel, das ohne konkrete Zahlen auskommt, falls Ihnen das lieber ist:

Nach 0 Iterationen ist sum = 0 und p = first gemäß Induction basis. Angenommen, in der 1. Iteration wird die Abbruchbedingung nicht erfüllt. Dann wird der Schritt 1.1 (sum := sum + p.n) ausgeführt. Das heißt, sum ist nun gleich dem Füllstand des 1. Arrays. Schauen wir uns jetzt die 2. Invariante an: Nach i=1 Iteration sollte sum = n1 + ... + ni-1 = n1 + ... n0 = 0 sein. Der Füllstand des 1. Arrays ist allerdings nicht 0 (zumindest nicht allgemein, so wie es die Invariante in der aktuellen Form fordert). Deshalb sollte die Invariante "sum = n1 + ... + ni" lauten. Dann stimmt es auch hier: sum = n1 + ... + ni = n1 + ... + n1 = n1.

Gruß, derJan2

sab
Mausschubser
Mausschubser
Beiträge: 97
Registriert: 28. Okt 2011 08:42

Re: ArrayList insert at position

Beitrag von sab »

derJan2 hat geschrieben:Deshalb sollte die Invariante "sum = n1 + ... + ni" lauten. Dann stimmt es auch hier: sum = n1 + ... + ni = n1 + ... + n1 = n1.
Würde das aber nicht \(sum = n_{1} + n_{1} = 2n_{1}\) ergeben?

lulu
Windoof-User
Windoof-User
Beiträge: 24
Registriert: 26. Okt 2011 17:20

Re: ArrayList insert at position

Beitrag von lulu »

sab hat geschrieben:Würde das aber nicht \(sum = n_{1} + n_{1} = 2n_{1}\) ergeben?
nein, mit sum= n1+...+nj ist gemeint:
Sum=
Tex2Img_1346535261.gif
Tex2Img_1346535261.gif (758 Bytes) 520 mal betrachtet

Antworten

Zurück zu „Archiv“