• Non ci sono risultati.

Disporre gli elementi di un vettore in modo da alternare gli

N/A
N/A
Protected

Academic year: 2022

Condividi "Disporre gli elementi di un vettore in modo da alternare gli"

Copied!
9
0
0

Testo completo

(1)

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

(2)

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

(3)
(4)

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

(5)

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

(6)

/* 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;

}

(7)

//--- // 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;

}

(8)

// ---

// 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 */

}

(9)

// ======================= 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;

}

Riferimenti

Documenti correlati

In un palazzo di 100 piani si vuole stabilire qual ` e il piano pi` u alto dal quale ` e possibile lanciare un uovo senza che esso si rompa.. Le uova sono considerate tutte aventi

Dati U,V sottospazi di un k-spazio vettoriale T , si definisce lo spazio somma U+V ={u+v| u∈U,v∈V} che risulta essere sottospazio di T ( il più piccolo sottospazio di T che

[r]

Dati un insieme A che contiene n elementi, un insieme B che contiene m elementi, ed una relazione R da A a B, la relazione R si può rappresentare con una matrice booleana nxm

Diciamo che un elemento di a nella generica posizione (i,j) è perfetto se il suo valore è pari alla somma del suo indice di riga e del suo indice di colonna, cioè se a[i][j] = i+j.

Si consideri una lista di numeri interi Lista implementata come lista doppiamente puntata non circolare implementata utilizzando la seguente struttura.. struct

Ricerca esaustiva: si scandisce il vettore, confrontando gli elementi con quello da cercare, fino a che.. • si sono confrontati tutti gli

La tendenza ad ossidarsi e ridursi genera un flusso di elettroni (e quindi di corrente elettrica) dall’anodo verso