[c] Algoritmo ricorsivo confronto numeri

[nasuka89]

Allora vorrei dei suggerimenti per l'impostazione di questo esercizio: " Implementare un algoritmo ricorsivo che, dato un array a di dimensione n, verifichi se esistono due numeri diversi i,j compresi nell'intervallo [0, n-1] tali che a[i]=j e a[j]=i". Grazie

[Who am I]

Sai qual'è il primo indice da cui partire (0), sai con che indice fermarti (n-1).
Oltre a capire la ricorsione non ci sono ulteriori requisiti necessari,quando l' hai studiata prova a scrivere il codice e vediamo se ci sono errori.

[nasuka89]

void algoritmo(int a[n]){

 int i,j;
 int trovato = 0; 


 j = 0;
 
  while( j != n){  

    for(i = 0; i < n-1 ; i++ ){
         
           
             if(a[i] == j && a[j] == i ){

                 trovato++;

              }

               
            if( trovato != 0){

                printf("I numeri cercati sono &d e %d", i, j);
                return; 

               }

          

         }

                     j++;
    }

                printf("Nessun risultato trovato");
                return; 
}

Per fare la ricorsione come faccio a richiamare la funzione se in input gli do solo l'array? cioè in teoria devo aumentare j e i ogni volta per cui dovrei passare anche questi in input?

[Scara95]

cannato in pieno, avevo capito un'altra cosa...

[Scara95]

Allora:

int algoritmo(int a[], int n);
int algoritmo_1(int trovati, int *a, int i, int n);
int algoritmo_2(int trovati, int *a, int i, int j, int n);

questi sono i prototipi delle funzioni ora:
la algoritmo viene chiamata da te e chiama algoritmo_1 inizializzando trovati e i a 0, algoritmo_1 richiama ricorsivamente se stessa finchè i < n, quando i == n ritorna trovati, ad ogni chiamata sostituisce trovati con trovati + la chiamata a algoritmo_2 e i con i+1;
algoritmo_2 viene chiamata con trovati e j inizializzati a 0 e richiama ricorsivamente se stessa finchè j < n, quando j == n ritorna trovati, ad ogni chiamata sostituisce trovati con trovati + 1 se la relazione fra i e j si verifica e j con j+1.

Ho scritto il codice e l'ho provato, è 16 righe con 3 di spazi e 3 di graffe (senza prototipi)...
Se hai problemi dimmi

[Who am I]

A parte il fatto che devi far ritornare un valore altrimenti la procedura sarebbe inutile (come faresti a capire se è vero o falso che c'è un elemento uguale ad un altro elemento?), il nome dovrebbe essere significativo. "algoritmo" non è indicativo di quello che la funzione vuole realmente fare.

Un esempio di prototipo:

bool ripetizione (int* a, int i, int n);
// bool si trova in stdbool.h, p un booleano (true o false)
// a è l' array
// i è l' indice dell' array che vuoi analizzare
// n è la dimensione massima dell' array

Allora puoi eseguire questo algoritmo:
- Se i è uguale a n ritorni false;
- Se invece i è minore o uguale a n-1, per ogni elemento j che va da 0 a n-1 controlli che ci sia un valore a[i] uguale a un valore a[j], se c'è un valore uguale ritorni true, se non c'è un valore uguale chiami ricorsivamente la funzione passando i+1 come parametro.

[Scara95]

Io ho seguito lo stesso schema della sua funzione e ho fatto esattamente quello che aveva fatto lui (come implementazione), apparte che per un if C le nostre due funzioni funzionerebbero comunque: 0 è false, qualsiasi valore è true...

[Who am I]

Ed è corretto però per non complicare le cose a nasuka89 suggerisco di fare una funzione unica come l' ho descritta nel mio post.

[Scara95]

Con il tuo schema introduci un ciclo while, quindi non si tratta solo di funzioni ricorsive, inoltre il mio sche può essere facilment riadattato per usare dei bool o una lista di strutture che contenga gli indici di questi valori appunto per come è stata strutturata.
Sempre riguardo le differenze: la tua soluzione risolve 2 problemi in una funzione, la mia si struttura in sottoproblemi: una funzione gestisce un'indice e l'altra gestisce l'altro.

Poi entrambe le soluzioni restano funzionanti e molto probabilmente ugualmente performanti:
Le mie funzioni sono tail recursive per come ho descritto l'implementazione...

[Who am I]

Non vado avanti a discutere perché non sarebbe giusto andare off-topic uteriormente, ma resto dell' idea che la mia proposta è più facilmente implementabile (e soddisfa la condizione di essere ricorsiva).