[C] divide et impera

[Fabiuz]

Ciao raga, eccomi alle prese con un altro problema. Devo definire una funzione RICORSIVA esisteOK che determina se l'array contiene la sequenza ok, cioe' 'o' seguito da 'k'.

Il prototipo della funzione e`: int esisteOK(char v[], int inf, int sup) e devo utilizzare la tecnica ricorsiva del DIVIDE ET IMPERA!!!
ma non so come c.... si fa!!
cioè ho provato ma nn mi viene ! potete darci un occhio? grazie!

int esisteOK(char v[],int inf,int sup){
  int i,med,e1,e2;
  if (inf==sup)
    return 0;
  else if (inf!=sup)
  {
     med=(inf+sup)/2;
     if ((v[inf]=='o')&&(v[sup]=='k'))
       printf("\n");
       return 1;
  }
  else{ 
       e1=esisteOK(v,inf,med);
       e2=esisteOK(v,med+1,sup);
       if ((e1)>=(e2))
         return 1;
  }      
}

cosa sbaglio?? nn riesco mai a capire quale è il caso base!!!

grazie mille raga!

[marco_c]

il caso base sarà

if inf = (sup - 1)
(
if v[inf]=='o' AND v[sup]=='k'
hai trovato l'ok e esci
else
non hai trovato l'ok e esci
)
else
(
chiamate ricorsive
)

[Fabiuz]

gentilmente puoi spiegarmi perchè??

grazie Marco!!!

[Fabiuz]

allora ho riscritto il codice secondo le tue indicazioni ma pare che si blocchi e il disco continua a macinare per niente...!
ecco :

int esisteOK(char v[],int inf,int sup){
  int i,med,e1,e2;
  if (sup==-1){
   if ((v[inf]=='o')&&(v[sup]=='k'))
     return 1;
   else return 0;
  }
  else{ 
     med=((inf+sup)/2);
     e1=esisteOK(v,inf,med);
     e2=esisteOK(v,med+1,sup);
     if ((e1)>=(e2))
       return 1;
  }      
}

cosa cè adesso che non va??

[floyd]

hai messo un if e la funzione non ritornava il risultato se la condizione era falsa
med=((inf+sup)/2);
e1=esisteOK(v,inf,med);
e2=esisteOK(v,med+1,sup);
return e1 + e2;
dovrebbe funzionare, e1 e e2 sono o 0, 0 o 0, 1 o 1, 0

[Fabiuz]

no non funziona niente...io devo trovare la sequenza.. io per sequenza intendo 2 lettere attaccate (di posto i e i++ per capirci).

cosa sbaglio??

[floyd]

if (sup < inf+2) {
if ((v[inf]=='o')&&(v[inf+1]=='k'))
return 1;
else return 0;
}

[dekdek]

io devo trovare la sequenza.. io per sequenza intendo 2 lettere attaccate (di posto i e i++ per capirci).

Non e' cio' che hai scritto nel tuo programma: la 'o' la cerchi nell'estremo inferiore e la 'k' in quello superiore...

[anx721]

Questa dovrebbe funzionare:

int esiste_OK(char a[], int inf, int sup){
    if(sup <= inf)
        return -1;
    int med = (inf + sup) / 2;
    if((a[med] == 'o') && (a[med + 1] == 'k'))
        return med;
    int temp = esiste_OK(a, inf, med);
    if(temp > -1)
        return temp;
    return esiste_OK(a, med + 1, sup);
} 

bada che non restituisce 0 o 1 ma ti dà l'indice della posizione dela prima occorrenza trovata di "ok", mentre dà -1 se "ok" non è presente, così puoi verificare meglio se lavora correttamente. Bada inoltre che va invocata come esiste_OK(a, 0, 20) se l'array 'a' ha 21 posizioni.

[Fabiuz]

si ma io devo usare il divide et impera (o Command and Conquer come lo vuoi chiamare....) e cosi in quel modo non posso confrontare i risultati delle due metà degli array! Purtroppo....


miii perchè non mi funge ancoraa???
nella maniera che ho avevo fatto io il pc si impalla e non capisco perchè......................