Clasa a IX-a lecția 17

From Algopedia
Jump to navigationJump to search

Tema - rezolvări

Rezolvări aici [1]

Lecție

În continuare vom discuta rezolvări ale unor probleme clasice cu vectori.

Căutare în vector

Se dă un vector v de n elemente și un extra element e. Să se găsească poziția p în v unde apare prima oară elementul e. Dacă elementul e nu apare p va avea valoarea n. O soluție elegantă care nu iese forțat din buclă și care nu folosește stegulețe este: 

// avem vectorul v de n elemente si o valoare e de gasit in acest vector
p = 0;
while ( p < n && v[p] != e )
  p++;
// acum p este fie pozitia primei aparitii a lui e, fie n daca e nu exista in v

Inserare în vector

Se dă un vector v de n elemente, un extra element e și o poziție p. Să se insereze elementul e la poziția p. În final elementul e va fi pe poziția p în vector, iar elementele de la poziția p pînă la final vor fi deplasate spre final cu o poziție. Vom considera că p este o poziție validă, între 0 și n. 

// avem vectorul v de n elemente si o valoare e de inserat la poziția p
for ( i = n - 1; i >= p; i-- ) // deplasăm elementele spre dreapta
  v[i+1] = v[i];
v[p] = e;
n++; // vectorul are acum n+1 elemente!
for ( i = n; i > p; i-- ) // deplasăm elementele spre dreapta
  v[i] = v[i-1];
v[p] = e;
n++; // vectorul are acum n+1 elemente!

Ștergere din vector

Se dă un vector v de n elemente și o poziție p. Să se elimine elementul de la poziția p din vector. Elementele de la poziția p pînă la final se vor deplasa către începutul vectorului cu o poziție. 

// avem vectorul v de n elemente si o poziție p ce trebuie eliminata
for ( i = p + 1; i < n; i++ ) // deplasam elementele spre stinga
  v[i-1] = v[i];
n--; // vectorul are acum n-1 elemente!

Varianta2: 

// avem vectorul v de n elemente si o poziție p ce trebuie eliminata
for ( i = p; i < n - 1; i++ ) // deplasam elementele spre stinga
  v[i] = v[i+1];
n--; // vectorul are acum n-1 elemente!

Răsturnare vector

Se dă un vector v de n elemente. Inversați poziția elementelor în vector. Avem mai multe soluții posibile, una foarte simplă este să folosim doi indici, unul care crește și unul care descrește. Vom interschimba elementele celor doi indici. Vom repeta acest lucru pînă ce indicii se întîlnesc.

Metoda 1

// avem vectorul v de n elemente, vrem sa il rasturnam
i = 0;
j = n – 1;
while ( i < j ) {
  aux = v[i];
  v[i] = v[j];
  v[j] = aux;
  i++;
  j--;
}

Metoda 2

// avem vectorul v de n elemente, vrem sa il rasturnam

for ( i = 0; i < n/2; i++ ) {
  aux = v[i];
  v[i] = v[n-i-1];
  v[n-i-1] = aux;
}

Rotire vector

Se dă un vector v de n elemente. Să se rotească vectorul cu o poziție către început cu o poziție. De exemplu [1, 6, 2, 7, 4, 3, 2] se va transforma în [6, 2, 7, 4, 3, 2, 1].

Rotire catre stanga

// avem vectorul v de n elemente, vrem sa il rotim la stinga cu o pozitie
aux = v[0];
for ( i = 1; i < n; i++ )
  v[i-1] = v[i];
v[n-1] = aux;

Rotire catre dreapta

// avem vectorul v de n elemente, vrem sa il rotim la stinga cu o pozitie
aux = v[n-1];
for ( i = n-1; i > 0; i-- )
  v[i] = v[i-1];
v[0] = aux;

Mutare zerouri la coadă

Se dă un vector v de n elemente. Să se modifice ordinea elementelor în vector astfel încît toate elementele zero să fie la coada vectorului. Celelalte elemente nu trebuie să își păstreze ordinea originală (pot fi în orice ordine). O soluție posibilă este să mergem cu doi indici, unul crescător și unul descrescător. Cel crescător avansează pînă ce găsește un zero. Apoi interschimbă cu celălalt indice, pe care îl scade. 

// avem vectorul v de n elemente, vrem sa mutăm zerourile la coada
i = 0;
j = n – 1;
while ( i < j ) {
  if ( v[i] == 0 ) { // daca avem un zero pe pozitia i
    v[i] = v[j];     // il trecem la coada, interschimbind cu pozitia j
    v[j] = 0;
    j--;             // deoarece pe pozitia j avem un zero, putem sa scadem j
  } else
    i++;             // daca avem nonzero pe pozitia i putem avansa i
}

Comparație vectori

Dați doi vectori de caractere să se spună care este ordinea lor lexicografică. Cu alte cuvinte, ordinea în care vor apărea cele două cuvinte în dicționar.

Rămîne ca temă.

Rotire multiplă de vector *

Se dă un vector v de n elemente și un număr k. Să se rotească vectorul cu o poziție către început cu k poziții. De exemplu, pentru k=3 [1, 6, 2, 7, 4, 3, 2] se va transforma în [7, 4, 3, 2, 1, 6, 2].

Rămîne ca temă pentru cei dornici să se lupte cu o problemă grea.

Laborator

#1452 Stergere_Element

Să se șteargă dintr-un șir elementul aflat pe o poziție dată.

#163 stergere

Să se șteargă dintr-un vector toate elementele care sunt numere prime.


#1453 stergere1

Să se șteargă dintr-un vector toate elementele pare.


#158 inserare

Să se insereze pe o poziție dată într-un șir o valoare precizată.

#159 inserareDupa Să se insereze într-un șir după fiecare element par dublul său.

#160 inserareInainte Să se insereze într-un șir înaintea fiecărui element pătrat perfect rădăcina sa pătrată.

#1365 aceeasi_paritate Se dau n numere întregi. Să se insereze între oricare două numere de aceeași paritate media lor aritmetică.

#1366 aceeasi_paritate_2 Se dau n numere întregi. Să se insereze între oricare două numere de aceeași paritate media lor aritmetică. Să se realizeze acest procedeu până nu se mai pot adăuga noi elemente.

#162 PermCirc

Determinați toate permutările circulare spre stânga ale unui vector dat. 

#include <stdio.h>
int main(){
  int n, i, j, aux, v[16];
  
  scanf("%d", &n );
  for( i = 0; i < n; i++ )
    scanf( "%d", &v[i] );

  for( i = 0; i < n; i++ ){
    // afisez vectorul 
    for( j = 0; j < n; j++ )
      printf( "%d ", v[j] );
    printf( "\n" );
    // fac o permutare circulara catre stanga
    aux = v[0];
    for( j = 1; j < n; j++ )
      v[j-1] = v[j];
    v[n-1] = aux;
    
  }
  return 0;
}

#596 Numere2 Gigel a găsit un șir cu n numere naturale. În fiecare zi Gigel parcurge șirul și când găsește o pereche de elemente consecutive egale o elimină din șir și se oprește. Determinați în câte zile va elimina Gigel elemente din șir și care sunt valorile din șir după eliminări. 

#include <stdio.h>
int st[25000];
int main(){
    FILE *fin, *fout;
    int n, i, k, x, zile;
    fin = fopen( "numere2.in", "r" );
    fout = fopen( "numere2.out", "w" );

    fscanf( fin, "%d%d", &n, &st[0] );

    zile = 0;
    k = 1;  			      // varful stivei
    for( i = 1; i < n; i++ ){
      fscanf( fin, "%d", &x );
      if( k > 0 && x == st[k-1] ){			            
        k --;		            		// eliminam un element din stiva
        zile ++;            			// crestem nr de zile, caci am facut o eliminare
      }          	
      else 								// daca x are valoare diferita decat precedenta 
        st[k++] = x;     				// adaugam x pe stiva
    }

    fprintf(fout, "%d\n", zile );

    for( i = 0; i < k; i++ )
      fprintf( fout, "%d ", st[i] );

    fclose(fin);
    fclose(fout);
    return 0;
}

Temă

Finalizati implementarea problemelor din fisa de laborator:

Rezolvați următoarele probleme:

  • compus problemă de exersat operațiile clasice pe vectori

Opțional, teme de gîndire:

  • Comparația a doi vectori: dați doi vectori, v de lungime m și w de lungime n să se spună dacă v este mai mic, egal, sau mai mare decît w. Gîndiți-vă cum ați face această problemă și încercați să scrieți o bucată de program C care să o rezolve.
  • Grea: rotk (rotație multiplă vector fără a face rotații repetate cu unu).

Rezolvări aici [2]

Retrieved from "https://www.algopedia.ro/wiki/index.php?title=Clasa_a_IX-a_lecția_17&oldid=17348"