+ Rispondi al messaggio
Visualizzazione dei risultati da 1 a 7 su 7

[C++] Ricerca binaria

  1. #1
    Nottambulo non  in linea Scolaretto
    Post
    322
    Like Inviati  
    0
    Like Ricevuti  
    0
    Sto preparando un piccolo compito dove devo utilizzare in maniera ricorsiva la ricerca binaria di una stringa. Il problema che la funzione restituisce vero se inserisco cile, quindi la prima parola dell'elenco che verifica, altrimenti sempre falso. Dove sbaglio?
    Grazie, ciao.

    #include <iostream>
    using namespace std;
    
    
    bool ricercaBinariaR(char *a[], int i, int j, char *x) {
      int m = (i + j) / 2;
        if (strcmp(a[m], x) == 0)return true ; // trovato
        else {
            if(strcmp(a[m], x) > 0) j = m - 1;
            else i = m + 1;
            if(i > j)return false; // non trovato
            else ricercaBinariaR(a, i, j, x);
        }
    }
    
    int main (int argc, char *argv[]) {
      if(argc != 2) {
        cout << "Uso: " << endl;
        cout << " ricercaBinariaI \"[stringa max 255 caratteri]\"" << endl;
        cout << " Il programma cerca in un'array di stringhe definita internamente" << endl
             << " la stringa specificata (tra apici) come argomento" << endl << endl;
        exit(1);
      }
      char ricerca[256];
      strncpy(ricerca, argv[1], 255);
      char *a[] = {
        "Argentina",
        "Bolivia",
        "Brasile",
        "Cile",
        "Colombia",
        "Equador",
        "Nicaragua",
        "Venezuela"
      };
      cout << (ricercaBinariaR(a, 0, 7, ricerca) ? "1" : "0") << endl;
    }
    

  2. #2
    L'avatar di bottomap
    bottomap non  in linea Amanuense
    Post
    4,130
    Like Inviati  
    0
    Like Ricevuti  
    0
    Ciao,

    Il problema piuttosto banale, e quello che hai scritto funzionerebbe a dovere, se tu non ignorassi le warning (che compilatore stai utilizzando? Ti dovrebbe riportare una warning che indica molto chiaramente quale sia il problema). Ricontrolla attentamente la funzione di ricerca... una cosa fondamentale nelle procedure ricorsive il ritorno dei valori al termine della stessa.

    Per il resto, quello che hai fatto case sensitive... se cerchi "cile" non lo troverai, se cerchi "Cile" invece si. Se il comportamento quello desiderato non c' niente da eccepire, altrimenti dovresti usare la versione case insensitive della strcmp (stricmp)
    ℹ️ Leggi di pi su bottomap ...

  3. #3
    Nottambulo non  in linea Scolaretto
    Post
    322
    Like Inviati  
    0
    Like Ricevuti  
    0
    Ciao, la funzione va benissimo case sensitive, so che il problema nel ritorno del valore e anche che qualcosa di banale, ma non riesco a capire il motivo. Al momento sto utilizzando DevC++ ( ho letto che non va bene, ma eclipse mi da problemi, prometto che lo sostituir) e ho provato anche con visual c++, ma non mi vengono date warning.
    Grazie, ciao

  4. #4
    L'avatar di bottomap
    bottomap non  in linea Amanuense
    Post
    4,130
    Like Inviati  
    0
    Like Ricevuti  
    0
    Ciao,

    Non possibile che non ti venga data una warning apposita... sicuramente lo deve fare MSVC, ma dovrebbe farlo qualsiasi altro compilatore. Hai per caso disabilitato le warning (o alcune di esse)? In caso non mai una buona idea...

    Visto che sai che il problema nel ritorno del valore, controlla accuratamente tutta la funzione (alla fine sono in tutto 10 righe) e verifica dove e quando la funzione ritorna o deve ritornare qualcosa... il problema non nel valore ritornato, proprio nel ritornare qualcosa o meno... nel tuo codice mancano in tutto 6 caratteri ed uno spazio...
    ℹ️ Leggi di pi su bottomap ...

  5. #5
    Nottambulo non  in linea Scolaretto
    Post
    322
    Like Inviati  
    0
    Like Ricevuti  
    0
    Grazie, trovato... manca un return, due giorni che ci picchio la testa!!! Pensavo che non servisse "return" quando richiamo la funzione

    Ora funziona:

    bool ricercaBinariaR(char *a[], int i, int j, char *x) {
      int m = (i + j) / 2;
        if (strcmp(a[m], x) == 0)return true ; // trovato
        else {
            if(strcmp(a[m], x) > 0) j = m - 1;
            else i = m + 1;
            if(i > j)return false; // non trovato
            else return ricercaBinariaR(a, i, j, x);
        }
    }
    
    Grazie, ciao

  6. #6
    L'avatar di bottomap
    bottomap non  in linea Amanuense
    Post
    4,130
    Like Inviati  
    0
    Like Ricevuti  
    0
    Ciao,

    Felice di sapere che hai risolto...

    Pensavo che non servisse "return" quando richiamo la funzione
    Questo un po'pi preoccupante... la necessit del return in questo caso specifico intimamente legata alla ricorsione ed al fatto che la funzione, nella sua interezza, ritorna un valore. Se il valore viene trovato al passo N, viene restituito il true... se il valore non viene mai trovato, verr restituito false, ma altrimenti deve essere restituito il valore calcolato al passo successivo.
    Il consiglio quindi di dare un'occhiata al concetto nel suo insieme... visto che ci hai perso due giorni, l'errore probabilmente di concetto, ed il caso di fugare eventuali dubbi prima di proseguire.
    ℹ️ Leggi di pi su bottomap ...

  7. #7
    Nottambulo non  in linea Scolaretto
    Post
    322
    Like Inviati  
    0
    Like Ricevuti  
    0
    Il consiglio quindi di dare un'occhiata al concetto nel suo insieme... visto che ci hai perso due giorni, l'errore probabilmente di concetto, ed il caso di fugare eventuali dubbi prima di proseguire.
    Sono d'accordo con te, ma purtroppo mentre cerco di ristudiare il c, linguaggio che purtroppo non uso da anni, il corso procede... una delle care conseguenze nel riprende gli studi dopo anni di fermo.

    Grazie dell'aiuto e della spiegazione.
    Ciao

+ Rispondi al messaggio

Potrebbero interessarti anche ...

  1. Risposte: 2
    Ultimo Post: 12-11-2020, 12:32
  2. [C] Function ricerca binaria ricorsiva
    Da mariano.monaco nel forum C/C++
    Risposte: 8
    Ultimo Post: 26-01-2012, 21:26
  3. Conversione binaria..
    Da artemis79 nel forum C/C++
    Risposte: 1
    Ultimo Post: 24-09-2009, 17:52
  4. Stringa binaria to Double
    Da adamsview nel forum Visual Basic 6
    Risposte: 0
    Ultimo Post: 01-04-2009, 12:19
  5. [C/C++] Sottrazione binaria
    Da programC__ nel forum C/C++
    Risposte: 5
    Ultimo Post: 20-09-2005, 10:09