-
uomoinverde.
User deleted
CITAZIONEBy starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.CODICETriangle 1:
-3-
-7- 4
2 -4- 6
8 5 -9- 3
That is, 3 + 7 + 4 + 9 = 23.
Find the maximum total from top to bottom of the triangle below:CODICETriangle 2
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
La richiesta dell'esercizio è quella di trovare, dato il triangolo, la strada che dalla cima al fondo dia la somma maggiore. Buon lavoro.
Suggerimento per una delle possibili soluzioni:SPOILER (clicca per visualizzare)È possibile suddividere il problema in sottoproblemi facilmente risolvibili?
. -
Guglielmoqwerty.
User deleted
CITAZIONE (uomoinverde @ 12/3/2014, 20:01)Suggerimento per una delle possibili soluzioni:SPOILER (clicca per visualizzare)È possibile suddividere il problema in sottoproblemi facilmente risolvibili?
Per l'aiutino: sì, è stata la prima cosa che mi è venuta in mente, ma non ne capisco l'utilità... (intendo una funzione ricorsiva con caso base il vertice).. -
uomoinverde.
User deleted
CITAZIONE (uomoinverde @ 12/3/2014, 20:01)Suggerimento per una delle possibili soluzioni:SPOILER (clicca per visualizzare)È possibile suddividere il problema in sottoproblemi facilmente risolvibili?
Per l'aiutino: sì, è stata la prima cosa che mi è venuta in mente, ma non ne capisco l'utilità... (intendo una funzione ricorsiva con caso base il vertice).
Trova un caso base che ti sia veramente utile, concordo sul fatto che considerare il vertice sia decisamente la cosa sbagliata.SPOILER (clicca per visualizzare)Prova a pensare concretamente quando scendi di un livello, ovvero quando hai scelto un numero per il tuo percorso: tra quali numeri puoi scegliere poi?. -
Guglielmoqwerty.
User deleted
CITAZIONE (uomoinverde @ 12/3/2014, 20:35)Trova un caso base che ti sia veramente utile, concordo sul fatto che considerare il vertice sia decisamente la cosa sbagliata.SPOILER (clicca per visualizzare)Prova a pensare concretamente quando scendi di un livello, ovvero quando hai scelto un numero per il tuo percorso: tra quali numeri puoi scegliere poi?
Ovviamente posso scegliere solo tra altri due numeri.
Ti spiego l'unica idea che mi è venuta, cosí mi confermi che sia sbagliata come penso:
Parto dall'alto e scelgo fra i due il numero massimo. Ma cosí rischio di perdere una strada di 99 se all'inizio ci sono due 00
Ps: mi sta venendo um dubbio, la soluzione parte dall'alto o dal basso?. -
.
Puoi scriverlo partendo dall'alto o dal basso. Dal basso è probabilmente più semplice, anche se meno performante.
Se trovo tempo e voglia, più tardi, o al più questa notte, vedo di scrivere qualche riga di codice ed applicare ciò che ho in mente.. -
.
@Guglielmoqwerty: partire dall'alto in quel modo ti porta certamente ad un esito negativo, in quanto non sai se il numero che c'è dopo è più grande o più piccolo della somma che hai sino ad ora. Se non ricordo male un implementazione come la tua si chiama "algoritmo goloso" (greedy, in inglese), in quanto scegli appunto la soluzione più buona (ma non tieni conto dei numeri che vengono dopo).
Io avrei una soluzione, ma non ho tempo per implementarla, quindi la descrivo solamente (sotto spoiler, così chi vuole leggerla la legge).SPOILER (clicca per visualizzare)Si inizia dal basso e si considera un piccolo triangolino formato da 3 numeri. Si effettua la somma di vertice + numero a sinistra, e quella di vertice è numero a destra. La somma maggiore viene inserita come vertice (poi posso eliminare la riga una volta fatti i calcoli (qui la elimino per chiarezza e comodità).
Uso il triangolo dell'esempio di PE:CODICE3
7 4
2 4 6
8 5 9 3
questo diventa quindi (8+2=10; e 5+2=7; quindi tengo 10, e così via):CODICE3
7 4
10 13 15CODICE3
20 19
Quindi 20+3 = 23.
Idee migliori al momento non ne ho.. -
uomoinverde.
User deleted
SPOILER (clicca per visualizzare)Io ho usato il tuo stesso approccio al problema, funziona bene.. -
Guglielmoqwerty.
User deleted
Che faccio la leggo? Perchè non ho assolutamente alcuna idea di come continuare.
Per facilitarmi un po' le cose posso chiedervi come inserireste i dati voi? Uno dei problemi che ho è appunto quello di non sapere come comportarmi davanti all'insieme dei dati e al come farli leggere al programma...
Idee?
. -
.
Ti rispondo così, su due piedi, in quanto non l'ho implementato...
Una soluzione potrebbe essere creare una struttura dati; l'altra usare una stringa e poi estrarre i dati poco alla volta.
Per quanto riguarda la soluzione, puoi anche leggere il mio spoiler. Ad ogni modo essendo un triangolo piccolo è risolvibile anche tramite forza bruta (provando tutte le combinazioni possibili quindi).. -
uomoinverde.
User deleted
Che faccio la leggo? Perchè non ho assolutamente alcuna idea di come continuare.
Per facilitarmi un po' le cose posso chiedervi come inserireste i dati voi? Uno dei problemi che ho è appunto quello di non sapere come comportarmi davanti all'insieme dei dati e al come farli leggere al programma...
Idee?
Puoi anche usare una matrice, date le modeste dimensioni!.
SoloPC [Tutto sui PC, Programmazione, Hacking, News, Grafica, e molto altro ancora!] 
Esercizi di programmazione
PE18 Maximum path sum I |
Contacts
Web