Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Programmazione 2, 9 CFU => Topic started by: peppe89ct on 26-04-2010, 21:25:30



Title: aiuto sistema di esercitazione
Post by: peppe89ct on 26-04-2010, 21:25:30
mi imbattevo ina domanda a risposta multipla....del tipo
Una linked-list semplice in cui head è diverso da tail  contiene almeno due elementi
che io ho spuntato perchè mi sembrava vera invece è falsa...qualcuno mi aiuta a capire???????


Title: Re:aiuto sistema di esercitazione
Post by: Daréios89 on 26-04-2010, 21:49:00
Mh, ancora l'argomento non l'ho ben fissato in mente, così, suggerisco una cosa che mi è venuta in mente, ma non so se giusta, se per esempio head è diverso da tail tu pensavi almeno ci fossero due elementi.
E se per esempio tail è uguale a null?


Title: Re:aiuto sistema di esercitazione
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 26-04-2010, 22:19:26
Mh, ancora l'argomento non l'ho ben fissato in mente, così, suggerisco una cosa che mi è venuta in mente, ma non so se giusta, se per esempio head è diverso da tail tu pensavi almeno ci fossero due elementi.
E se per esempio tail è uguale a null?
tail=null\Rightarrowhead=null\Rightarrowhead=tail

Secondo me è corretto dire che ci sono almeno 2 elementi. E ora lo dimostro formalmente:

Lemma
Sia L linked list semplice.
head (L)\neqtail (L)\RightarrowCount (L)\geq2

Dim.
(Nota: \oplus è il simbolo dell'operatore logico XOR)
Per assurdo sia Count (L) < 2.
Essendo che Count (L)\geq0 per definizione, si ha che
Count (L) < 2 \RightarrowCount (L) = 0 \oplus Count (L) = 1

Caso 1 - Count (L) = 0 \Rightarrow head (L) = tail (L) = null
ASSURDO era head (L) \neq tail (L)

L'unica altra possibilità è il
Caso 2 - Count (L) = 1 \Rightarrow head (L) = tail (L) \neq null
ASSURDO era head (L) \neq tail (L) ∎

L'unico motivo per cui il lemma può essere falso, è che stiamo analizzando lo "stato" della lista linkata semplice "durante" un'inserimento o una cancellazione, senza che l'intera procedura sia stata completata.
Ma mi sembra troppo esagerato dover pensare pure a questi micro-dettagli... .penso


Title: Re:aiuto sistema di esercitazione
Post by: peppe89ct on 26-04-2010, 22:26:35
Ma tu ancora alle 11 e 20 riesci a fare le dimostrazioni con ilo lemma???? complimenti il mio cervello è andata in StackOwerflowError...ciao e notte 


Title: Re:aiuto sistema di esercitazione
Post by: mafalda on 10-05-2010, 09:08:35
Code:
BinarySelect(A, a, b)
1. if (a==b) then return A[a];
2. c = floor ((a+b)/2);
3. S1 = S2 = 0;
4. for i=a to c do S1 = S1 + A[i];
5. for i=c+1 to b do S2 = S2 + A[i];
6. if (S1 > S2) then return BinarySelect(A, a, c);
7. else return BinarySelect(A, c+1, b);

con A=[6, 2, 2, 10, 1, 6, 3, 7] e i parametri (A,1,8).

Svolgendo questo esercizio a me risulta 7 l'output, mentre il sistema di esercitazione mi dice che il corretto output è 10 ma non capisco come ci arrivi a questo risultato???


Title: Re:aiuto sistema di esercitazione
Post by: cock86 on 10-05-2010, 09:44:28
che calcoli fai??!?


Title: Re:aiuto sistema di esercitazione
Post by: mafalda on 10-05-2010, 09:51:07
( A, 1, 8 )  con c=4 , s1= 20 , s2= 27.  s1<s2 quindi:

( A, 5, 8 )  con c=6 , s1=7 , s2=16 . s1<s2 quindi:

( A, 7,8 )  con c=7 , s1= 3 , s2=10 . s1<s2 quindi:

( A, 8, 8 )  con c=8 , ma a questo punto ho che a==b e quindi:

A[8] che nel mio array risulta essere 7.

Cosa c'è che non va???


Title: Re:aiuto sistema di esercitazione
Post by: cock86 on 10-05-2010, 09:57:31
l'errore sta nella S2, l'ho trovato già dalla prima riga e non sono andato avanti. Quindi non so se dopo c'è altro. Comunque nella S2 sommi gli elementi da c+1 a b, quindi nel prima caso da 5 a 8, che fa 17 e non 27.


Title: Re:aiuto sistema di esercitazione
Post by: mafalda on 10-05-2010, 10:02:03
Hai ragione!!! non ci avevo fatto caso..perfetto grazie mille, adesso tutto chiaro!!!  .coolio


Title: Re:aiuto sistema di esercitazione
Post by: cock86 on 10-05-2010, 10:11:57
figurati!! .camberman