[RISOLTO] Il programma funziona ma è scritto male (C++)

Fai una domanda Tutte le categorie
giuscri
giuscri
29 ago 2012, 13:21
NOTA: ho modificato il codice per renderlo un po' più leggibile. Spero ci sia riuscito.

Il programma che devo costruire deve contare quante volte ogni numero primo si ripete nella scomposizione degli interi da 2 a 100.

La scomposizione degli interi si trova in un file "preparato.dat". Il file è da leggersi come segue:

Numero da scomporre Numero di fattori
Primo fattore Molteplicità di questo fattore Secondo fattore Molteplicità di questo secondo fattore

Per esempio:

8 1
2 3

dove 8 è il numero da scomporre: ha un solo fattore (il 2) che si ripete per tre volte.

Questo è il codice che mi è venuto in mente ma mi sembra un poco macchinoso e non elegantissimo.

#include <iostream>
#include <fstream>

using namespace std;

struct coppia{

	int factor;
	int multeplicity;

};

void stampa(coppia*);

int i=0; // i sarà l'indice dei fattori caricati nel vettore

int main(){

	int number,n_factors;
	int prime,esponente;
	const int N=500;
	coppia v[N];
	
	for(int k=0;k<N;k++) v[k].multeplicity=0; //Inizializza a 0 v[k].multeplicity per ogni k
	
	ifstream ingresso;
	ingresso.open("preparato.dat");

	ingresso >> number >> n_factors;

	do{

	for(int j=0;j<n_factors;j++){ // Legge tanti fattori quanti ne dice la riga sopra

	ingresso >> prime >> esponente;

	// Il ciclo quì sotto verifica che il fattore non sia già stato caricato in v;

	for(int k=0;k<i;k++) if(v[k].factor == prime) {v[k].multeplicity++; esponente=-1; break;}

	// L'assegnazione di -1 ad esponente è un modo per usare l'if successivo: non sapevo come fare, altrimenti
	
	if(esponente!=-1) {v[i].factor=prime; v[i].multeplicity=esponente; i++;}

	}

	ingresso >> number >> n_factors;

	}while(!ingresso.eof());

	stampa(v);
	
	return 0;

}

//La funzione seguente stampa su ogni riga il fattore e la sua molteplicità;
void stampa(coppia* v) {for(int k=0;k<i;k++) cout << v[k].factor << " " << v[k].multeplicity << endl; return;}


Allego anche una parte del file "preparato.dat" nel caso fossi stato poco chiaro:


Grazie a tutti!

EDIT: in particolare mi chiedo: esiste un modo per far capire, in C++, che la riga è terminata? Avrebbe reso il compito molto più facile.
Risposte
claudio862
claudio862
29 ago 2012, 14:35
Il tuo codice è decisamente illeggibile. Ho provato a capire cosa fa ma non ci sono riuscito.
L'unica cosa che salta subito all'occhio è questa:

int N=500;
dato v[N];

È un errore, in C++ gli array devono avere una dimensione costante*, mentre N è una variabile. Le alternative sono (in ordine dalla peggiore alla migliore):
- dichiarare N con una direttiva del preprocessore (#define N 500):
- dichiarare N costante (const int N = 50;);
- usare un contenitore standard invece di un array (std::vector dato(50);).

* Alcuni compilatori come GCC permettono array di dimensione variabile, ma non è standard. Se usi GCC passa l'opzione "-std=c++98" (o c++11) per disabilitare estensioni non standard.

Per la tua ultima domanda, puoi leggere un'intera linea con std::getline():

std::string l;
std::getline(stream, l);
// Hai letto tutta una linea dentro la variabile "l".
// "l" non contiene il carattere '\n' (che però è stato letto dallo stream)

Per sapere se ci sono stati errori nella lettura puoi controllare lo stato dello stream:

std::string l;
std::getline(stream, l);
if (stream.fail()) {
    // La lettura è fallita, lo stream non conteneva una linea.
}

Funziona in generale, anche quando leggi un intero o altro con l'operatore >>.
Una volta che hai una stringa puoi creare un nuovo stream a partire da essa:

#include <sstream>
...
std::getline(stream, l);
std::istringstream stream2(l);
int n, n2;
stream2 >> n >> n2;



Quello che avrei fatto io è:

- Leggere tutte le fattorizzazioni (eventualmente salvarle in un elenco, ma non serve);
- Per ogni fattorizzazione, scorrere tutti i fattori;
- Ogni fattore F è un numero primo, e compare M volte dove M è la sua molteplicità;
- Incrementare di M il numero di volte in cui compare il numero F.

#include <iostream>
#include <fstream>
#include <string>
#include <map>

// Legge direttamente tutto da uno stream.
std::istream & operator>>(std::istream & stream,
                          std::map<int, int> & primes_with_times)
{
    // Finché riesce a leggere...
    while (stream.good()) {
        int n, n_factors;

        // Legge il numero e il numero di fattori.
        stream >> n >> n_factors;

        // Per ogni fattore...
        for (int i = 0; i < n_factors; ++i) {
            int factor, multeplicity;

            // ... legge il fattore e la sua molteplicità.
            stream >> factor >> multeplicity;

            // Se la mappa non contiene "factor", viene automaticamente inserito
            // ed inizializzato al valore di default (zero).
            primes_with_times[factor] += multeplicity;
        }
    }

    return stream;
}

// Legge le fattorizzazioni da un file.
std::map<int, int> read_primes(const std::string & filename)
{
    std::ifstream file;
    file.open(filename.c_str());

    std::map<int, int> primes_with_times;
    file >> primes_with_times;

    return primes_with_times;
}

// Scrive l'elenco dei numeri primi con il numero di volte in cui compaiono
// nelle fattorizzazioni.
std::ostream & operator<<(std::ostream & stream,
                          const std::map<int, int> & primes)
{
    for (std::map<int, int>::const_iterator pi = primes.begin();
         pi != primes.end();
         ++pi) {
        // L'iteratore di una mappa "punta" ad un std::pair<>, dove il primo
        // campo è l'indice della mappa e il secondo è il contenuto.
        const int number = pi->first;
        const int times = pi->second;
        stream << "Prime number " << number << " appears " << times << " times"
               << '\n';
    }

    return stream;
}

int main()
{
    std::map<int, int> primes_with_times = read_primes("./preparato.dat");
    std::cout << primes_with_times;
}
giuscri
giuscri
29 ago 2012, 17:16
"claudio86":
Il tuo codice è decisamente illeggibile. Ho provato a capire cosa fa ma non ci sono riuscito.
L'unica cosa che salta subito all'occhio è questa:

int N=500;
dato v[N];

È un errore, in C++ gli array devono avere una dimensione costante*, mentre N è una variabile. Le alternative sono (in ordine dalla peggiore alla migliore):
- dichiarare N con una direttiva del preprocessore (#define N 500):
- dichiarare N costante (const int N = 50;);
- usare un contenitore standard invece di un array (std::vector dato(50);).

* Alcuni compilatori come GCC permettono array di dimensione variabile, ma non è standard. Se usi GCC passa l'opzione "-std=c++98" (o c++11) per disabilitare estensioni non standard.


Per l'esame che sto preparando mi capita di avere a che fare con esercizi in cui devo caricare in un vettore una quantità imprecisata di dati. Solitamente scrivo qualcosa di simile a questo, quando mi trovo a dover memorizzare più di N dati:


if(i==N){ //dove i è il contatore degli elementi attualmente memorizzati nell'array

int *w=new int[N+allungo]; //dove 'allungo' è una variabile precedentemente dichiarata e inizializzata

copia(w,v); //una "void" che copia i valori del vecchio vettore in quello nuovo

v=w;

N+=allungo;

}


Se volessi dichiarare costante il valore di N, come potrei continuare ad usare array "dinamici", nel modo che ho scritto sopra?

Per la tua ultima domanda, puoi leggere un'intera linea con std::getline():

std::string l;
std::getline(stream, l);
// Hai letto tutta una linea dentro la variabile "l".
// "l" non contiene il carattere '\n' (che però è stato letto dallo stream)

Per sapere se ci sono stati errori nella lettura puoi controllare lo stato dello stream:

std::string l;
std::getline(stream, l);
if (stream.fail()) {
    // La lettura è fallita, lo stream non conteneva una linea.
}

Funziona in generale, anche quando leggi un intero o altro con l'operatore >>.
Una volta che hai una stringa puoi creare un nuovo stream a partire da essa:

#include <sstream>
...
std::getline(stream, l);
std::istringstream stream2(l);
int n, n2;
stream2 >> n >> n2;



Quello che avrei fatto io è:

- Leggere tutte le fattorizzazioni (eventualmente salvarle in un elenco, ma non serve);
- Per ogni fattorizzazione, scorrere tutti i fattori;
- Ogni fattore F è un numero primo, e compare M volte dove M è la sua molteplicità;
- Incrementare di M il numero di volte in cui compare il numero F.

#include <iostream>
#include <fstream>
#include <string>
#include <map>

// Legge direttamente tutto da uno stream.
std::istream & operator>>(std::istream & stream,
                          std::map<int, int> & primes_with_times)
{
    // Finché riesce a leggere...
    while (stream.good()) {
        int n, n_factors;

        // Legge il numero e il numero di fattori.
        stream >> n >> n_factors;

        // Per ogni fattore...
        for (int i = 0; i < n_factors; ++i) {
            int factor, multeplicity;

            // ... legge il fattore e la sua molteplicità.
            stream >> factor >> multeplicity;

            // Se la mappa non contiene "factor", viene automaticamente inserito
            // ed inizializzato al valore di default (zero).
            primes_with_times[factor] += multeplicity;
        }
    }

    return stream;
}

// Legge le fattorizzazioni da un file.
std::map<int, int> read_primes(const std::string & filename)
{
    std::ifstream file;
    file.open(filename.c_str());

    std::map<int, int> primes_with_times;
    file >> primes_with_times;

    return primes_with_times;
}

// Scrive l'elenco dei numeri primi con il numero di volte in cui compaiono
// nelle fattorizzazioni.
std::ostream & operator<<(std::ostream & stream,
                          const std::map<int, int> & primes)
{
    for (std::map<int, int>::const_iterator pi = primes.begin();
         pi != primes.end();
         ++pi) {
        // L'iteratore di una mappa "punta" ad un std::pair<>, dove il primo
        // campo è l'indice della mappa e il secondo è il contenuto.
        const int number = pi->first;
        const int times = pi->second;
        stream << "Prime number " << number << " appears " << times << " times"
               << '\n';
    }

    return stream;
}

int main()
{
    std::map<int, int> primes_with_times = read_primes("./preparato.dat");
    std::cout << primes_with_times;
}


Devo guardare con più calma queste righe perché non sono abituato all'operatore di risoluzione (si chiama così?). Ad ogni modo ti ringrazio.

Nota: ho aggiunto un po' di commenti nel codice scritto nel messaggio precedente. Spero si capisca di più. Grazie!
claudio862
claudio862
29 ago 2012, 20:04
"giuscri":
Per l'esame che sto preparando mi capita di avere a che fare con esercizi in cui devo caricare in un vettore una quantità imprecisata di dati. Solitamente scrivo qualcosa di simile a questo, quando mi trovo a dover memorizzare più di N dati:
[…]
Se volessi dichiarare costante il valore di N, come potrei continuare ad usare array "dinamici", nel modo che ho scritto sopra?

Sono due cose diverse.

int Nr = 40;
int * a = new int[Nr]; // Array dichiarato dinamicamente. N può essere
                       // un'espressione nota solo a runtime.

const int Nc = 40;
int b[Nc]; // Array dichiarato staticamente. N deve essere noto a compile time.

Il vincolo riguarda solamente gli array statici, quelli dinamici creati con l'operatore new[] possono avere dimensione nota a runtime.

Quello che mi sembra stia facendo tu in questo caso è:
- Allochi con new[] un array dinamico di N elementi;
- Quando leggi N elementi incrementi N e allochi un altro array, più grande;
- Copi il contenuto del vecchio array nel nuovo;
- * Deallochi il vecchio array con delete[].
- Usi il nuovo array.

* Non lo hai fatto nel codice che hai postato, ma è importante.

È esattamente quello che fa std::vector. A meno di scenari particolari (stai provando ad implementare la tua classe vector, oppure hai un professore che ti vieta di usare contenitori della libreria standard) dovresti usare std::vector (o simili).


"giuscri":
Devo guardare con più calma queste righe perché non sono abituato all'operatore di risoluzione (si chiama così?).

Gli operatori >> e << sono gli operatori di bit shifting.
Per tipi che non rappresentano numeri interi non hanno un particolare significato, per convenzione vengono usati per inserire / estrarre variabili dagli stream. Servono semplicemente per usare la sintassi stream >> variabile.
Se ti causano confusione trattali come semplici funzioni. Invece di:

std::istream & operator>>(std::istream & stream, Tipo & tipo)
{...}

...

Tipo t;
int a;
std::cout >> t >> a;

vedili così:

void estrai(std::istream & stream, Tipo & tipo)
{...}

...

Tipo t;
int a;
estrai(std::cout, t);
std::cout >> a;

Allo stesso modo per l'operatore <<.


"giuscri":
Nota: ho aggiunto un po' di commenti nel codice scritto nel messaggio precedente. Spero si capisca di più. Grazie!

È un po' più chiaro, ma quello che dovresti davvero fare è migliorare l'indentazione. Ad esempio la linea

for(int k=0;k<i;k++) if(v[k].factor == prime) {v[k].multeplicity++; esponente=-1; break;}

andrebbe indentata più o meno così:

for(int k = 0; k < i; k++) {
    if(v[k].factor == prime) {
        v[k].multeplicity++;
        esponente=-1;
        break;
    }
}

Inoltre, se ho capito l'algoritmo che stai usando (non mi è chiarissimo, forse faresti meglio a spiegarlo a parole), dovresti fare:

for(int k = 0; k < i; k++) {
    if(v[k].factor == prime) {
        v[k].multeplicity += esponente;
        esponente=-1;
        break;
    }
}
giuscri
giuscri
30 ago 2012, 00:37
"claudio86":
Inoltre, se ho capito l'algoritmo che stai usando (non mi è chiarissimo, forse faresti meglio a spiegarlo a parole), dovresti fare:

for(int k = 0; k < i; k++) {
    if(v[k].factor == prime) {
        v[k].multeplicity += esponente;
        esponente=-1;
        break;
    }
}


Si, assolutamente: ho fatto un po' di confusione. Provo a spiegare (ti ringrazio per la cortesia intanto):

devo contare quante volte ciascun fattore si ripete nella scomposizione dei numeri da 2 a 100. Dato che molti numeri primi si ripetono nella scomposizione degli interi in [2,100], prima di caricare un fattore con la sua molteplicità devo verificare se questo è già stato caricato: nel caso "v[k].multeplicity += esponente;".

Una delle questioni che mi lasciano perplesso è "esponente = -1;". Come posso scrivere che se il fattore NON compare fra quelli già caricati devo caricarlo ora?

L'idea è di assegnare, dentro l'if dedicato all'aggiunta di molteplicità per fattori già caricati, un valore "strano" ad 'esponente', di modo che sia chiarissimo che sono passato di lì.

Per questo soltanto se esponente!=-1 vado a caricare il fattore che ho appena letto, altrimenti leggo un nuovo fattore e ancora verifico se è già stato caricato, etc.

Mi pare macchinoso, però.

claudio862
claudio862
30 ago 2012, 10:22
Un modo appena migliore per evitare di impostare esponente=-1 è quello di usare una variabile bool.

do {

  ...

  bool appenaInserito = false;

  for(int k = 0; k < i; k++) {
    if(v[k].factor == prime){
      v[k].multeplicity += esponente; 
      
      appenaInserito = true;

      break;
    }
  }

  if(! appenaInserito) {
    v[i].factor = prime;
    v[i].multeplicity = esponente;
    i++;
  }

  ...
}


Un modo concettualmente più elegante è prima controllare se il fattore è presente, in caso contrario aggiungerlo, poi incrementarne la molteplicità.

do {

  ...

  bool presente = false;
  for(int k = 0; k < i; k++) {
    if(v[k].factor == prime){
      presente = true;
      break;
    }
  }
  if (!presente) {
    v[i].factor = prime;
    v[i].multeplicity = 0;
    i++;
  }

  // Ora sicuramente il fattore è presente nella lista.
  // Ora ne incremento la molteplicità.

  for(int k = 0; k < i; k++) {
    if(v[k].factor == prime){
      v[k].multeplicity += esponente;
      break;
    }
  }

  ...
}

Però così facendo scorri due volte la lista invece di una, peggiorando le prestazioni. Non si dovrebbe mai ottimizzare un pezzo di codice senza prima aver controllato che sia effettivamente utile farlo, ma in questo caso è anche poco elegante. Una soluzione è memorizzare la posizione del fattore una volta trovato.

do {

  ...

  int posizioneFattore;
  bool presente = false;
  for(int k = 0; k < i; k++) {
    if(v[k].factor == prime){
      presente = true;
      posizioneFattore = k;
      break;
    }
  }
  if (!presente) {
    v[i].factor = prime;
    v[i].multeplicity = 0;
    posizioneFattore = i;
    i++;
  }

  // Ora sicuramente il fattore è presente nella lista.
  // Ed è alla posizione "posizioneFattore".
  // Ora ne incremento la molteplicità.

  v[posizioneFattore].multeplicity += esponente;

  ...
}

Ora la lista viene scorsa una volta sola.


Oppure, potresti evitare queste ricerche usando direttamente un vettore. Invece di avere un vettore di coppie (fattore, molteplicità), potresti semplicemente memorizzare direttamente le molteplicità:

molt[0] = 0;
molt[1] = 0;
molt[2] = 16;
molt[3] = 8;
molt[4] = 0;
molt[5] = 3;
molt[6] = 0;
molt[7] = 2;
molt[8] = 0;
molt[9] = 0;
...

Il problema evidente è che la maggior parte degli elementi è inutilizzata (solo gli indici primi vengono usati). Ad esempio ci sono poco più di 1000 numeri primi nei primi 10000 numeri naturali, quindi il 90% della memoria sarebbe sprecata (e crescerebbe ancora di più per intervalli più grandi).


Infine, quello che dovresti davvero fare, è usare un array associativo, che in C++ è implementato dalla classe std::map.

// Associa ad un intero (fattore) un altro intero (molteplicità).
std::map<int, int> v;

// Molteplicità del numero primo "p": "v[p]", oppure "v.at(p)".

do {

  ...

  if (v.count(prime) == 0) {
    // Se il numero non è contenuto nell'array associativo, aggiungilo.
    v[prime] = 0;
  }

  // Ora sicuramente il fattore è presente nell'array associativo.
  v[prime] += esponente;

  ...
}

In questo modo l'array viene ancora scorso due volte invece che una, anche se le operazioni hanno complessità logaritmica e non lineare, quindi probabilmente è irrilevante.
Per completezza, ecco come si fa a scorrere l'array associativo un'unica volta (se non hai ancora visto gli iteratori probabilmente non ti sarà chiarissimo).

std::map<int, int> v;

do {

  ...

  // Prendi l'iteratore al fattore corrente. 
  std::map<int, int>::iterator position = v.find(prime);

  if (position == v.end()) {
    // Se l'iteratore è alla fine vuol dire che il fattore non è presente.
    // Inserisci una nuova coppia (fattore, 0) e salva l'iteratore.
    position = v.insert(std::make_pair(prime, 0)).first;
  }

  // Ora sicuramente il fattore è presente nell'array associativo.
  // Incrementa il valore puntato dall'iteratore.
  *position += esponente;

  ...
}
giuscri
giuscri
30 ago 2012, 11:22
"claudio86":
Una soluzione è memorizzare la posizione del fattore una volta trovato.

do {

  ...

  int posizioneFattore;
  bool presente = false;
  for(int k = 0; k < i; k++) {
    if(v[k].factor == prime){
      presente = true;
      posizioneFattore = k;
      break;
    }
  }
  if (!presente) {
    v[i].factor = prime;
    v[i].multeplicity = 0;
    posizioneFattore = i;
    i++;
  }

  // Ora sicuramente il fattore è presente nella lista.
  // Ed è alla posizione "posizioneFattore".
  // Ora ne incremento la molteplicità.

  v[posizioneFattore].multeplicity += esponente;

  ...
}

Ora la lista viene scorsa una volta sola.


Per ora prendo questo! Devo ringraziarti per il tempo e per la serietà che mi hai dedicato.

Mazel tov, a presto!

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.