Impostazione funzione ricorsiva

di
Nippolo
il
3 risposte
Nippolo
Nippolo
Molto attivo
Iscritto da
mar, 2018
Messaggi:
1241

Impostazione funzione ricorsiva

Ciao, ho un insieme di nodi collegati in vario modo tra di loro e in questa rete devo ricercare un ciclo (inteso come catena chiusa non ramificata) che rispetta delle precise condizioni.
Per farlo ho implementato una funzione ricorsiva. L'impostazione generale (molto semplificata) è la seguente:
int main()
{
    ...
    nodo x = ...
    vector<nodo*> ciclo {&x};
    if(sviluppa_ciclo(ciclo))
    {
        ...
    }
    ...
}

bool sviluppa_ciclo(vector<nodo*> &ciclo)
{
    for(nodo *current = ... ; ... ; current = ...)
    {
        if(CONDIZIONE_1)
        {
            ciclo.push_back(current);
            if(current == ciclo.begin())
            {
                if(CONDIZIONE_2)
                {
                    return true;
                }
            }
            else if(sviluppa_ciclo(ciclo))
            {
                return true;
            }
            ciclo.pop_back();
        }
    }
    return false;
}
Sembra funzionare, ma mi chiedevo se la ricorsione potesse essere impostata in maniera più semplice/compatta. Che dite?

3 Risposte

  • Nippolo
    Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi:
    1241

    Re: Impostazione funzione ricorsiva

    Ho modificato un po' il codice nella speranza di renderlo più chiaro.

    CONDIZIONE_1 ha lo scopo di verificare se il nodo corrente può far parte del ciclo.
    CONDIZIONE_2 invece ha lo scopo di verificare se il ciclo ottenuto sia valido.

    Detto ciò, quello che chiedo è se l'impostazione ricorsiva, intesa come la posizione della chiamata ricorsiva e dei return, possa essere scritta in maniera più semplice/compatta.
  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    6074

    Re: Impostazione funzione ricorsiva

    Problema 1: il 'pseudocodice' e' un algoritmo che non e' scritto in un particolare linguaggio di programmazione (C, Java,..) ma in un generico linguaggio di programmazione procedurale.

    Inoltre usa concetti della matematica (insiemi, sequenze, vettori,...) senza andare nel dettaglio della loro implementazione.

    Ma, cosa fondamentale, tale codice puo' essere convertito 1:1 in un vero codice funlzionante.

    il tuo 'pseudocodice' non lo e'

    problema 2: ci sono algoritmi efficienti per l'identificazione di cicli su grafi. la loro implementazione puo' essere fatta iterativamente o ricorsivamente, a piacere.

    dal tuo 'pseudocodice' non si capisce se stai usando uno di questi approcci o qualcosa di simile, o se l'algo va in ricorsione infinita.

    problema 3: fai un uso strano di vector: togli nodi dalla testa e li aggiungi in coda. questo vuol dire che potresti analizzare il nodo piu' volte.

    non c'e' motivo di analizzare un nodo di un grafo piu' di una volta. si analizza una volta soltanto. invece puo' essere confrontato con i nodi gia' analizzati e se e' gia' stato analizzato, hai trovato un ciclo

    quindi: boh!
  • Nippolo
    Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi:
    1241

    Re: Impostazione funzione ricorsiva

    In linea di massima so cosa si intende per pseudocodice, e ovviamente quello che ho postato non lo è.
    Semplicemente mi sono limitato a riportare in C++ lo schema generale della funzione ricorsiva che ho scritto (che è molto più articolata, con molti più controlli, etc...), nella speranza di rendere l'idea... se poi non ci sono riuscito mi dispiace.

    In ogni caso penso che l'idea di base dovrebbe essere abbastanza chiara: il for cicla tra i nodi, CONDIZIONE_1 verifica se il nodo corrente può far parte del ciclo e CONDIZIONE_2 verifica se il ciclo ottenuto sia valido.

    migliorabile ha scritto:

    problema 3: fai un uso strano di vector: togli nodi dalla testa e li aggiungi in coda. questo vuol dire che potresti analizzare il nodo piu' volte.
    Nel codice completo ci sono tutti i controlli affinché non vengano riprovate strade già percorse.
    Inoltre sia le aggiunte che le rimozioni avvengono entrambe in coda al vector ciclo, con lo scopo appunto di andare a sondare i vari percorsi possibili.
Devi accedere o registrarti per scrivere nel forum
3 risposte