Dom 18 Agosto, 06:32:31 - 2019

Autore Topic: Testo esame 7 Febbraio 2011  (Letto 7348 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline Parasca

  • Direttore di Dipartimento
  • ***
  • Post: 1909
  • FeedBack: +267/-229
  • Una scrivania ordinata è sintomo di mente malata!
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #30 il: Gio 10 Febbraio, 22:59:51 - 2011 »
Ora non ricordo bene, ma sono sicuro al 99% che la risposta a quella domanda era la somma di due termini.

No, quella nn era perchè l'ho messa io ed era sbagliata..
--> "...ma che matrimonio io voglio sperperare un patrimonio, morire in manicomio, andare all’inferno e far impazzire il demonio...!" <-- (Articolo <3)


Offline Lorixx89

  • Professore Associato
  • *
  • Post: 641
  • FeedBack: +60/-14
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #31 il: Ven 11 Febbraio, 10:08:54 - 2011 »
Ma erano 2 le risposte con la somma di due termini..

Offline gengio5

  • Studente di Dottorato
  • ***
  • Post: 133
  • FeedBack: +9/-6
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #32 il: Sab 12 Febbraio, 12:36:53 - 2011 »


Scusate ma il programma del problema 1 di Algoritmi cosa dovrebbe fare?L'ho scritto,fatto partire e non fa assolutamente nulla!

Offline Parasca

  • Direttore di Dipartimento
  • ***
  • Post: 1909
  • FeedBack: +267/-229
  • Una scrivania ordinata è sintomo di mente malata!
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #33 il: Sab 12 Febbraio, 18:17:32 - 2011 »
Incrementa di 1 il numero che tu metti nella lista..da quello che ho capito faceva questo..metti che voglio incrementare di uno il numero 192...allora mettevi nella lista prima il 2, poi il 9, e poi l'uno...quando andrai a stamparla dopo averla sottoposta al metodo dovrebbe (e dico dovrebbe) darti  391 (perchè li mette al contrario..e quindi sarebbe 193)..almeno credo..
--> "...ma che matrimonio io voglio sperperare un patrimonio, morire in manicomio, andare all’inferno e far impazzire il demonio...!" <-- (Articolo <3)


Offline gengio5

  • Studente di Dottorato
  • ***
  • Post: 133
  • FeedBack: +9/-6
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #34 il: Lun 14 Febbraio, 19:43:29 - 2011 »
Incrementa di 1 il numero che tu metti nella lista..da quello che ho capito faceva questo..metti che voglio incrementare di uno il numero 192...allora mettevi nella lista prima il 2, poi il 9, e poi l'uno...quando andrai a stamparla dopo averla sottoposta al metodo dovrebbe (e dico dovrebbe) darti  391 (perchè li mette al contrario..e quindi sarebbe 193)..almeno credo..


Grazie!Ho provato e mi stampa qualche numero,ma le vere difficoltà poi sono nel realizzare i metodi degli esercizi successivi

Male male  ???

Offline Parasca

  • Direttore di Dipartimento
  • ***
  • Post: 1909
  • FeedBack: +267/-229
  • Una scrivania ordinata è sintomo di mente malata!
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #35 il: Lun 14 Febbraio, 21:29:43 - 2011 »
I metodi successivi sono molto semplici..una volta che hai capito il meccanismo..cioè per quanto riguarda quello che decrementa per esempio..immaginati prima un caso generale..il numero   345 che deve decrementare di 1..inizialmente l'index starà sul "5"..finchè l'index è maggiore di 0, non c'è problema, basta che con una set modifichi il numero puntato dall'index, decrementandolo di 1..quindi qualcosa del tipo set(index, val-1)..il numero diverrà  344..
Il caso speciale è nel caso in cui hai qualche zero...facciamo che hai per esempio  100: quando ti trovi uno "0" non serve decrementare di uno perchè avresti -1, penso che la soluzione sia settare il valore puntato dall'index a 9, e chiamare ricorsivamente il metodo con index + 1..
Per il passo base non saprei..da per scontato ci sia un numero strettamente positivo se non sbaglio..

Per la differenza io ho usato solo il metodo decrementa al suo interno..

Spero di esserti stata d'aiuto e di non aver detto cavolate..
--> "...ma che matrimonio io voglio sperperare un patrimonio, morire in manicomio, andare all’inferno e far impazzire il demonio...!" <-- (Articolo <3)


Offline gengio5

  • Studente di Dottorato
  • ***
  • Post: 133
  • FeedBack: +9/-6
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #36 il: Mar 15 Febbraio, 12:01:04 - 2011 »
I metodi successivi sono molto semplici..una volta che hai capito il meccanismo..cioè per quanto riguarda quello che decrementa per esempio..immaginati prima un caso generale..il numero   345 che deve decrementare di 1..inizialmente l'index starà sul "5"..finchè l'index è maggiore di 0, non c'è problema, basta che con una set modifichi il numero puntato dall'index, decrementandolo di 1..quindi qualcosa del tipo set(index, val-1)..il numero diverrà  344..
Il caso speciale è nel caso in cui hai qualche zero...facciamo che hai per esempio  100: quando ti trovi uno "0" non serve decrementare di uno perchè avresti -1, penso che la soluzione sia settare il valore puntato dall'index a 9, e chiamare ricorsivamente il metodo con index + 1..
Per il passo base non saprei..da per scontato ci sia un numero strettamente positivo se non sbaglio..

Per la differenza io ho usato solo il metodo decrementa al suo interno..

Spero di esserti stata d'aiuto e di non aver detto cavolate..


Però è strano:ho fatto come mi hai detto,ho messo nella lista il numero 192 ma invece di stamparmi 193 mi dà 0 e poi 1

Offline Parasca

  • Direttore di Dipartimento
  • ***
  • Post: 1909
  • FeedBack: +267/-229
  • Una scrivania ordinata è sintomo di mente malata!
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #37 il: Mar 15 Febbraio, 13:26:49 - 2011 »

Però è strano:ho fatto come mi hai detto,ho messo nella lista il numero 192 ma invece di stamparmi 193 mi dà 0 e poi 1

Si..mi sono espressa male, scusami..ti ho detto "finchè l'index è maggiore di zero" quando in realtà è il "val" che deve essere maggiore di zero..cioè il "cifre.get(index)"

Così è come l'ho fatto io:

Codice: [Seleziona]
public static void decrementa(LinkedList<Integer> cifre) {
    decrementaRic(cifre, 0);
}
public static void decrementaRic(LinkedList<Integer> cifre, int index) {
    if (index >= cifre.size())
        cifre.add(0);
    else {
        Integer val = cifre.get(index);
        if (val > 0)
            cifre.set(index, val-1);
        else {
            cifre.set(index, 9);
            decrementaRic(cifre,index+1);
        }
    }
}
« Ultima modifica: Mar 15 Febbraio, 13:29:16 - 2011 da Parasca »
--> "...ma che matrimonio io voglio sperperare un patrimonio, morire in manicomio, andare all’inferno e far impazzire il demonio...!" <-- (Articolo <3)


Offline spin

  • Ricercatore
  • ****
  • Post: 274
  • FeedBack: +3/-6
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #38 il: Mar 15 Febbraio, 18:47:08 - 2011 »

il costo in funzione della dimensione dell'input cosa dovrebbe venire?  ???

Offline Parasca

  • Direttore di Dipartimento
  • ***
  • Post: 1909
  • FeedBack: +267/-229
  • Una scrivania ordinata è sintomo di mente malata!
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #39 il: Mar 15 Febbraio, 20:14:30 - 2011 »
il costo in funzione della dimensione dell'input cosa dovrebbe venire?  ???

Mi sembra abbia costo lineare.. O(n) sia per incrementa che per decrementa..al massimo viene effettuata una chiamata ricorsiva per ogni intero della lista..inolte c'è il metodo della LinkedList "get(index)" che ha costo O(n)
--> "...ma che matrimonio io voglio sperperare un patrimonio, morire in manicomio, andare all’inferno e far impazzire il demonio...!" <-- (Articolo <3)


Offline Lorixx89

  • Professore Associato
  • *
  • Post: 641
  • FeedBack: +60/-14
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #40 il: Mer 16 Febbraio, 11:36:41 - 2011 »
Attenzione perché se viene effettuata una sola chiamata ricorsiva per ogni intero della lista, e ad ogni chiamata c'è la get(index) che costa O(n) il costo complessivo diviene quadratico, ossia O(n^2)

Offline Parasca

  • Direttore di Dipartimento
  • ***
  • Post: 1909
  • FeedBack: +267/-229
  • Una scrivania ordinata è sintomo di mente malata!
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #41 il: Mer 16 Febbraio, 12:23:01 - 2011 »
Attenzione perché se viene effettuata una sola chiamata ricorsiva per ogni intero della lista, e ad ogni chiamata c'è la get(index) che costa O(n) il costo complessivo diviene quadratico, ossia O(n^2)

Oddio sai che mo mi viene il dubbio? Perchè io ricordo di aver scritto O(n) e era esatto mi pare.. O.o
La chiamata ricorsiva comunque non è in un ciclo..boh
--> "...ma che matrimonio io voglio sperperare un patrimonio, morire in manicomio, andare all’inferno e far impazzire il demonio...!" <-- (Articolo <3)


Offline Lorixx89

  • Professore Associato
  • *
  • Post: 641
  • FeedBack: +60/-14
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #42 il: Mer 16 Febbraio, 12:36:15 - 2011 »
Non è necessario che sia in un ciclo la chiamata ricorsiva per ottenere un costo quadratico. E' la stessa ricorsione a "simulare" un ciclo sulla linkedlist. Un ciclo che costa O(n). Ma sono praticamente convinto che se ad ogni chiamata, chiami anche la get della linkedlist che nel caso peggiore è O(n) allora tutto il codice costa O(n^2). Se non è vero allora pazienza.. xD Almeno algoritmi l'ho tolto hihi

Offline Parasca

  • Direttore di Dipartimento
  • ***
  • Post: 1909
  • FeedBack: +267/-229
  • Una scrivania ordinata è sintomo di mente malata!
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #43 il: Mer 16 Febbraio, 16:29:42 - 2011 »
Boh non mi convince...il costo quadratico non mi torna proprio..perchè non è che chiamo il metodo ricorsivo ogni volta su tutti gli elementi della lista..ma prima su quello con indice  0 poi 1, poi 2..quindi se sommi tutto il costo è O(n)..è vero, c'è una get, ma il costo complessivo secondo me a questo punto sarebbe del tipo O(n) (per la get) + O(n) (per le chiamate ricorsive)..boh non riesco neanche a spiegarlo decentemente..magari qualcuno ci viene in aiuto e ci dice cosa pensa  :asd:
--> "...ma che matrimonio io voglio sperperare un patrimonio, morire in manicomio, andare all’inferno e far impazzire il demonio...!" <-- (Articolo <3)


Offline spin

  • Ricercatore
  • ****
  • Post: 274
  • FeedBack: +3/-6
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #44 il: Mer 16 Febbraio, 17:10:13 - 2011 »

se davvero il metodo get() su una lista ha costo O(n) mi sa che ha ragione lui...viene quadratico. Tra l'altro tra i 2 compiti c'è una differenza: in uno si usa il generico metodo get() su una lista (che ha costo O(n)) mentre nell'altro si usa il metodo get() sull'iteratore che ha costo lineare come c'è scritto anche sullo stesso compito. Quindi mi sa che in quello della lista veniva quadratico e nell'altro lineare.....alla correzione nn vi ricordate che hanno detto i prof?