Disporre gli elementi di un vettore in modo da alternare gli elementi pari con gli elementi dispari
L'algoritmo proposto prevede di scorrere il vettore (usando l'indice i) dalle posizioni iniziali per indicare la posizione in cui disporre l’elemento idoneo.
Se in una posizione i-esima si deve posizionare un elemento pari, partendo dalla posizione successiva (usando l’indice j), si cerca un elemento dispari e si effettua lo scambio. E così se in una posizione i-esima si deve posizionare un elemento dispari, partendo dalla posizione successiva, si cerca un elemento pari e si effettua lo scambio.
Il posizionamento, in una certa locazione, di un elemento pari o dispari viene pilotato da una variabile flag che, impostata a false, inserisce un elemento pari ed, invece, impostata a true inserisce un elemento dispari. Ovviamente, dopo l’avvenuto posizionamento la variabile viene negata per cambiare la ricerca.
Il procedimento termina quando, scorrendo il vettore, si arriva al penultimo elemento (l’ultimo, comunque, è corretto) oppure non si trovano più elementi da scambiare, ovvero se tutti gli elementi finali sono dello stesso tipo (tutti pari o tutti dispari)
Esempio
Dato l’ array :11 5 3 7 6 4 8 15 10
al primo passaggio si ottiene :
6 5 3 7 11 4 8 15 10
al secondo passaggio si ottiene :
6 5 3 7 11 4 8 15 10
al terzo passaggio si ottiene :
6 5 4 7 11 3 8 15 10
al quarto passaggio si ottiene :
6 5 4 7 11 3 8 15 10
e così via fino al termine :
6 5 4 7 8 3 10 15 11
Analisi dei dati
Identificatore Descrizione Tipo Input Output Lavoro Dmax Costante : dimensione massima del
vettore intero
Dim dimensione del vettore intero si
V[] vettore contenente gli elementi da
posizionare intero si si
I indice iniziale per scorrere il vettore
dall’inizio intero si
J indice per scorrere il vettore dalla
posizione successiva ad I intero si
F flag : indica se si deve sistemare un
numero pari o uno dispari booleano si
S flag : indica se si è verificato o meno
uno scambio booleano si
Funzione Alterna
F = 0
V
S = 1
F = NOT(F)
F
End
V
F
I<Dim-1 AND S=1 F = 0
R = V[I] mod 2
R ≠ 0
V
I = I + 1
F
I = 0
S = Pari(I) V
R = V[I] mod 2
R = 0
S = Dispari(I) F
Funzione Pari(J)
ES = 0
P = J
F
Return ES
F
J<Dim AND ES=0 R = V[J] mod 2
V
J = J + 1
R = 0 V
C = V[P]
V[P] =V[J]
V[J] = C J = J + 1
ES = 1
Funzione Dispari(J)
ES = 0
P = J
F
Return ES
F
J<Dim AND ES=0 R = V[J] mod 2
V
J = J + 1
R ≠ 0 V
C = V[P]
V[P] =V[J]
V[J] = C J = J + 1
ES = 1
/* disporre gli elementi di un vettore in modo da alternare gli elementi pari con gli elementi dispari.
*/
#include <iostream>
#include <stdlib.h> // per rand() e srand()
#include <time.h> // per time()
using namespace std;
const int maxdim = 50;
int v[maxdim]={0};
int dim; // variabile globale
//======================== FUNZIONI ======================
// funzione per la richiesta della dimensione del vettore int dimensione_vettore()
{ do {
cout << "Inserire la dimensione del vettore (max="<<maxdim<<") ..: ";
cin >> dim;
}
while ((dim < 1 ) || (dim > maxdim));
return dim;
}
// ---
// funzione per il caricamento random del vettore void carica_vettore()
{
srand (time(NULL));
for (int i = 0; i < dim; ++i) {
v[i]=rand();
} }
// --- // funzione per la visualizzazione del vettore void visualizza_vettore()
{
cout<<"\n ===== Visualizzazione vettore ====="<<endl;
for (int i=0; i < dim; ++i) {
cout << "\nL'elemento di posto " << i+1 << "...: " << v[i]<<endl;
} }
//--- // funzione per lo scambio di due variabili
void scambia(int &x, int &y) {
int temp;
temp = x;
x = y;
y = temp;
}
//--- // funzione per la ricerca di un numero pari
bool cerca_pari(int j) {
int p; // conserva la posizione corrente in cui si deve sistemare l'elemento pari bool esito_scambio = false; /* segnala se si è verificato uno scambio se nella ricerca non si effettua alcuno scambio vuol dire che non ci sono più elementi da alternare e, quindi, l'algoritmo deve terminare */
p=j;
++j; // si parte, nella ricerca di un elemento pari, dalla posizione successiva a quella attuale
do {
if (v[j]%2 == 0) // se l'elemento è pari {
scambia(v[p],v[j]); // si effettua lo scambio
esito_scambio=true; // e si imposta la variabile per segnalare l'avvenuto scambio }
else // se l'emeneto è dispari {
++j; // si continua a scorrere il vettore }
}while(j<dim && esito_scambio==false);
/* il ciclo termina quando si arriva, nella ricerca, alla fine del vettore oppure quando si effettua uno scambio */
return esito_scambio; /* si ritorna alla funzione chiamante la variabile che segnala se, nella ricerca dell'elemento, è stato o meno
effettuato uno scambio */
}
//--- // funzione per la ricerca di un numero dispari bool cerca_dispari(int j)
{
int p; // conserva la posizione corrente in cui si deve sistemare l'elemento dispari bool esito_scambio = false;
p=j;
++j; // si parte, nella ricerca di un elemento dispari, dalla posizione successiva a quella
attuale
do {
if (v[j]%2 != 0) {
scambia(v[p],v[j]);
esito_scambio=true;
} else {
++j;
}
}while(j<dim && esito_scambio==false);
return esito_scambio;
}
// ---
// funzione per alternare gli elementi pari con gli elementi dispari void alterna_pari_dispari()
{
bool f=false; // serve per cercare un elemento pari o uno dispari bool scambio=true;
int i=0;
do {
/* f=false indica che nella posizione attuale deve esserci un elemento pari;
f=true indica che nella posizione attuale deve esserci un elemento dispari;
Partendo con f=false si alternano elementi pari con elementi dispari; con f=true si alternano elementi dispari con
elementi pari.
*/
if (f==false) /* nella posizione corrente deve esserci un elemento pari */
{
if (v[i]%2 != 0) // se l'elemento è dispari {
scambio=cerca_pari(i); /* si cerca un elemento pari passando alla funzione la posizione corrente e ricevendo la segnalazione se è avvenuto o meno uno scambio
*/
} }
else // nella posizione corrente deve esserci un elemento dispari {
if (v[i]%2 == 0) // se l'elemento è pari {
scambio=cerca_dispari(i); // si cerca un elemento pari }
}
++i; // dopo il posizionamento dell'elemento si aggiorna l'indice attuale f=!f; /* si nega la variabile in modo da ricercare un elemento
dispari dopo aver posizionato un elemento pari, oppure ricercare un elemento pari dopo aver posizionato un elemento dispari */
}while(i<dim-1 && scambio == true);
/* il ciclo termina quando l'indice attuale arriva alla penultima posizione (l'ultima in tutti i casi è corretta) oppure quando nella ricerca di un elemento da posizionare non si è verificato alcuno scambio */
}
// ======================= MAIN ==========================
int main (int argc, char *argv[]) {
char quit;
quit = '\0';
while (quit != 'q') {
dimensione_vettore();
carica_vettore();
visualizza_vettore();
alterna_pari_dispari();
visualizza_vettore();
// =======================================
// termine programma con richiesta di uscita cout <<"Premere q per uscire ";
cin >> quit;
} return 0;
}