Idee per un esercizio

a
alessio.palma (1480 points)
0 34 56
asked Jan 29, 2019 in Info sul corso e sugli esami by alessio.palma (1,480 points)

def es10(lista1, lista2):
    '''
    Es. 10:  9 punti
    Abbiamo due liste di interi lista1 e lista2 per ogni elemento di lista1 vogliamo sapere se e' esprimibile
    sommando (anche piu' volte ) interi presenti nella lista2.
    Si definisca la funzione ricorsiva (o che usa una vostra funzione ricorsiva) es10(lista1, lista2)
    che, prese le due liste, restituisce una terza lista della stessa lunghezza di lista1.
    La terza lista lista3 contiene solo zeri e/o uni.
    Per ogni i, il valore lista3[i] sara' uno se l'intero lista1[i] e' esprimibile come somma degli
    interi presenti in lista2 (presi anche più volte), sara' zero altrimenti.
    Ad esempio per
    lista1=[ 10, 11, 23,26,27,28]
    lista2=[ 13,5]
    es4(lista1,lista2) restituisce [1, 0, 1, 1, 0, 1]
    perche'
    10 = 5+5
    11 non è ottenibile come somma di soli interi appartenenti a [13, 5]
    23 = 13+5+5
    26 = 13+13
    27 non è ottenibile come somma di soli interi appartenenti a [13, 5]
    28 = 13+5+5+5

Idee su come risolverlo? 

206 views

3 Answers

Best answer
ledoriver (4630 points)
1 6 17
answered Jan 29, 2019 by ledoriver (4,630 points)
selected Jan 30, 2019 by alessio.palma

Io ho provato così.

L'idea sarebbe quella di chiamare la funzione ricorsiva su di un numero alla volta di lista1 e per quel numero analizzare tutti i casi possibili, non appena ne trovo uno che viene allora ritornare '1', altrimenti sempre '0'.

Posso riconoscere subito il caso baso in cui deve venire '1' che sarebbe quando un numero di lista2 è un suo divisore.

inoltre ho aggiunto che se il numero i di lista2 è maggiore di n di lista1 è sicuro che non andrà bene.

se nessuno di questi casi in cui ritorno per forza '1' o per forza '0' si verifica per i allora chiamo la funzione su se stessa ma invece che n (il numero della lista1) la chiamo con n-i

(la funzione ricorsiva come argomenti prende solo n e lista2)

Ora non so gli altri test ma con lista1=[ 10, 11, 23,26,27,28], lista2=[ 13,5] mi viene, ho fatto altri test con diverse liste e mi viene...

Posso mandare il codice o è contro il regolamento? 

Emanuele (5950 points)
0 6 12
commented Jan 29, 2019 by Emanuele (5,950 points)
È ovviamente contro il regolamento scemo, ma non ti preoccupare, ti lovvo lo stesso.
a.capobianco1 (16770 points)
1 54 165
commented Jan 29, 2019 by a.capobianco1 (16,770 points)
Beh.. Stiamo parlando di esercizi per i quali una soluzione pubblica è stata già pubblicata... Non stiamo parlando di homework... Avere la possibilità di confrontare diversi modi di risolvere credo possa essere costruttivo infondo... Anche tutte le soluzioni dell'appello dell'8 sono state pubblicate... Anche tutti i codici degli hw a scadenza sono a disposizione di tutti coloro che vi hanno partecipato... Stiamo parlando di esercizi vecchi... Poi l'ultima parola è del prof.
Emanuele (5950 points)
0 6 12
commented Jan 29, 2019 by Emanuele (5,950 points)
Ma si, volevo solo prendere in giro ledo, comunque effettivamente se le soluzioni sono pubbliche, allora forse non è un problema mandare codice.
ledoriver (4630 points)
1 6 17
commented Jan 29, 2019 by ledoriver (4,630 points)
ora mi metto a piangere
ledoriver (4630 points)
1 6 17
commented Jan 29, 2019 by ledoriver (4,630 points)

Dove si può trovare il testo dell'appello dell'8?

a
alessio.palma (1480 points)
0 34 56
commented Jan 29, 2019 by alessio.palma (1,480 points)
Non ho provato il tuo codice ma l'idea sembra giusta, se però un numero di lista1 non ha divisori in lista2 può darsi che sia comunque ottenibile sommando il numero di lista2 ad altri numeri, questo caso come lo verifichi?
ledoriver (4630 points)
1 6 17
commented Jan 29, 2019 by ledoriver (4,630 points)

Così

def ricorsiva(n, l):
    zero = True
    for i in l:
        if i > n: # non si può ottenere n con quel numero
            zero = True
        else:
            if n%i == 0:
                zero = False
                break # non serve controllare gli 'i' futuri
            else:
                if ricorsiva(n-i, l): # <-- tutti i casi possibili
                    zero = False
    if zero:
        return 0
    else:
        return 1

def es10(lista1, lista2):
    lista3 = []
    
    for n in lista1:
        lista3.append(ricorsiva(n, lista2))
    
    return lista3

1
1824194 (1040 points)
3 15 23
answered Jan 29, 2019 by 1824194 (1,040 points)
un'idea potrebbe essere quella di fare la divisione col resto tra gli elementi della prima lista e gli elementi della seconda. O vedi se sono divisori l'uno dell'altro e aggiungi 1 alla lista risultato) o vedi se il resto della divisione dà 1 (ossia aggiungi 0) oppure vedi se sommando tot volte il numero della lista 2 in questione, puoi ottenere un resto pari ad un altro elemento della lista.Il 23 e il 28 si ottengono con più somme: tipo 28 diviso 5 dà resto 3 che non è 1 e allora 5+5=10 e 28 diviso 10  che dà resto 8 che non è 1 ed è ancora più piccolo di 13 che è l'altro della lista, 5+5+5=15 e 28 diviso 15 dà resto 13 che è nella lista e allora inserisci 1 nella lista
_andrea_ (45670 points)
2 40 297
answered Jan 29, 2019 by _andrea_ (45,670 points)
Puoi provare così: passi aa funzione ricorsiva un n e una lista. n inizialmente è il numero di cui verificare se si può comporre, e la lista è sempre la stessa. Ora iteri sui numeri della lista: se ne trovi uno divisore di n ritorni 1 (ma attento, così rischi di non entrare mai in ricorsione!) Se ne trovi uno maggiore vai avanti, se ne trovi uno minore, k, richiami la ricorsione su n-k. Avanti così finché non trovi n nella lista. Allora metti 1 per quell'n