[C++] Problema scrittura algoritmo

[Mrhide1]

Buonasera a tutti,
ho un problema con la scrittura dell'algoritmo di questo programma e volevo avere qualche consiglio per capire come impostare il programma: dato un file in cui è presente una sequenza di interi di lunghezza INDEFINITA, devo scrivere un programma che trovi i numeri che si ripetono e le occorrenze di questi numeri e scrivere su un secondo file contenente su ogni riga la coppia numero - occorrenze
Esempio:
File 1: 12 34 56 1 12 34 60 12 4

File 2:
12 3
34 2

Per la scrittura dell'algoritmo ho alcuni dubbi. Il primo è che non so come ragionare per la comparazione in quanto ci sono più elementi che ripetono,fosse stato uno solo avrei comparato questo con ogni posizione del vettore e incrementato il contatore delle occorrenze in caso di uguaglianza, ma già per dire con due numeri che si ripetono non so come fare.Il secondo dubbio riguarda invece un possibile soluzione, in pratica avevo pensato di comparare la posizione i-esima con ciascuna posizione successiva ma chiaramente il problema sorge con le posizioni precedenti. Ultimo dubbio era riguardante il file 2 che non so se utilizzare una struct oppure graficamente facevo in modo di stampare i numeri che si ripetevano e a fianco le occorrenze.

[torn24]

Premetto che sicuramente ci sono soluzioni migliori, ma vorrei proporti come risolverei io il problema.

Per trovare l'occorrenza di un numero, scorriamo l'array e verifichiamo se troviamo numeri uguali.


Ora per il problema specifico, trovare tutte le occorrenze, procederei cosi.

1) Mi creo un array di appoggio dove inserisco i numeri che prendo in considerazione.

2) Prendo il primo elemento della sequenza, e lo inserisco nel'array di appoggio
3)Scorro la sequenza, e verifico le occorrenze.
4) Prendo il secondo elemento della sequenza, verifico che non sia contenuto nel'array di appoggio, se non è contenuto "non è mai stato preso in considerazione quel numero",lo salvo nel'array, procedo a scorrere la sequenza e verifico le occorrenze.

5) Questo fatto per ogni elemento della sequenza di numeri . il confronto deve avvenire dalla posizione dell' elemento, ossia 3 elemento, confronto da posizione 3 a fine sequenza, perché i numeri precedenti sono stati già confrontati.

Visto che non parla di uso di struct, io salverei file2, con un testo.

Numero 12 occorrenze 3
Numero 4 occorrenze 2
....
....

[Scara95]

Puoi utilizzare parte del counting sort.
Se sei pigro puoi utilizzare un hashing table al posto di un array di dimensione max-min+1, perderai l'ordinamento crescente dei numeri ma per il problema non è rilevante.

[Mrhide1]

Premetto che sicuramente ci sono soluzioni migliori, ma vorrei proporti come risolverei io il problema.

Per trovare l'occorrenza di un numero, scorriamo l'array e verifichiamo se troviamo numeri uguali.


Ora per il problema specifico, trovare tutte le occorrenze, procederei cosi.

1) Mi creo un array di appoggio dove inserisco i numeri che prendo in considerazione.

2) Prendo il primo elemento della sequenza, e lo inserisco nel'array di appoggio
3)Scorro la sequenza, e verifico le occorrenze.
4) Prendo il secondo elemento della sequenza, verifico che non sia contenuto nel'array di appoggio, se non è contenuto "non è mai stato preso in considerazione quel numero",lo salvo nel'array, procedo a scorrere la sequenza e verifico le occorrenze.

5) Questo fatto per ogni elemento della sequenza di numeri . il confronto deve avvenire dalla posizione dell' elemento, ossia 3 elemento, confronto da posizione 3 a fine sequenza, perché i numeri precedenti sono stati già confrontati.

Visto che non parla di uso di struct, io salverei file2, con un testo.

Numero 12 occorrenze 3
Numero 4 occorrenze 2
....
....

ora ci provo e vedo se trovo problemi. Un altro dubbio che avevo riguardava però l'allocazione dinamica del vettore di dimensione indefinita, è corretto scrivere così?

int main (){
	int riemp = 0;
	int *vet;
	vet = new int [riemp];
	
    fstream file;
    file.open ("dati.txt",ios::in);
    if(!file)
    {
    	cout << "errore apertura file!!!";
    }
	
	while (!file.eof())
	{
		file >> vet[riemp++];
		
	}
	
	
	for (int i=0;i< riemp ;i++)
	cout << "  "<< vet[i];
	
	system("pause");
}

[Scara95]

No, perché l'array ha come dimensione quella con cui viene creato.

[Scara95]

Comunque è sia più semplice che più efficiente fare come ho detto io...

[Mrhide1]

Strano eppure me lo stampa correttamente l'array,in tal caso come si scrive l'allocazione dinamica? Comunque io non ho mai usato il counting sort,quindi non so come applicarlo al mio problema in un certo senso.

[Mrhide1]

allora per il momento mi sono messo in condizioni "comode" cioè ho scelto questo array: 1 2 1, e ho impostato vet2 di lunghezza 1 per il momento. Tuttavia non mi stampa nulla.il codice è questo:

int cont = 0;
int j = 0;


while (j < riemp)	{
	  for (int i=j;i<riemp;i++)
	  {
		vet2[j] = vet1[i];
		if (vet2[j]==vet1[i+1])
		cont++;
		if (i==riemp)
		{
		  j++;
	    }
	  }	
	  
	  
	}

in sostanza avevo pensato che con un while avrei potuto confrontare l'elemento dell'array d'appoggio in questione con tutta la sequenza e non appena la prima comparazione fosse terminata aumentavo l'indice dell'array d'appoggio,passando all'elemento successivo e così una nuova comparazione con la sequenza.

[Scara95]

Puoi usare il template vector nella libreria standard?

[Mrhide1]

Per mia sfortuna no poichè non l'abbiamo mai trattato a lezione,anche se da come ho capito sarebbe molto utile ma purtroppo devo usare nei miei programmi solo quello che abbiamo studiato in classe.