Topic: ricorsione e alberi  (Letto 78 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline simone13

  • python unicellularis
  • *
  • Post: 11
  • Punti reputazione: 0
    • Mostra profilo
ricorsione e alberi
« il: Luglio 27, 2019, 16:45 »
buon pomeriggio,
avrei bisogno di un aiuto per risolvere il seguente problema:
ho una lista di interi, su questa lista devo sottrarre due elementi adiacenti  a,b solo se a>=b. il risultato andrà a sostituire i due elementi sottratti modificando la lista. devo scrivere una funzione che ritorni tutte le liste generate dalle possibili combinazioni di sottrazioni:
esempio:
ho la lista 19 -3 2 -10 -20
i risultati sarebbero (senza doppioni):
         [(10,), (30,), (50,),
        (10, -20), (20, 10), (22, 32), (30, -20),
        (19, -3, 32), (20, -10, -20), (22, 2, 10), (22, 12, -20),
        (19, -3, 2, 10), (19, -3, 12, -20), (22, 2, -10, -20),
        (19, -3, 2, -10, -20)]
non posso utilizzare nessun genere di libreria esterna.
il mio ragionamento era di considerare le possibili combinazioni come nodi di un albero, che ha radice la lista iniziale, e come figli le liste generate dalle possibili combinazioni, e di proseguire ricorsivamente fino a quando non posso più fare sottrazioni.
in questo caso l'albero avrebbe come radice (19, -3, 2, -10, -20) e come figli (19, -3, 2, 10), (19, -3, 12, -20), (22, 2, -10, -20) e ognuno di questi figli sarà padre delle combinazioni su questi ultimi. non riesco a scrivere questa funzione ricorsiva. qualcuno può aiutarmi?
grazie in anticipo :)

Offline RicPol

  • python sapiens sapiens
  • ******
  • Post: 2.870
  • Punti reputazione: 9
    • Mostra profilo
Re:ricorsione e alberi
« Risposta #1 il: Luglio 27, 2019, 17:52 »

Offline GlennHK

  • python sapiens sapiens
  • ******
  • Post: 1.654
  • Punti reputazione: 1
    • Mostra profilo
    • La Tana di GlennHK
Re:ricorsione e alberi
« Risposta #2 il: Luglio 29, 2019, 22:10 »
Inizia buttando giù una definizione formale dell'algoritmo che vuoi scrivere. Con la ricorsione aiuta molto.