[C++] Problema scrittura algoritmo

[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.

[Mrhide1]

Eventualmente per l'allocazione dinamica va bene anche così? Se va bene almeno un dubbio l'ho tolto di mezzo. Ora cerco di interpretare la parte dell'algoritmo riguardante le comparazioni,perchè così a primo impatto non è che mi è proprio tutto chiaro e cerco di postare qualcosa di più simile possibile al tuo algoritmo.

#include <iostream>#include <fstream>




using namespace std;




void leggi (char *nome,int *vettore,int dim);
void stampa(int *vettore,int n);




int main ()
{
	
	char nome[30];
	cout<<"Inserisci nome file: ";
	cin>>nome;
	
	
	fstream file;
	int numeri;
	file.open(nome,ios::in);
	if(!file)
	{
		cout<<"File non trovato"<<endl;
	}
	
	
	 int dim=0;
/*	 while(!file.eof())
	 {
	 	file>>numeri;
	 	i++;
	 }
*/


	while (file>>numeri)
	dim++;
	
	
	cout << "La dimensione del vettore e': " << dim; 
	int *vettore;
	vettore = new int[dim];
	
	leggi(nome,vettore,dim);
	cout << "Il vettore stampato e': ";
    stampa(vettore,dim);
    
	file.close();
	cout << "\n\n";
	system("pause");
}










void leggi (char*nome,int *vettore,int dim)
{
	fstream file;
	file.open(nome,ios::in);
	if(!file)
	{
		cout<<"File non trovato"<<endl;
	}
	
	 
	 for(int i=0;i<dim;i++)
	{
	 	file>>vettore[i];
	}
		file.close();
		
			
	
	cout << "\n\n";
}




void stampa(int *vettore,int dim)
{
    for(int i=0;i<dim;i++)
	 {
	 	cout<< " | " << vettore[i]<< " | ";
	 }
		
    cout << "\n\n";
}

[Scara95]

Se ti va bene scorrere due volte il file sì

[Mrhide1]

Suppongo che per il mio livello principiante sia accettabile come cosa. Comunque del tuo codice non ho ben capito come collaborano insieme le funzioni int min,int max e void counts, cioè le prima due a cosa servono di preciso?

[Scara95]

Trova il minimo(massimo).
Scorre l'array tenendo sempre l'elemento più piccolo(grande).

[Mrhide1]

ah ecco ora ho capito che hai fatto, trovando il massimo e il minimo ti sei dato un range dei dati da gestire. Ti prometto che l'ultimo dubbio è non ti rompo più, non ho ben capito dove fai le comparazioni tra i vari numeri, dai tuoi commenti nel programma penso che il problema stia qua,inoltre questa notazione ++c non l'ho mai vista ad essere sincero.

for(int i = 0; i < v.length; i++) {        ++c[v.data[i]-mi];
    }

Ho notato inoltre che il programma che mi hai scritto ha un piccolo errore,in pratica mi aggiunge un numero in più alla sequenza esempio: 1 2 3 4 5. Quando eseguo il programma legge la sequenza 1 2 3 4 5 5 e perciò mi conta un numero in più che in realtà non c'è.

[Scara95]

ah ecco ora ho capito che hai fatto, trovando il massimo e il minimo ti sei dato un range dei dati da gestire. Ti prometto che l'ultimo dubbio è non ti rompo più, non ho ben capito dove fai le comparazioni tra i vari numeri, dai tuoi commenti nel programma penso che il problema stia qua,inoltre questa notazione ++c non l'ho mai vista ad essere sincero.

for(int i = 0; i < v.length; i++) {        ++c[v.data[i]-mi];
    }

Ho notato inoltre che il programma che mi hai scritto ha un piccolo errore,in pratica mi aggiunge un numero in più alla sequenza esempio: 1 2 3 4 5. Quando eseguo il programma legge la sequenza 1 2 3 4 5 5 e perciò mi conta un numero in più che in realtà non c'è.

++a è simile ad a++ l'unica differenza è che il primo fa l'incremento e poi restituisce il nuovo valore, mentre il secondo prima restituisce il nuovo valore e poi fa l'incremento. In quel contesto fanno esattamente la stessa cosa quindi, poiché il valore restituito non viene utilizzato.
Non c'è nessun compare perché ad ogni numero nel range corrisponde una casella nell'array che viene usata per contare le volte che appare (l'incremento di uno sta a significare che appare "una volta in più di prima").

Per quanto riguarda il problema in lettura, non ho fatto attenzione e ho preso il tuo codice dandolo per giusto. Il problema deriva dalla presenza di spazi a fine file, quindi non hai raggiunto l'eof ma ci sono ancora caratteri. Puoi risolvere così:

    int e;
    while (file >> e)    {
        push(v, e);
    }

[Mrhide1]

No scusami ho sbagliato io nell'impostare la domanda,la differenza la so tra le due notazioni,quello che non ho capito � come fa quella parte di codice che ti ho indicato a far girare tutto bene. Mi da l'impressione che dici se becco il numero v.data[i]-mi incrementa l'occorrenza nella casella dell'array relativo a quel numero quindi passa 0 a 1 per esempio. Ah che poi in sostanza con il range in input hai fatto un p� una furbata perch� se i numeri sono 1 2 3 256 in realt� il tuo range � di 256 numeri ma imponendo la condizione di stampare tutti i numeri che hanno numero di occorrenze diverso da zero hai eliminato tutti i numeri da 4 a 255.

[Mrhide1]

No scusami ho sbagliato io nell'impostare la domanda,la differenza la so tra le due notazioni,quello che non ho capito è come fa quella parte di codice che ti ho indicato a far girare tutto bene. Mi da l'impressione che dici se becco il numero v.data[i]-mi incrementa l'occorrenza nella casella dell'array relativo a quel numero quindi passa 0 a 1 per esempio. Ah che poi in sostanza con il range in input hai fatto un pò una furbata perchè se i numeri sono 1 2 3 256 in realtà il tuo range è di 256 numeri ma imponendo la condizione di stampare tutti i numeri che hanno numero di occorrenze diverso da zero hai eliminato tutti i numeri da 4 a 255.

[Scara95]

Ah che poi in sostanza con il range in input hai fatto un pò una furbata perchè se i numeri sono 1 2 3 256 in realtà il tuo range è di 256 numeri ma imponendo la condizione di stampare tutti i numeri che hanno numero di occorrenze diverso da zero hai eliminato tutti i numeri da 4 a 255.

Esattamente.
Hai letto la descrizione del counting sort?

Ha complessità O(n+m) dove n è il numero di dati in input e m l'ampiezza del range. Ovvero cresce linearmente su uno dei due.

L'algoritmo proposto nell'ultimo post ha complessità O(n^2), ovvero cresce quadraticamente sul numero di dati in input.

Quale è meglio? Dipende dal numero di dati in input, dalla memoria disponibile e dal range.

n=65536 è il limite in cui si incontrano le curve su un intero a 32 bit, ma è improbabile userai sempre tutto il range di interi.

Prendiamo ad esempio i numeri da 0 a 10000, basta n=100 a far incontrare le curve, un input di 100 numeri è meno che improbabile.