Algoritmo ricorsivo per selezionare numeri ascendenti non contigui da una lista

Question

Ho bisogno di scrivere una funzione che trovi la sottodimensione ascendente più lunga, non necessariamente contigua, in una lista di numeri. La funzione deve essere ricorsiva.

Ho un problema con il mio algoritmo e non riesco a capire come risolverlo. Ecco un esempio Lista di partenza:

[88, 1, 22, 3, 34, 6, 54, 9, 19]

Il risultato corretto è:

[1 , 3, 6, 9, 19]

e voglio stampare sullo schermo la lunghezza di questa sub-sequenza, in questo caso, 5.

La mia funzione:

int subseires(int arraysub[], int small, int i, int j, int coun){ 
    if(i==size) return 0; 

    if(arraysub[i]>arraysub[j]) 
     subseires(arraysub, small, i+1, j+1, coun); 

    if(arraysub[i]<arraysub[j]) 
     subseires(arraysub, small, i, j+1, coun+1); 

    return coun; 
} 

Can

chiunque aiutare sottolineando i problemi con la mia procedura?

Answer 1

L'algoritmo è probabilmente errato.

Quello che devi fare è per ogni membro della aray, se puoi selezionarlo (non è inferiore a quello precedente che hai selezionato) quindi controlla due opzioni in modo ricorsivo: selezionarlo o non selezionarlo. In questo modo si va fino alla fine della matrice e si restituisce la lunghezza totale. Alla fine stampi la lunghezza più lunga.

Provare ad implementare questo algoritmo in una funzione C.

Answer 2

Quindi è sufficiente stampare la lunghezza dell'elenco, non la lista stessa? Questo aiuta, perché semplifica la gestione della memoria (che è un problema per c).

Questa è davvero solo una ricerca glorificata. In ogni punto è necessario conoscere (1) il valore corrente (se presente); (2) la lunghezza corrente (se presente); (3) la posizione nell'elenco; (4) la più grande lunghezza conosciuta. L'utilizzo di una lunghezza pari a zero aiuta a tracciare quando non si ha un valore corrente (quindi non è necessario un valore iniziale "magico"). Il valore di ritorno dovrebbe essere la lunghezza maggiore.

Su ciascuna ricorsione è possibile saltare il numero corrente o includerlo nell'elenco (ma solo se è inferiore al valore corrente).

modo che il codice è solo:

 
#include <stdio.h> 

int max(int a, int b) { 
    return a > b ? a : b; 
} 

int find(int* data, int total_length, int offset, int previous, 
     int run_length, int max_length) { 
    // update max length if it has improved          
    if (run_length > max_length) max_length = run_length; 
    // if we are at the end, return max           
    if (offset == total_length) return max_length; 
    // if the current value is too small, we cannot include it      
    if (run_length && data[offset] <= previous) 
    return find(data, total_length, offset+1, previous, run_length, max_length); 
    // otherwise, we want the best of either including it or not     
    return max(
    // try including it               
    find(data, total_length, offset+1, data[offset], run_length+1, max_length), 
    // try excluding it               
    find(data, total_length, offset+1, previous, run_length, max_length)); 
} 

// test                   
int main(int argc, char *argv) { 
    int data[] = { 88, 1, 22, 3, 34, 6, 54, 9, 19 }; 

    printf("%d\n", find(data, 9, 0, 0, 0, 0)); 
    return 0; 
} 
 

ovviamente questo è il codice terribile c (non perché non ho usato l'inizializzazione array, che qualcuno "gentilmente" fisso (anche se non si sono preoccupati di votare questo risposta - Immagino che ritengano di essere motivato a postare qui imparando dalla loro profonda conoscenza della sintassi C) ma perché usa lo stack di chiamate dove sarebbe più efficiente usare una struttura di memoria separata).

(anche, devo dire, scrivere qualcosa del genere è molto più facile come una funzione ricorsiva che come farlo in un ciclo, perché basta scrivere ciò che vuoi che succeda - se tu avessi un ciclo allora dovresti è necessario preoccuparsi di cambiare i valori e resettarli e tutto quel caos. Il problema è che abusa in modo orribile dello stack).

Answer 3

La funzione ricorsiva è necessario sarà simile a questa

void dfs (int curr, int length){ 
    if (length > max)max = length; 
    if (curr >= index) 
     return ; 
    for (int I=curr+1;I <= index; I++){ 
     if (array[I] >= array[curr]){ 
      dfs (I, length+1); 
     } 
    } 
} 

Qui array [] è matrice intera. I numeri sono riempiti con l'indice 1 per l'indice n. 'curr' è l'indice corrente e 'length' è la lunghezza della sub-sequenza massima con numeri ascendenti. 'max' è il massimo di tale lunghezza. Per calcolare la lunghezza si dovrebbe chiamare

dfs(0, 0); 

Per un pieno di codice Java di lavoro: http://pastebin.com/H315si0K