Progettare la soluzione ricorsiva

Naviga le tue risposte
2

Capisco la ricorsione e la trovo utile e intuitiva mentre risolvo i problemi sugli alberi ma per molti altri problemi la ricorsione non mi impedisce di lasciarmi perplesso. Recentemente stavo risolvendo il seguente problema:

Write a recursive function that counts how many different ways you can make change for an amount, given a list of coin denominations.

Dopo aver provato a fondo e un po 'su Google ho trovato la seguente soluzione e pensarci nei dettagli mi fa girare la testa . 

function isEmpty(coins) {
  return coins.length === 0;
}

function allButFirst(coins) {
  return coins.slice(1);
}

function countChange(money, coins) {
  if (money === 0) return 1

  else if (money > 0 && !isEmpty(coins)) {
    return countChange(money - coins[0], coins) +
      countChange(money, allButFirst(coins));
  }

  else // money < 0
    return 0;
}

console.clear();
console.log(countChange(4, [1, 2])); // 3 (1+1+1+1), (1+1+2), (2+2)

AFAIK, il primo passo nella soluzione ricorsiva è verificare se la struttura sottostante è ricorsiva e nel mio caso sì. Ma io sono lì una sorta di principio del modello mentale o qualcosa che potrebbe aiutare a progettare una soluzione del genere, anche qualcosa che potrebbe impedirmi di andare nella direzione sbagliata funzionerebbe?

    
posta CodeYogi 05.08.2016 - 19:20
fonte

2 risposte

1

Qui ci sono due problemi:

  1. Apporta le modifiche per una determinata situazione e,
  2. Permuta la situazione data per trovare altre risposte.

Questi due aspetti rendono le cose piuttosto confuse. Quindi, dovrai davvero provare a tenere separati questi problemi.

La prima cosa che dovresti cercare di capire che il risultato di ogni chiamata o livello della soluzione che stai cercando è un insieme o una serie di risposte, piuttosto che una singola risposta, a causa dei requisiti di permutazione.

Se hai scomposto la parte delle permutazioni, la risposta risultante è un insieme di monete per taglio, quindi già con una sola risposta migliore, hai un tipo di risultato che è un insieme di coppie. Quando poi calcoli le permutazioni, hai una matrice di questi insiemi.

Quindi, una soluzione dovrebbe rendere forse la migliore risposta possibile (quantità di cambiamento) per la situazione, e quindi anche permutare la situazione in modo che possa apparire un'altra risposta. Vorrei dire che questi finirebbero come parti diverse del codice. Ad esempio, quando attraversi un albero ("in ordine"), inizi: (1) attraversa a sinistra, quindi (2) lavora da solo, quindi (3) attraversa a destra. Ciascuno di questi passaggi è chiaramente visibile come distinto l'uno dall'altro nel codice.

Infine, le permutazioni devono limitare la quantità di monete di ogni tipo altrimenti, non penso che riuscirai a colpire tutte le permutazioni. Quindi, l'input deve descrivere denominazioni e sia quantità infinita sia quantità limitata. Quindi una permutazione può limitare la quantità prima, quindi limitare solo le denominazioni (che naturalmente diminuiscono dalla quantità diventando limitata a zero).

In breve, devi esaminare seriamente il tipo o la forma del risultato che ti aspetti per un tale problema e, come dire per il tipo o la forma dell'input che stai fornendo.

(Inoltre, stai lavorando in una lingua che ha un'assistenza di tipo limitata, mentre se fossi in C # o Java riceverai un buon aiuto dal linguaggio e dal compilatore sui tipi corretti.)

    
risposta data 05.08.2016 - 19:42
fonte
0

Il modo di creare un algoritmo ricorsivo è il seguente ...

Prima scrivi una funzione che risolva il caso più semplice. Quindi risolvi il caso più semplice prima riducendolo al caso più semplice e poi chiama di nuovo la funzione per il caso più semplice.

Supponi per questo problema che le monete siano nelle denominazioni 1, 5, 10, 25.

Quindi scrivi prima una funzione che restituisce tutti i modi in cui è possibile apportare modifiche a 0 e gli errori in qualsiasi altra situazione. (Il cambiamento per 0 sarebbe, ovviamente, una serie vuota di monete.)

Quindi cambia la funzione in modo che possa apportare modifiche per 1, quindi 2, quindi 3, fino a 4. (In ogni caso, c'è una sola soluzione, un singolo array di 1 che somma l'importo inviato.

Quindi il primo interessante ... Apporta il cambiamento per 5, qui la funzione dovrebbe produrre due array. Uno contenente [5] e l'altro contenente [1] + makeChange (4).

Il prossimo interessante ... Fai il cambiamento per 10. Ora dovrebbe tornare [[10], [5] + makeChange (5), [1] + makeChange (9)]

E così via ...

    
risposta data 06.08.2016 - 03:14
fonte

Leggi altre domande sui tag

Esiste un modo multipiattaforma per aprire una connessione TCP, inviare una richiesta di posta HTTP e mantenere aperta la connessione? Come posso filtrare il mio sistema di coordinate?