PDA

Visualizza la versione completa : [C] soluzione "ricorsiva"


shAke82
10-05-2004, 10:45
Non riesco a risolvere questo problema ricorsivo...
Data una lista di interi x verificare se esiste un prefisso di l di peso x.
Dove il prefisso i-esimo di l sono i suoi primi i elementi. Il peso di una lista di interi e' la somma dei suoi elementi.

Bloody3000
10-05-2004, 16:29
Speiga meglio cosa devi fare...........
mi sembra di capire che devi fare una procedura ricorsiva che trovi quel risultato
solo che non si capisce per niente il problema!! ;)

shAke82
10-05-2004, 18:52
chiedo venia :D

in pratica ho una lista di interi
ex. tos -> 3 -> 4 -> 9 -> 18 -> 2 -> 1

ed un intero x
ex. x=16

nel caso dell'esempio la funzione deve restituire VERO visto che esiste un prefisso i-esimo* (3) di l che ha come peso** x (16).

(l(1) -> l(2) -> l(3) =3+4+9 =16)

* Il prefisso i-esimo di l sono i suoi primi i elementi.
** Il peso di una lista di interi e' la somma dei suoi elementi.

In effetti e' un po' incasinato se non esplicito per bene ;)

Ora il problema io saprei risolverlo in modo iterativo, ma in modo ricorsivo non riesco a capire che devo fare :P

FreeManX
10-05-2004, 18:57
uhmm ma la complessita di questo coso (a livello di calcolo macchina) cresce con il crescere della pila!!!

Dovresti verificare tutte le permutazioni possibili con gli elementi della lista. Sti ca!!! :D

shAke82
10-05-2004, 19:01
vero che cresce con il crescere della pila ma per le permutazioni non credo servano visto che...

"le finestre di peso" sono quelle che vanno dalla testa ad i, NON tutte le finestre della lista..... per fortuna :D

FreeManX
10-05-2004, 19:05
Originariamente inviato da shAke82
vero che cresce con il crescere della pila ma per le permutazioni non credo servano visto che...

"le finestre di peso" sono quelle che vanno dalla testa ad i e non tutte le finestre della lista..... per fortuna :D

cioe' tu devi vedere la somma di elementi continui???? e non zompettando qua e la nella lista?

shAke82
10-05-2004, 19:07
Originariamente inviato da FreeManX
cioe' tu devi vedere la somma di elementi continui???? e non zompettando qua e la nella lista?

yeeesssssssssssssss ;)

FreeManX
10-05-2004, 19:10
cioe:

prendi l'elemento i-esmio e provi a sommarlo con i+1,i+2 finche non arrivi alla somma???

e se non arrivi che devi fare???

bye

shAke82
10-05-2004, 19:16
hai una lista di interi ed un intero x:

il primo elemento della lista e' uguale a x?

se no

il primo + secondo elemento della lista = x?

se no

il primo + secondo + .... i-esimo elemento della lista = x?

se no, non esistono finestre della lista uguali a x e ritorni falso...altrimenti ritorni vero :P

rocco.g
10-05-2004, 19:27
Originariamente inviato da shAke82
hai una lista di interi ed un intero x:

il primo elemento della lista e' uguale a x?

se no

il primo + secondo elemento della lista = x?

se no

il primo + secondo + .... i-esimo elemento della lista = x?

se no, non esistono finestre della lista uguali a x e ritorni falso...altrimenti ritorni vero :P

ma non diventa troppo pesante l'esecuzione del programma così ?

cioè se ci sono parecchi controlli da fare la procedura non diventa troppo lunga e pesante ?

p.s. scusate se ho fatto un'osservazione assurda...

Loading