[C++] esercizio ok?
Devo fare l'esame di informatica per ingegneria meccanica e sto cercando di risolvere alcuni esercizi.
"Siano dati in ingresso due vettori V1 e V2 di numeri interi. Si supponga che entrambi i vettori siano disordinati. Scrivere un programma (in C++) che identifichi la più lunga sequenza di elementi ordinati del vettore V1 (denominata S1) e la più lunga sequenza di elementi ordinati del vettore V2 (denominata S2). Si provveda poi a scambiare tali sequenze: la sequenza S1 trovata nel vettore V1 deve essere inserita nel vettore V2 al posto della sequenza S2 e viceversa. Stampare infine i vettori V1 e V2."
Io l'ho risolto così:
Pare che funzioni, voi che dite? Grazie
"Siano dati in ingresso due vettori V1 e V2 di numeri interi. Si supponga che entrambi i vettori siano disordinati. Scrivere un programma (in C++) che identifichi la più lunga sequenza di elementi ordinati del vettore V1 (denominata S1) e la più lunga sequenza di elementi ordinati del vettore V2 (denominata S2). Si provveda poi a scambiare tali sequenze: la sequenza S1 trovata nel vettore V1 deve essere inserita nel vettore V2 al posto della sequenza S2 e viceversa. Stampare infine i vettori V1 e V2."
Io l'ho risolto così:
#include <iostream>
using namespace std;
int main() {
cout<<"Scegliere la dimensione del primo vettore:\n";
int dim1;
int dim2;
cin>>dim1;
cout<<"Scegliere la dimensione del secondo vettore:\n";
cin>>dim2;
int vett1[dim1];
int vett2[dim2];
int i;
for (i=0;i<dim1;i++)
{cout<<"Inserisci l'elemento numero "<<i+1<<" del primo vettore:\n";
cin>>vett1[i];
}
for (i=0;i<dim2;i++)
{cout<<"Inserisci l'elemento numero "<<i+1<<" del secondo vettore:\n";
cin>>vett2[i];
}
cout<<"Il primo vettore è:\n";
for(i=0;i<dim1;i++)
{cout<<" "<<vett1[i];}
cout<<"\nIl secondo vettore è:\n";
for(i=0;i<dim2;i++)
{cout<<" "<<vett2[i];}
//introduco il vettore lunghezza1 e indpar1 in cui memorizzare le lunghezze e gli indici di partenza delle serie trovate
int j1=-1; int lunghezza1[dim1]; int uno1=1; int k1=0; int indpar1[dim1];
//azzero i vettori lunghezza1 e indpar1
for(i=0;i<dim1;i++)
{lunghezza1[i]=0;}
for(i=0;i<dim1;i++)
{indpar1[i]=0;}
//memorizzazione di lunghezze e indici nelle componenti dei vettori
for(i=1;i<dim1;i++)
{
if(vett1[i-1]<vett1[i])
{j1++; lunghezza1[j1]=++uno1; indpar1[j1]=k1;}
else
{uno1=1; k1=i;}
}
//calcolo dell'elemento massimo e sua posizione
int massimo1; int posmax1=0;
massimo1=lunghezza1[0];
for(i=1;i<dim1;i++)
{
if(massimo1<lunghezza1[i])
{massimo1=lunghezza1[i]; posmax1=i;}
}
cout<<"\nLa sequenza crescente più lunga del primo vettore ha lunghezza "<<massimo1<<" e parte dalla posizione "<<indpar1[posmax1]+1;
cout<<"\nEssa è:\n";
for(i=indpar1[posmax1];i<indpar1[posmax1]+massimo1;i++)
{cout<<" "<<vett1[i];}
//Faccio la stessa cosa per il secondo vettore
int j2=-1; int lunghezza2[dim2]; int uno2=1; int k2=0; int indpar2[dim2];
for(i=0;i<dim2;i++)
{lunghezza2[i]=0;}
for(i=0;i<dim2;i++)
{indpar2[i]=0;}
for(i=1;i<dim2;i++)
{
if(vett2[i-1]<vett2[i])
{j2++; lunghezza2[j2]=++uno2; indpar2[j2]=k2;}
else
{uno2=1; k2=i;}
}
int massimo2; int posmax2=0;
massimo2=lunghezza2[0];
for(i=1;i<dim2;i++)
{
if(massimo2<lunghezza2[i])
{massimo2=lunghezza2[i]; posmax2=i;}
}
cout<<"\nLa sequenza crescente più lunga del secondo vettore ha lunghezza "<<massimo2<<" e parte dalla posizione "<<indpar2[posmax2]+1;
cout<<"\nEssa è:\n";
for(i=indpar2[posmax2];i<indpar2[posmax2]+massimo2;i++)
{cout<<" "<<vett2[i];}
//scambio le sequenze ordinate e mostro i risultati
cout<<"\nSostituendo la sequenza ordinata del primo vettore con quella del secondo, il primo vettore diventa:\n";
for(i=0;i<indpar1[posmax1];i++)
{cout<<" "<<vett1[i];}
for(i=indpar2[posmax2];i<indpar2[posmax2]+massimo2;i++)
{cout<<" "<<vett2[i];}
for(i=indpar1[posmax1]+massimo1;i<dim1;i++)
{cout<<" "<<vett1[i];}
cout<<"\nSostituendo la sequenza ordinata del secondo vettore con quella del primo, il secondo vettore diventa:\n";
for(i=0;i<indpar2[posmax2];i++)
{cout<<" "<<vett2[i];}
for(i=indpar1[posmax1];i<indpar1[posmax1]+massimo1;i++)
{cout<<" "<<vett1[i];}
for(i=indpar2[posmax2]+massimo2;i<dim2;i++)
{cout<<" "<<vett2[i];}
}
Pare che funzioni, voi che dite? Grazie
Risposte
In generale va molto meglio, ma ci sarebbero comunque alcune cose da aggiustare.
Innanzitutto conviene cambiare il nome alla variabile "max" in quanto rappresenta una funzione della libreria standard.
Ho dato un'occhiata veloce alla parte del main dedicata alla ricerca della sequenza più lunga e ho notato diversi problemi:
- ci sono più istruzioni per riga;
- visto che effettui le stesse operazioni su entrambi i vettori conviene ricorrere alle funzioni;
- se inserisci array con un solo elemento il programma non si comporta come dovrebbe;
- dal punto di vista logico credo di aver capito quello che cerchi di fare, ma se lo scopo è quello di identificare la lunghezza e l'origine della sequenza più lunga, ti stai complicando troppo la vita. A tal proposito dai un'occhiata al codice che ho postato in precedenza.
In ogni caso se proprio vuoi tener traccia di ogni sequenza (che se ho ben capito è lo scopo del tuo codice) e poi trovare quella più lunga, possiamo ragionare sul modo in cui rendere il codice più semplice e leggibile.
Innanzitutto conviene cambiare il nome alla variabile "max" in quanto rappresenta una funzione della libreria standard.
Ho dato un'occhiata veloce alla parte del main dedicata alla ricerca della sequenza più lunga e ho notato diversi problemi:
- ci sono più istruzioni per riga;
- visto che effettui le stesse operazioni su entrambi i vettori conviene ricorrere alle funzioni;
- se inserisci array con un solo elemento il programma non si comporta come dovrebbe;
- dal punto di vista logico credo di aver capito quello che cerchi di fare, ma se lo scopo è quello di identificare la lunghezza e l'origine della sequenza più lunga, ti stai complicando troppo la vita. A tal proposito dai un'occhiata al codice che ho postato in precedenza.
In ogni caso se proprio vuoi tener traccia di ogni sequenza (che se ho ben capito è lo scopo del tuo codice) e poi trovare quella più lunga, possiamo ragionare sul modo in cui rendere il codice più semplice e leggibile.
Effettivamente è molto cervellotico l'algoritmo per trovare le sequenze crescenti. A ogni passo io registro nelle componenti del vettore indpar e lung rispettivamente indice di partenza e lunghezza dell'eventuale sequenza crescente trovata. Darò un'occhiata al tuo codice per vedere come semplificare.
Per quanto riguarda la definizione di una matrice variabile, va bene così?
Per quanto riguarda la definizione di una matrice variabile, va bene così?
int nrighe; int ncolonne; cin>>nrighe; cin>>ncolonne; int* matriceprova=new int[nrighe][ncolonne];
No, non va bene, infatti se provi non compila.
Una matrice non è altro che un array bidimensionale, ossia un array di array. Quindi, detti "rig" e "col" rispettivamente il numero di righe e colonne della matrice, bisogna prima allocare una array di "rig" puntatori ad int e poi tramite un ciclo for allocare "rig" array di "col" int. Ovviamente così come un array di int è definito da un puntatore, così un array di puntatori ad int è definito da un puntatore a puntatore, ossia da un puntatore doppio.
Non dimenticare che una volta allocata, la memoria va anche deallocata.
In pratica bisogna fare una cosa del genere:
Una matrice non è altro che un array bidimensionale, ossia un array di array. Quindi, detti "rig" e "col" rispettivamente il numero di righe e colonne della matrice, bisogna prima allocare una array di "rig" puntatori ad int e poi tramite un ciclo for allocare "rig" array di "col" int. Ovviamente così come un array di int è definito da un puntatore, così un array di puntatori ad int è definito da un puntatore a puntatore, ossia da un puntatore doppio.
Non dimenticare che una volta allocata, la memoria va anche deallocata.
In pratica bisogna fare una cosa del genere:
//ALLOCAZIONE
int** matrice = new int*[rig];
for(int i = 0; i < rig; i++)
{
matrice[i] = new int[col];
}
//DEALLOCAZIONE
for(int i = 0; i < rig; i++)
{
delete[] matrice[i];
}
delete[] matrice;
Click sull'immagine per visualizzare l'originale
Buonasera, non mi funziona neanche dichiarando rig e col come suggerito da netbeans. Dichiarando rig e col esce questo:
Click sull'immagine per visualizzare l'originale
PS: Ho capito bisogna dare dei valori a rig e col altrimenti vengono assegnati valori casuali troppo grandi e la memoria si esaurisce.
Oggi ho fatto lo scritto, di seguito la traccia.
"Siano dati i ingresso i riempimenti e gli elementi di due matrici di interi M1 e M2 ed un valore intero K. Si provveda a calcolare, per ogni riga di M1, il valore minimo MIN ed il valore massimo MAX e si verifichi se esiste almeno una riga di M2 contenente K elementi inclusi nell'intervallo [MIN,MAX]. Se tale condizione risulta verificata, si provveda a copiare i K elementi trovati in un nuovo vettore allocato in MODO DINAMICO. Si provveda a stampare il vettore V e l'indice della riga di M2 trovata. Si organizzi il programma in sottoprogrammi.
Non ho fatto in tempo a finire tutto, comunque ho definito una matrice imatrice per l'input e una matrice omatrice per l'output allocandole come mostrato nel post precedente quindi in modo dinamico anche se il fatto che nella traccia è precisata l'allocazione dinamica per il vettore mi fa pensare che non fosse obbligatoria per le matrici. Poi ho richiesto il valore K e ho creato due vettori MIN e MAX nelle cui componenti sono contenuti i valori dei minimi e dei massimi per ogni riga, e quindi li ho mostrati a video. Basta, poi è scaduto il tempo. Non ho organizzato il programma in sottoprogrammi e non so neanche che significa. Il codice funzionava, secondo voi c'è la sufficienza? Mi interessa molto questo esame però ho anche altra roba da fare e sono indietrissimo, so che ho ampissimi margini di miglioramento ma un bel 18 lo accetterei volentieri XD. E comunque ci sarà anche una prova orale.
"Siano dati i ingresso i riempimenti e gli elementi di due matrici di interi M1 e M2 ed un valore intero K. Si provveda a calcolare, per ogni riga di M1, il valore minimo MIN ed il valore massimo MAX e si verifichi se esiste almeno una riga di M2 contenente K elementi inclusi nell'intervallo [MIN,MAX]. Se tale condizione risulta verificata, si provveda a copiare i K elementi trovati in un nuovo vettore allocato in MODO DINAMICO. Si provveda a stampare il vettore V e l'indice della riga di M2 trovata. Si organizzi il programma in sottoprogrammi.
Non ho fatto in tempo a finire tutto, comunque ho definito una matrice imatrice per l'input e una matrice omatrice per l'output allocandole come mostrato nel post precedente quindi in modo dinamico anche se il fatto che nella traccia è precisata l'allocazione dinamica per il vettore mi fa pensare che non fosse obbligatoria per le matrici. Poi ho richiesto il valore K e ho creato due vettori MIN e MAX nelle cui componenti sono contenuti i valori dei minimi e dei massimi per ogni riga, e quindi li ho mostrati a video. Basta, poi è scaduto il tempo. Non ho organizzato il programma in sottoprogrammi e non so neanche che significa. Il codice funzionava, secondo voi c'è la sufficienza? Mi interessa molto questo esame però ho anche altra roba da fare e sono indietrissimo, so che ho ampissimi margini di miglioramento ma un bel 18 lo accetterei volentieri XD. E comunque ci sarà anche una prova orale.
Ci sono diversi punti dell'esercizio che non sono specificati, come la modalità in cui tali matrici siano passare in input al programma o come debbano essere allocate. Non posso affermare se questi punti siano effettivamente liberi all'interpretazione dello studente o se l'insegnante si aspetti qualcosa di particolare che non ha però specificato chiaramente. Queste sono cose che si possono conoscere solo entrando in contatto con il professore o dalle esercitazioni. L'allocazione della matrice come nel post precedente (nella seconda immagine) mi sembra corretta. Non vedo ragioni per non accettare tale soluzione.
Dividere il programma in sottoprogramma significa semplicemente che devi suddividere il programma in diverse funzioni, ognuna che risolve parti diverse del tuo problema. Se hai messo tutto nel main allora non hai rispettato tale richiesta.
Non esistono parametri oggettivi per valutare un codice per un esame di informatica, dipende dall'insegnante. Non mi è del tutto chiaro il punto in cui ti sei fermato. Hai stampato il contenuto di V senza allocarlo? Hai stampato solo MIN e MAX per ogni riga? Se devo dare una opinione dal poco che ho capito del tuo esame, suppongo tu possa arrivare alla sufficienza, eventualmente attraverso l'orale.
Dividere il programma in sottoprogramma significa semplicemente che devi suddividere il programma in diverse funzioni, ognuna che risolve parti diverse del tuo problema. Se hai messo tutto nel main allora non hai rispettato tale richiesta.
Non esistono parametri oggettivi per valutare un codice per un esame di informatica, dipende dall'insegnante. Non mi è del tutto chiaro il punto in cui ti sei fermato. Hai stampato il contenuto di V senza allocarlo? Hai stampato solo MIN e MAX per ogni riga? Se devo dare una opinione dal poco che ho capito del tuo esame, suppongo tu possa arrivare alla sufficienza, eventualmente attraverso l'orale.
Per un mio modo di fare non frequento le lezioni e mi capita di conoscere i professori solo all'esame.
Ho definito una funzione imatrice per l'input della matrice, e una omatrice per l'output. Poi ho richiesto l'inserimento di K e ho definito due vettori MIN e MAX aventi come dimensione le righe della matrice M1 e in ogni componente ho memorizzato il valore del minimo e del massimo per ogni riga e ho mostrato sullo schermo i vettori MIN e MAX.
Il mio programma chiede di inserire numero di righe e colonne delle due matrici, poi di inserire i vari elementi e mostra sullo schermo le matrici formattate. Poi ti chiede di inserire un valore K e infine mostra i vettori MIN e MAX.
Ho definito una funzione imatrice per l'input della matrice, e una omatrice per l'output. Poi ho richiesto l'inserimento di K e ho definito due vettori MIN e MAX aventi come dimensione le righe della matrice M1 e in ogni componente ho memorizzato il valore del minimo e del massimo per ogni riga e ho mostrato sullo schermo i vettori MIN e MAX.
Il mio programma chiede di inserire numero di righe e colonne delle due matrici, poi di inserire i vari elementi e mostra sullo schermo le matrici formattate. Poi ti chiede di inserire un valore K e infine mostra i vettori MIN e MAX.
Il codice funzionava, secondo voi c'è la sufficienza?
Oltre alla variabile professore dipende anche da quale esame hai sostenuto e da quale facoltà frequenti.
Quanto tempo avevi a disposizione?
Per quanto riguarda la traccia, oltre ad essere molto vaga, mi sembra anche abbastanza stupida. Purtroppo come spesso accade la difficoltà degli esercizi sta più nell'interpretazione che nell'effettiva risoluzione del problema presentato.
Alcune osservazioni:
- bisognerebbe imporre che K sia minore o uguale del numero di colonne di M2, altrimenti il vettore V sarà sicuramente vuoto;
- se il vettore V contiene tutti gli "n x K" elementi (dove n è il numero di righe di M1 che rispettano la condizione), non ci sarebbe bisogno anche di un altro vettore per tenere traccia degli indici delle righe di M2 di provenienza?
Non è chiaro se il vettore V deve contenere i valori per tutte le righe o solo per quella attualmente presa in considerazione.
In effetti utilizzare una matrice di n righe (dove n è sempre il numero di righe di M1 che rispettano la condizione) e K colonne avrebbe più senso.
Un ulteriore vettore di n elementi potrebbe poi essere utilizzato per tenere traccia degli indici delle righe di M2.
Un ulteriore vettore di n elementi potrebbe poi essere utilizzato per tenere traccia degli indici delle righe di M2.
In realtà tutto il problema non ha molto senso dato che l'unica cosa che si fa con quel vettore è stamparlo, a quel punto basterebbe rileggere la riga stampando a schermo i valori in questione. Insomma si crea il vettore al solo scopo di crearlo 
.
Di per sé esistono molti punti oscuri del testo e non è ben chiaro quale debba essere l'output esatto del programma (cosa succede quando la condizione non è soddisfatta? Cosa succede nel caso più righe di M2 soddisfino la condizione? I valori di massimo e minimo della riga vanno stampati?). In ogni caso la maggior parte delle operazioni agiscono sulle singole righe, quindi cambia poco il metodo usato per allocare le matrici. Inoltre anche il modo in cui le matrici stesse sono inizializzate non è ben definito. Suppongo che lui intenda che vengono inseriti dalla console, ma il testo non lo dice esplicitamente (e certamente è un modo molto scomodo per correggere i compiti).
Riguardo ai massimi e minimi comunque non era necessario memorizzarli per ogni riga dato che puoi controllare le righe della seconda matrice prima di calcolare massimo e minimo della riga successiva.
.Di per sé esistono molti punti oscuri del testo e non è ben chiaro quale debba essere l'output esatto del programma (cosa succede quando la condizione non è soddisfatta? Cosa succede nel caso più righe di M2 soddisfino la condizione? I valori di massimo e minimo della riga vanno stampati?). In ogni caso la maggior parte delle operazioni agiscono sulle singole righe, quindi cambia poco il metodo usato per allocare le matrici. Inoltre anche il modo in cui le matrici stesse sono inizializzate non è ben definito. Suppongo che lui intenda che vengono inseriti dalla console, ma il testo non lo dice esplicitamente (e certamente è un modo molto scomodo per correggere i compiti).
Riguardo ai massimi e minimi comunque non era necessario memorizzarli per ogni riga dato che puoi controllare le righe della seconda matrice prima di calcolare massimo e minimo della riga successiva.
Si è vero, la traccia è ambigua, comunque non l'ho superato quindi mi sono messo a fare altri esercizi che a breve posterò. Non ho visto il compito né discusso col professore dell'ambiguità della traccia e non ho tempo per farlo visto che il prossimo appello sarà lunedì.
Voglio creare un programma che, dato un vettore, mi dice se gli elementi sono ordinati in modo crescente oppure no. Posso mettere dentro l'if più proposizioni o addirittura un ciclo for (in modo da confrontare l'elemento con quello successivo fino ad esaurire il vettore)? Ho provato ma non funziona.
EDIT: RIsolto
Voglio creare un programma che, dato un vettore, mi dice se gli elementi sono ordinati in modo crescente oppure no. Posso mettere dentro l'if più proposizioni o addirittura un ciclo for (in modo da confrontare l'elemento con quello successivo fino ad esaurire il vettore)? Ho provato ma non funziona.
EDIT: RIsolto
Provavo a fare quest'esercizio:
"Siano dati in ingresso una matrice di numeri interi M e un valore intero K. Scrivere un programma che verifichi se esistono almeno due colonne di M i cui valori siano ordinati in modo crescente. Se tale condizione risulta verificata si provveda a fondere gli elementi di tali colonne in un vettore ordinato V: nel fare questa operazione si deve garantire che il vettore V contenga solo gli elementi che sono a
Distanza maggiore di K tra loro. Stampare infine la matrice M, indicare gli indici delle colonne a valori crescenti eventualmente trovate e, nel caso, il vettore V ottenuto."
SOno arrivato qui:
Come posso continuare?
"Siano dati in ingresso una matrice di numeri interi M e un valore intero K. Scrivere un programma che verifichi se esistono almeno due colonne di M i cui valori siano ordinati in modo crescente. Se tale condizione risulta verificata si provveda a fondere gli elementi di tali colonne in un vettore ordinato V: nel fare questa operazione si deve garantire che il vettore V contenga solo gli elementi che sono a
Distanza maggiore di K tra loro. Stampare infine la matrice M, indicare gli indici delle colonne a valori crescenti eventualmente trovate e, nel caso, il vettore V ottenuto."
SOno arrivato qui:
#include <iostream>
using namespace std;
void imatrice(int nrig, int ncol, int** matrice)
{
for(int i=0;i<nrig;i++)
{
for(int j=0;j<ncol;j++)
{
cout<<"\nInserisci l'elemento posizionato sulla riga "<<i+1<<" e sulla colonna "<<j+1<<" ";
cin>>matrice[i][j];
}
}
}
void omatrice(int nrig, int ncol, int** matrice)
{
for(int i=0;i<nrig;i++)
{
cout<<"\n";
for(int j=0;j<ncol;j++)
{
cout<<" "<<matrice[i][j]<<" ";
}
}
}
int main()
{
int i;
int j;
int nrig;
int ncol;
int k;
cout<<"Inserisci il numero di righe della matrice ";
cin>>nrig;
cout<<"\nInserisci il numero di colonne della matrice ";
cin>>ncol;
int** matrice=new int* [nrig];
for(i=0;i<nrig;i++)
{
matrice[i]=new int[ncol];
}
imatrice(nrig, ncol, matrice);
cout<<"\nLa matrice che hai inserito è\n";
omatrice(nrig, ncol, matrice);
//parte per l'individuazione delle colonne ordinate in modo crescente
int cont=0; //variabile contatore per sapere se ci sono almeno due colonne crescenti e che uso per dare il messaggio di avviso
bool varbool=true;
for(j=0;j<ncol;j++)
{
for(i=1;i<nrig;i++)
{
if(matrice[i-1][j]<matrice[i][j])
{
;
}
else varbool=false;
}
if(varbool)
{
cout<<"\nLa colonna "<<j+1<<" è ordinata in modo crescente.";
++cont;
}
else
{
cout<<"\nLa colonna "<<j+1<<" non è ordinata in modo crescente.";
//riporto varbool a true, cioè la resetto al valore di partenza
varbool=true;
}
}
if(cont>=2)
{
cout<<"\nEsistono almeno due colonne ordinate in modo crescente.";
}
}
Come posso continuare?
Per il momento va bene, anche se la parte relativa all'individuazione delle colonne ordinate in modo crescente può essere migliorata.
In ogni caso arrivato a questo punto quali difficoltà incontri? Non riesci ad impostare il problema dal punto di vista logico oppure non riesci a tradurre in codice l'algoritmo a cui hai pensato?
In ogni caso arrivato a questo punto quali difficoltà incontri? Non riesci ad impostare il problema dal punto di vista logico oppure non riesci a tradurre in codice l'algoritmo a cui hai pensato?
Vorrei proseguire memorizzando in un vettore gli indici delle sole colonne crescenti e non so come farlo. Poichè al massimo questo vettore avrà dimensione ncol, stavo pensando di definire un vettore di dimensione appunto ncol e inizializzarlo a zero, e poi memorizzare nelle componenti gli indici delle eventuali colonne crescenti, però così ci sarebbero altre componenti inutilizzate poste a zero che non mi interessano e non mi piace. Voglio che questo vettore memorizzi solo gli indici delle colonne crescenti e nient'altro, quindi la sua dimensione effettiva non posso definirla a priori. Fatto questo utilizzerei l'algoritmo di merge per unire le varie colonne ed ottenere il vettore richiesto.
Poi ho un dubbio generale sugli esercizi che forse dovrei chiedere al docente: i vettori, le matrici e i numeri in input vanno inseriti da console oppure devo scrivere un codice particolare che poi verrà testato andando a modificare i valori scritti nel codice stesso? Infine il docente nei suoi esempi non usa per i vettori l'allocazione dinamica, ma all'inizio scrive una cosa tipo define nmax=100 come se imponesse un limite massimo alla dimensione del vettore.
Poi ho un dubbio generale sugli esercizi che forse dovrei chiedere al docente: i vettori, le matrici e i numeri in input vanno inseriti da console oppure devo scrivere un codice particolare che poi verrà testato andando a modificare i valori scritti nel codice stesso? Infine il docente nei suoi esempi non usa per i vettori l'allocazione dinamica, ma all'inizio scrive una cosa tipo define nmax=100 come se imponesse un limite massimo alla dimensione del vettore.
Prima di tutto, anche se capisco la fretta per il nuovo appello, sarebbe stato estremamente utile confrontarti con il professore riguardo al compito. Comprendere cosa sia richiesto dal professore può infatti essere abbastanza importante.
Sono sempre stupito dall'importanza data da molti studenti e principianti all'idea di sprecare memoria. Ci sono situazioni in cui è importante preoccuparsi della quantità di memoria usata, ma nella maggior parte dei casi è molto più importante come i dati sono distribuiti in memoria. Ma normalmente viene data molta poca importanza a questo aspetto. Allocare un'array di dimensione ncol è certamente la soluzione più semplice in questo caso in cui non puoi usare qualcosa come un std::vector. La dimensione dell'array sarà comunque semplicemente \(4\,\mathrm{ncol}\) bytes (assumendo che gli indici siano di 32bit). Anche con una matrice con un numero di colonne pari ad un milione avresti comunque solo qualche MB di memoria usata.. Corrisponde ad una singola riga in più della matrice che probabilmente sarà molto più grande. È possibile implementare una struttura dati che viene ridimensionata in base alla quantità di colonne effettivamente inserite, ma in questo caso non credo ci siano vantaggi.
È abbastanza comune definire negli esercizi/esempi una dimensione massima e quindi allocare la matrice in modo statico. Ma questa è una domanda per il tuo professore. Puoi provare a scrivergli una email se non vuoi andare a parlargli di persona.
Sono sempre stupito dall'importanza data da molti studenti e principianti all'idea di sprecare memoria. Ci sono situazioni in cui è importante preoccuparsi della quantità di memoria usata, ma nella maggior parte dei casi è molto più importante come i dati sono distribuiti in memoria. Ma normalmente viene data molta poca importanza a questo aspetto. Allocare un'array di dimensione ncol è certamente la soluzione più semplice in questo caso in cui non puoi usare qualcosa come un std::vector. La dimensione dell'array sarà comunque semplicemente \(4\,\mathrm{ncol}\) bytes (assumendo che gli indici siano di 32bit). Anche con una matrice con un numero di colonne pari ad un milione avresti comunque solo qualche MB di memoria usata.. Corrisponde ad una singola riga in più della matrice che probabilmente sarà molto più grande. È possibile implementare una struttura dati che viene ridimensionata in base alla quantità di colonne effettivamente inserite, ma in questo caso non credo ci siano vantaggi.
È abbastanza comune definire negli esercizi/esempi una dimensione massima e quindi allocare la matrice in modo statico. Ma questa è una domanda per il tuo professore. Puoi provare a scrivergli una email se non vuoi andare a parlargli di persona.
Ho cercato di ottimizzare il tutto anche se sono bloccato sempre al punto di ieri.
Il mio metodo di studio mi porta ad interagire con i docenti solo dopo aver sbattuto la testa a lungo da solo e aver appreso abbastanza gli argomenti. Sono fatto strano, se qualcuno mi parla di qualcosa di complicato e io non ci ho mai ragionato prima ho difficoltà a seguire il discorso.
All'inizio ho messo le variabili globali in modo da evitare di scriverle sempre come argomenti delle funzioni.
Il mio metodo di studio mi porta ad interagire con i docenti solo dopo aver sbattuto la testa a lungo da solo e aver appreso abbastanza gli argomenti. Sono fatto strano, se qualcuno mi parla di qualcosa di complicato e io non ci ho mai ragionato prima ho difficoltà a seguire il discorso.
All'inizio ho messo le variabili globali in modo da evitare di scriverle sempre come argomenti delle funzioni.
#include <iostream>
using namespace std;
int nrig;
int ncol;
int i;
int j;
void imatrice(int** matrice)
{
for(int i=0;i<nrig;i++)
{
for(int j=0;j<ncol;j++)
{
cout<<"\nInserisci l'elemento posizionato sulla riga "<<i+1<<" e sulla colonna "<<j+1<<" ";
cin>>matrice[i][j];
}
}
}
void omatrice(int** matrice)
{
for(int i=0;i<nrig;i++)
{
cout<<"\n";
for(int j=0;j<ncol;j++)
{
cout<<" "<<matrice[i][j]<<" ";
}
}
}
int testasecolonnacrescente(int** matrice, int col)
{
for(int i=1;i<nrig;i++)
{
if(matrice[i-1][col]>=matrice[i][col])
{
return 0;
}
}
return 1;
}
int main()
{
cout<<"Inserisci il numero di righe della matrice ";
cin>>nrig;
cout<<"\nInserisci il numero di colonne della matrice ";
cin>>ncol;
//allocazione matrice
int** matrice=new int* [nrig];
for(i=0;i<nrig;i++)
{
matrice[i]=new int[ncol];
}
imatrice(matrice);
cout<<"\nLa matrice che hai inserito è\n";
omatrice(matrice);
int col;
for(col=0;col<ncol;col++)
{
if(testasecolonnacrescente(matrice,col))
cout<<"\nLa colonna "<<col+1<<" è crescente.";
else
cout<<"\nLa colonna "<<col+1<<" non è crescente.";
}
}
Infine il docente nei suoi esempi non usa per i vettori l'allocazione dinamica, ma all'inizio scrive una cosa tipo define nmax=100 come se imponesse un limite massimo alla dimensione del vettore.
L'istruzione corretta sarebbe #define nmax 100 e in pratica non stai facendo altro che definire una macro che in fase di compilazione sostituisce nmax con 100 (anche se secondo me è sempre meglio utilizzare al posto del #define una variabile dichiarata "const").
In ogni caso lo scopo è lo stesso, ossia si sta fissando un valore non modificabile che andrà a costituire la dimensione dell'array statico (come già detto in precedenza l'allocazione di un array statico richiede che la dimensione dello stesso sia nota già in fase di compilazione).
Detto questo, ti consiglio ai fini dell'esame di ricorrere all'allocazione dinamica della memoria solo nei casi in cui è esplicitamente richiesto dall'esercizio.
Vorrei proseguire memorizzando in un vettore gli indici delle sole colonne crescenti e non so come farlo. Poichè al massimo questo vettore avrà dimensione ncol, stavo pensando di definire un vettore di dimensione appunto ncol e inizializzarlo a zero, e poi memorizzare nelle componenti gli indici delle eventuali colonne crescenti, però così ci sarebbero altre componenti inutilizzate poste a zero che non mi interessano e non mi piace.
Come già detto da apatriarca in questi casi non sussistono problemi dovuti allo spreco di memoria, quindi la scelta migliore è un array di ncol elementi, di cui ti interessano solo i primi cont (l'inizializzazione a zero è inutile). Infatti affinchè il vettore contenga solo gli indici delle colonne crescenti, ad un irrilevante guadagno in termini di memoria, si associa una maggiore complessità del codice e un maggior numero di operazioni (bisogna infatti o ricorrere più volte all'allocazione dinamica oppure scorrere la matrice due volte).
Fatto questo utilizzerei l'algoritmo di merge per unire le varie colonne ed ottenere il vettore richiesto.
Non conosco questo algoritmo, in ogni caso io userei un vettore di nrig x ncol elementi in cui andrei a copiare tutti gli elementi delle colonne crescenti e poi lo ordinerei. Per quanto riguarda la questione del K anche questo esercizio risulta parecchio ambiguo, nel senso che non ho capito se intende la distanza in termini di indici oppure la differenza tra valori successivi (e in entrambi i casi comunque è poco chiaro che quello di preciso bisognerebbe fare).
Sono fatto strano, se qualcuno mi parla di qualcosa di complicato e io non ci ho mai ragionato prima ho difficoltà a seguire il discorso.
Non è poi tanto strano, alla fine dipende anche da chi spiega e soprattutto dal grado di comprensione che uno si impone.
Ho cercato di ottimizzare il tutto anche se sono bloccato sempre al punto di ieri.
Alcune considerazioni:
- dichiari i e j come variabili globali ma poi non le sfrutti visto che nelle funzioni le dichiari di nuovo, mentre nel main potresti utilizzare semplicemente la variabile j al posto di dichiarare una nuova variabile col;
- visto l'utilizzo che ne fai, conviene che la funzione testacolonna ritorni un bool e non un int;
- ti consiglio di aggiornare il programma utilizzando array statici e aggiungendo la parte relativa al vettore V (almeno per quanto riguarda l'unione e l'ordinamento, mentre la parte riguardante il parametro K dimmi tu come vuoi interpretarla).
@SuperSquirrel: Con algoritmo di merge fa riferimento alla fase finale del merge sort in cui due array ordinati vengono combinati per formare un nuovo array ordinato con gli elementi di entrambi. Ha una complessità lineare. E' molto più semplice da implementare di un algoritmo generico di ordinamento. Un esempio (senza controllo dell'input) è il seguente:
Ovviamente in altre circostanze non è necessario implementare tale funzioni che è già presente nella libreria..
void merge(int *dst, int n, int *a, int m, int *b)
{
int i = 0, j = 0, k = 0;
while (i < n && j < m) {
dst[k++] = a[i] < b[j] ? a[i++] : b[j++];
}
while (i < n) { dst[k++] = a[i++]; }
while (j < m) { dst[k++] = b[j++]; }
}
Ovviamente in altre circostanze non è necessario implementare tale funzioni che è già presente nella libreria
Non conoscevo questo algoritmo di ordinamento, ma mi sono fatto un'idea di come funziona. In effetti nell'ordinare un vettore
costituito dall'unione di vettori già ordinati non ha senso partire da zero.
costituito dall'unione di vettori già ordinati non ha senso partire da zero.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo