RISOLTO Eseguire ricerca in un algoritmo

[AxelR]

Ciao a tutti,
mi servirebbe una dritta!
In un un algoritmo in cui è presente un vettore composto da 12 numeri che saranno scelti casualmente tra un min di 38 e un massimo di 55, dovrei inserire un controllo di questi numeri che alla fine mi dia in output i numeri non presenti in quel vettore (quindi i numeri tra 38 e 55 non selezionati per popolarlo).
Io utilizzerò Flowgorithm per creare questo algoritmo.
Grazie mille.

 

[Moffetta88]

Ok, hai bisogno un flowchart quindi...
Tu fin dove sei arrivato? perchè qui sul forum non facciamo i compiti agli altri, ma aiutiamo

 

[AxelR]

Ciao! Si esattamente.
Sono arrivato, una volta fatte le varie dichiarazioni, a popolare il vettore con il criterio di cui sopra,
Poi mi sono perso nel cercare di trovare un criterio con cui effettuare la verifica.
Allego le immagini del diagramma per com'è ora.
Grazie

 

[AxelR]

Inserisco la richiesta completa dell'esecuzione dell'algoritmo:
- Realizzare un vettore di dimensione 11 con numeri casuali interi compresi tra 38 e 55 e visualizzare il vettore in output: e questo credo sia corretto quanto ho scritto;
- Visualizzare in output i numeri non presenti nel vettore (considerando i valori possibili tra 38 e 55): qui mi servirebbe una mano, in quanto non so bene come ricercare un numero in un vettore.
Ringrazio.

 

[DispatchCode]

- Visualizzare in output i numeri non presenti nel vettore (considerando i valori possibili tra 38 e 55): qui mi servirebbe una mano, in quanto non so bene come ricercare un numero in un vettore.

Ti rispondo a livello logico di algoritmo: è un tipo di problema che generalizzando puoi affrontare in due modi.

Su un insieme piccolo scorri da inizio a quando lo trovi (o alla fine, se non esiste) con il vettore di partenza. Scorri in un tempo lineare, avendo N elementi.

In caso di molti elementi il vettore lo si ordina. Ordinando è molto più comodo, se usi per esempio la ricerca dicotomica li guardi tutti in log base 2 di n (in pratica, dimezzi ogni volta, dovresti guardare l'algoritmo per capire che intendo, se non lo conosci).

Eg. se hai (53,41,45,44,57,39), lo ordini ottenendo (39,41,44,45,53,57). Supponiamo devi trovare 57.

Usando la ricerca dicotomica, dividi per due e inizi quindi da 44. 44 è minore di 57, quindi la parte a sx viene scartata, e il vettore che consideri sarà (45,53,57).
Dividi per 2 e prendi 53, che non è il valore che cerchi ed è minore. A questo punto vai ancora a dx e romani con 1 solo elemento che è anche quello corretto

Se ricerchi in maniera lineare banalmente scorri tutto da inizio a fine, appunto.

Non so se è quello che ti interessava capire però

 

[M1n021]

Implementando una sorta di tabella hash, il controllo diventa immediato.

 

[Hero467]

Si, tenete conto che sta usando flowgorithm. Adesso, io ho usato poco quel programma, ma dal poco che l'ho usato era molto limitato. Ed utilizzava una sintassi derivata dal c, quindi niente hash table

 

[M1n021]

Si, tenete conto che sta usando flowgorithm. Adesso, io ho usato poco quel programma, ma dal poco che l'ho usato era molto limitato. Ed utilizzava una sintassi derivata dal c, quindi niente hash table

Non conosco il programma in questione, ma alla fine per quello che intendo basta un semplice array di (55-38+1) elementi booleani inizializzati a 0. Nel momento in cui viene estratto un numero casuale basterà settare il corrispondente elemento dell'array a 1.

 

[ilfe98]

Inserisco la richiesta completa dell'esecuzione dell'algoritmo:
- Realizzare un vettore di dimensione 11 con numeri casuali interi compresi tra 38 e 55 e visualizzare il vettore in output: e questo credo sia corretto quanto ho scritto;
- Visualizzare in output i numeri non presenti nel vettore (considerando i valori possibili tra 38 e 55): qui mi servirebbe una mano, in quanto non so bene come ricercare un numero in un vettore.
Ringrazio.

Allora per farla davvero spiccia puoi fare anche così:
Crei il tuo vettore di 11 elementi, ed un vettore booleano di 17 elementi(55-38). Per ogni numero letto nel primo vettore inserisci un uno nella casella del secondo vettore:
Esempio leggi 38 vai ad inserire in posizione 38-38 (0) un uno. Poi leggo 45, quindi faccio 45-38=7. In posizione 7 inserisco 1. Alla fine gli 0 rappresentano i numeri non presenti.
È efficiente? No. Funziona? Sì. Ci sono altri modi? Assolutamente sì, ma questo è facilissimo e adatto ai beginner :)
Consiglio una lettura di hash table e trie

 

[M1n021]

Allora per farla davvero spiccia puoi fare anche così:
Crei il tuo vettore di 11 elementi, ed un vettore booleano di 17 elementi(55-38). Per ogni numero letto nel primo vettore inserisci un uno nella casella del secondo vettore:
Esempio leggi 38 vai ad inserire in posizione 38-38 (0) un uno. Poi leggo 45, quindi faccio 45-38=7. In posizione 7 inserisco 1. Alla fine gli 0 rappresentano i numeri non presenti.
È efficiente? No. Funziona? Sì. Ci sono altri modi? Assolutamente sì, ma questo è facilissimo e adatto ai beginner :)
Consiglio una lettura di hash table e trie

In pratica sono le stesse cose che ho detto io:

Implementando una sorta di tabella hash, il controllo diventa immediato.

.... alla fine per quello che intendo basta un semplice array di (55-38+1) elementi booleani inizializzati a 0. Nel momento in cui viene estratto un numero casuale basterà settare il corrispondente elemento dell'array a 1.

In ogni caso vale la pena precisare che gli elementi dell'array booleano devono essere 18 (55-38+1).

P.S.
Perché dici che non è efficiente?, Se parliamo di efficienza temporale (che a mio modo di vedere è l'unica di cui ha senso parlare in un contesto del genere), penso che sia impossibile fare di meglio...

 

[AxelR]

Ciao a tutti, ringrazio per le risposte!
Intanto preciso anche io che è circa una settimana che mi sono approcciato a questo mondo, quindi le mie basi sono pressochè nulle!
Quindi quanto proposto da ilfe98 nella mia testa ha un senso e l'ho capito, ora devo metterlo in pratica, però mi dovete un attimo guidare.

Vi riporto la prima parte codificata dal programma in C++, che magari vi risulta più comprensibile:

int main() {
srand(time(0)); //Seed random number generator

int v, min, a, c, num;
int vET[12];
int vETO[18];

a = 38;
for (v = 0; v <= 11; v++) {
vET[v] = rand() % 17 + 38;
}

for (c = 0; c <= 17; c++) {
vETO[c] = a;
a = a + 1;
}

Fino a questo punto ho creato un vettore intero di dimensione 11 e l'ho popolato con numeri casuali pescati dal range 38 - 55.
Poi ho creato un altro vettore intero di dimensione 18, nel quale sono andato ad inserire dal 38 al 55 in ogni posizione (non so bene se possa servire a qualcosa, nella mia idea serviva per termine di confronto).
Ora stando a quanto proposto. dovrei iniziare un vettore boleano simile al secondo, che leggendo un po' mi pare accetti sono true/false o 0/1 come valore, e in questo memorizzare la presenza/assenza del numero nel primo vettore.
Per farlo quindi dovrei mettere in confronto i due. facendo ciclare tutti i valore del primo per ogni valore del secondo, alla fine dove ho 0 vuol dire che quel numero non è presente nel primo vettore, giusto?
Ecco sarei un po' in difficoltà a mettere insieme il tutto, viste le mie scarse competenze! Portate pazienza!

 

[DispatchCode]

Rileggendo la richiesta mi sono accorto di averla letta male: ho letto la ricerca di 1 elemento nel vettore.
Ora riesco a dare una spiegazione alla vostra soluzione

Btw, il popolamento va bene, l'altro ciclo non ti serve.
La tabella booleana la riempi scorrendo il tuo array randomico.

L'array booleano lo inizializzi come:

int table[18] = {0};

Poi ti fai un ciclo sull'altro array (quello casuale). Quindi andrai a fare tipo 43-38=5. Questo sarà l'indice dell'array booleano da settare a 1.

Penso sia questo ciò che dicono sopra.

Invece di settarli a 0/1 potresti inizializzarlo con i nr del tuo range. Quando becchi un elemento lo metti a 0 in questa mappa.

Così come vantaggio hai che scorrendo ancora questo Array, tutti i valori >0 sono quelli non presenti nell'array.

Cambia poco, se usi 0/1 è comunque semplice risalirci.

 

[AxelR]

Ciao a tutti,
credo di essere arrivato alla risoluzione!
Dato che le mie conoscenze in merito (ripeto) sono limitate, mi sono concentrato su quello che so (e il concetto booleano ancora non mi è chiaro), per cui ho utilizzato gli operato basilari per mettere insieme la verifica.
Il risultato è questo, vi metto la codifica in C++, nel caso vi interessasse:

#include <iostream>
#include <sstream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <ctime>

using namespace std;

// Headers
string toString (double);
int toInt (string);
double toDouble (string);

int main() {
    srand(time(0));   //Seed random number generator
    
    int i, j, find, cont, num;
    int v[11];

    cont = 1;
    num = 1;
    for (i = 0; i <= 10; i++) {
        v[i] = rand() % 17 + 38;
        cout << "Il " << cont << "°" << " valore scelto è " << v[i] << endl;
        cont = cont + 1;
    }
    for (i = 38; i <= 55; i++) {
        find = 0;
        for (j = 0; j <= 10; j++) {
            if (v[j] == i) {
                find = 1;
            }
        }
        if (find == 0) {
            cout << "Il " << num << "°" << " valore non presente è " << i << endl;
            num = num + 1;
        }
    }
    return 0;
}

// The following implements type conversion functions.
string toString (double value) { //int also
    stringstream temp;
    temp << value;
    return temp.str();
}

int toInt (string text) {
    return atoi(text.c_str());
}

double toDouble (string text) {
    return atof(text.c_str());
}

 

[M1n021]

Alcune osservazioni:

- quelle funzioni sono inutili (infatti non le utilizzi) e di conseguenza anche alcune delle librerie che hai incluso;
- dal momento che i numeri casuali devono appartenere all'intervallo [38;55] la formula corretta da utilizzare è

rand() % 18 + 38

- nel momento in cui poni find=1 puoi anche uscire dal ciclo for con l'istruzione break;
- in ogni caso volendo seguire il tuo algoritmo farei qualcosa del genere:

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main()
{
    srand(time(0));

    const int MIN = 38;
    const int MAX = 55;
    const int DIM_1 = 12;
    const int DIM_2 = MAX - MIN + 1;

    int v[DIM_1];

    for(int i = 0; i < DIM_1; ++i)
    {
        v[i] = rand() % DIM_2 + MIN;
        cout << v[i] << " ";
    }
    cout << endl;
    for(int i = MIN, j; i <= MAX; ++i)
    {
        for(j = 0; j < DIM_1 && v[j] != i; ++j);
        if(j == DIM_1)
        {
            cout << i << " ";
        }
    }
}

- seguendo invece l'idea che ho proposto nei precedenti post:

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main()
{
    srand(time(0));

    const int MIN = 38;
    const int MAX = 55;
    const int DIM_1 = 12;
    const int DIM_2 = MAX - MIN + 1;

    int v[DIM_1];
    int u[DIM_2] = {0};

    for(int i = 0; i < DIM_1; ++i)
    {
        v[i] = rand() % DIM_2 + MIN;
        u[v[i] - MIN] = 1;
        cout << v[i] << " ";
    }
    cout << endl;
    for(int i = MIN; i <= MAX; ++i)
    {
        if(u[i - MIN] == 0)
        {
            cout << i << " ";
        }
    }
}

 

[bigendian]

ottimo, o anche in C

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

static int v[56];

int main()
{
        int i, c = 0;

        srand(time(0));

        do {
                i = rand() % 100;
                if (i < 38 || i > 55)
                        continue;
                v[i]++;
                c++;
        } while (c < 10);

        for (i = 38; i <= 55; i++) {
                if (!v[i])
                        printf("il numero %d non e' nella serie\n", i);
        }

        return 0;
}