Difference between revisions of "Clasa a IX-a lecția 20"

From Algopedia
Jump to navigationJump to search
(Blanked the page)
Tag: Blanking
 
Line 1: Line 1:
= Tema - rezolvări =
 
  
Rezolvări aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_V-a_lec%C8%9Bia_23_-_27_ian_2015]
 
 
= Lecție =
 
În continuare vom discuta rezolvări ale unor probleme clasice cu vectori.
 
 
== Căutare în vector ==
 
Se dă un vector <tt>v</tt> de <tt>n</tt> elemente și un extra element <tt>e</tt>. Să se găsească poziția <tt>p</tt> în <tt>v</tt> unde apare prima oară elementul <tt>e</tt>. Dacă elementul <tt>e</tt> nu apare <tt>p</tt> va avea valoarea <tt>n</tt>. O soluție elegantă care nu iese forțat din buclă și care nu folosește stegulețe este:
 
 
<syntaxhighlight>// 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</syntaxhighlight>
 
 
== Inserare în vector ==
 
Se dă un vector <tt>v</tt> de <tt>n</tt> elemente, un extra element <tt>e</tt> și o poziție <tt>p</tt>. Să se insereze elementul e la poziția <tt>p</tt>. În final elementul <tt>e</tt> va fi pe poziția <tt>p</tt> în vector, iar elementele de la poziția <tt>p</tt> 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.
 
 
<syntaxhighlight>// 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!</syntaxhighlight>
 
 
<syntaxhighlight>
 
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!</syntaxhighlight>
 
 
== Ștergere din vector ==
 
Se dă un vector <tt>v</tt> de <tt>n</tt> elemente și o poziție <tt>p</tt>. Să se elimine elementul de la poziția <tt>p</tt> din vector. Elementele de la poziția <tt>p</tt> pînă la final se vor deplasa către începutul vectorului cu o poziție.
 
 
<syntaxhighlight>// 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!</syntaxhighlight>
 
 
Varianta2:
 
 
<syntaxhighlight>// 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!</syntaxhighlight>
 
 
== Răsturnare vector ==
 
Se dă un vector <tt>v</tt> de <tt>n</tt> 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 ===
 
<syntaxhighlight>// 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--;
 
}</syntaxhighlight>
 
=== Metoda 2 ===
 
<syntaxhighlight>// 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;
 
}</syntaxhighlight>
 
 
== Rotire vector ==
 
Se dă un vector <tt>v</tt> de <tt>n</tt> elemente. Să se rotească vectorul cu o poziție către început cu o poziție. De exemplu <tt><nowiki>[1, 6, 2, 7, 4, 3, 2]</nowiki></tt> se va transforma în <tt><nowiki>[6, 2, 7, 4, 3, 2, 1]</nowiki></tt>.
 
===Rotire catre stanga===
 
<syntaxhighlight>// 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;</syntaxhighlight>
 
 
===Rotire catre dreapta===
 
<syntaxhighlight>// 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;</syntaxhighlight>
 
 
== Mutare zerouri la coadă ==
 
Se dă un vector <tt>v</tt> de <tt>n</tt> 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.
 
 
<syntaxhighlight>// 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
 
}</syntaxhighlight>
 
== Compactarea vectorului ==
 
Rezolvara problemei precedente, u pastrarea ordinii elementelor:
 
<syntaxhighlight>
 
#include <stdio.h>
 
 
int v[1000];
 
 
int main(){
 
  int i, j, n;
 
 
 
  scanf( "%d", &n );
 
  for ( i = 0; i < n; i++ )
 
    scanf( "%d", &v[i] );
 
     
 
  j = 0;
 
  for ( i = 0; i < n; i++ )
 
    if ( v[i] != 0 )
 
        v[j++] = v[i];
 
 
 
  for ( i = j; i < n; i++ )
 
    v[i] = 0;
 
 
 
  for ( i = 0; i < n; i++ )
 
    printf( "%d ", v[i] );
 
  return 0;
 
}
 
</syntaxhighlight>
 
 
== 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 <tt>v</tt> de <tt>n</tt> elemente și un număr <tt>k</tt>. Să se rotească vectorul cu o poziție către început cu <tt>k</tt> poziții. De exemplu, pentru <tt>k=3</tt> <tt><nowiki>[1, 6, 2, 7, 4, 3, 2]</nowiki></tt> se va transforma în <tt><nowiki>[7, 4, 3, 2, 1, 6, 2]</nowiki></tt>.
 
 
Rămîne ca temă pentru cei dornici să se lupte cu o problemă grea.
 
 
= Laborator =
 
* [https://www.pbinfo.ro/?pagina=probleme-lista&tag=157 Probleme pbinfo ]
 
 
===#1452 Stergere_Element===
 
Să se șteargă dintr-un șir elementul aflat pe o poziție dată.
 
<syntaxhighlight>
 
#include <stdio.h>
 
 
int v[1500];
 
int main(){
 
  int n, p, i;
 
  scanf( "%d %d", &n, &p );
 
  /// citim elementele vectorului
 
  for ( i = 0 ; i < n ; i++ )
 
    scanf("%d", &v[i] );
 
  /// voi sterge elementul de pe pozitia p-1
 
  for ( i = p ; i < n ; i++ )
 
    v[i-1] = v[i];
 
  n--;
 
  /// afisam vectorul
 
  for ( i = 0 ; i < n ; i++ )
 
    printf("%d ", v[i]);
 
  return 0;
 
}
 
</syntaxhighlight>
 
 
===#163 stergere===
 
Să se șteargă dintr-un vector toate elementele care sunt numere prime.
 
==== Metoda 1 ====
 
<syntaxhighlight>
 
#include <stdio.h>
 
int v[1000];
 
int main(){
 
  int n, i, j, d;
 
 
  scanf( "%d", &n );
 
  for ( i = 0; i < n; i++ )
 
    scanf( "%d", &v[i] );
 
 
  i = 0;
 
  while (  i < n ){
 
    /// verific daca v[i] e prim
 
    d = 2;
 
    while ( d * d <= v[i] && v[i] % d > 0 )
 
      d ++;
 
    /// daca v[i] e prim il elimin din vector
 
    if (  d * d > v[i] && v[i] > 1 ){
 
      /// voi elemina elementul de pe pozitia i prin mutarea valorilor de la i+1 la n-1
 
      for ( j = i + 1; j < n; j++ )
 
        v[j-1] = v[j];
 
      n--;
 
    }
 
    else  /// trec la urmatorul element
 
      i++;
 
  }
 
  for ( i = 0; i < n; i++ )
 
    printf( "%d ", v[i] );
 
  return 0;
 
}
 
</syntaxhighlight>
 
 
==== Metoda 2 ====
 
O metoda mai rapida de a obtine sirul de valori cerut este de a afisa valorile neprime imediat ce u fost verificate.
 
 
<syntaxhighlight>
 
#include <stdio.h>
 
 
int main(){
 
  int n, i, nr, d;
 
 
  scanf( "%d", &n );
 
  for ( i = 0; i < n; i++ ){
 
    scanf( "%d", &nr );
 
    /// verific daca numarul e prim
 
    d = 2;
 
    while ( d * d <= nr && nr % d > 0 )
 
      d ++;
 
    /// daca numarul nu e prim il afisez
 
    if ( !( d * d > nr && nr > 1) )
 
      printf( "%d ", nr );
 
  }
 
  return 0;
 
}
 
</syntaxhighlight>
 
 
===#1453 stergere1===
 
Să se șteargă dintr-un vector toate elementele pare.
 
<syntaxhighlight>
 
#include <stdio.h>
 
int v[1000];
 
int main(){
 
  int n, i, j, d;
 
 
  scanf( "%d", &n );
 
  for ( i = 0; i < n; i++ )
 
    scanf( "%d", &v[i] );
 
 
  i = 0;
 
  while (  i < n ){
 
    /// daca v[i] e par il elimin din vector
 
    if (  v[i] % 2 == 0 ){
 
      /// voi elemina elementul de pe pozitia i prin mutarea valorilor de la i+1 la n-1
 
      for ( j = i + 1; j < n; j++ )
 
        v[j-1] = v[j];
 
      n--;
 
    }
 
    else  /// trec la urmatorul element
 
      i++;
 
  }
 
  for ( i = 0; i < n; i++ )
 
    printf( "%d ", v[i] );
 
  return 0;
 
}
 
</syntaxhighlight>
 
===#158 inserare===
 
Să se insereze pe o poziție dată într-un șir o valoare precizată.
 
<syntaxhighlight>
 
#include <stdio.h>
 
 
int v[1500];
 
int main(){
 
  int n, p, i, x;
 
  scanf( "%d%d%d", &n, &x, &p );
 
  /// citim elementele vectorului
 
  for ( i = 0 ; i < n ; i++ )
 
    scanf( "%d", &v[i] );
 
  /// voi insera elementul e pe pozitia p - 1
 
  for ( i = n ; i >= p ; i-- )
 
    v[i] = v[i-1];
 
  v[p-1] = x;
 
  n++;
 
  /// afisam vectorul
 
  for ( i = 0 ; i < n ; i++ )
 
    printf( "%d ", v[i] );
 
  return 0;
 
}
 
</syntaxhighlight>
 
'''#159 inserareDupa'''
 
Să se insereze într-un șir după fiecare element par dublul său.
 
<syntaxhighlight>
 
#include <stdio.h>
 
 
int v[50];
 
int main(){
 
  int n, p, i, j, x;
 
  scanf( "%d", &n );
 
  /// citim elementele vectorului
 
  for ( i = 0 ; i < n ; i++ )
 
    scanf( "%d", &v[i] );
 
  for ( i = 0 ; i < n ; i++ ){
 
    if ( v[i] % 2 == 0 ){
 
      /// voi insera elementul 2*v[i] pe pozitia i + 1
 
      for ( j = n ; j > i + 1 ; j-- )
 
        v[j] = v[j-1];
 
      v[i+1] =2 * v[i] ;
 
      n++;
 
      ///sar peste elementul inserat
 
      i++;
 
    }
 
  }
 
  /// afisam vectorul
 
  for ( i = 0 ; i < n ; i++ )
 
    printf( "%d ", v[i] );
 
  return 0;
 
}
 
 
</syntaxhighlight>
 
'''#160 inserareInainte'''
 
Să se insereze într-un șir înaintea fiecărui element pătrat perfect rădăcina sa pătrată.
 
<syntaxhighlight>
 
</syntaxhighlight>
 
'''#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.
 
<syntaxhighlight>
 
#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;
 
}
 
</syntaxhighlight>
 
 
=== [https://www.pbinfo.ro/?pagina=probleme&id=596 #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.
 
<syntaxhighlight>
 
#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;
 
}
 
</syntaxhighlight>
 
 
= Temă =
 
Finalizati implementarea problemelor din fisa de laborator:
 
* [https://www.pbinfo.ro/?pagina=probleme-lista&tag=157 Probleme pbinfo ]
 
Rezolvați următoarele probleme:
 
* [http://varena.ro/problema/compus compus] problemă de exersat operațiile clasice pe vectori
 
 
'''Opțional''', teme de gîndire:
 
* Comparația a doi vectori: dați doi vectori, <tt>v</tt> de lungime <tt>m</tt> și <tt>w</tt> de lungime <tt>n</tt> să se spună dacă <tt>v</tt> este mai mic, egal, sau mai mare decît <tt>w</tt>. 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''': [http://varena.ro/problema/rotk rotk] (rotație multiplă vector fără a face rotații repetate cu unu).
 
 
Rezolvări aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_V-a_lec%C8%9Bia_24_-_10_feb_2015]
 
 
= Corectare tema =
 
== Comparare vectori ==
 
Fie doua siruri de caractere. Sa se afiseze cel mai mic sir, din punct de vedere lexicografic. Cele doua siruri se citesc de la tastatura.
 
 
<syntaxhighlight>
 
#include <stdio.h>
 
char a[100],b[100];
 
 
int main(){
 
  int i, j, n, m;
 
  char c;
 
  // citim primul sir de caractere
 
  n = 0;
 
  c = fgetc (stdin);
 
  while( c != '\n' ){
 
    a[n] = c;
 
    n++;
 
    c = fgetc(stdin);
 
  }
 
  // citim primul sir de caractere
 
  m = 0;
 
  c = fgetc( stdin );
 
  while( c != '\n' ){
 
    b[m] = c;
 
    m ++;
 
    c = fgetc( stdin );
 
  }
 
  //comparam cei 2 vectori si ii afisam in ordine lexicografica
 
  i = 0;
 
  while(a[i] == b[i] && i < n && i < m )
 
    i++;
 
  if( i == n ){
 
    for( j = 0; j < n; j++ )
 
      putc( a[j], stdout );
 
  }
 
  else if( i == m ){
 
    for(j = 0; j < m; j++ )
 
      putc( b[j] , stdout );
 
  }
 
  else if ( a[i] < b[i] ){
 
    for( j = 0; j < n; j++ )
 
      putc( a[j], stdout );
 
  }
 
  else {
 
    for(j = 0; j < m; j++ )
 
      putc( b[j], stdout );
 
  }
 
  return 0;
 
}
 
</syntaxhighlight>
 

Latest revision as of 13:14, 14 February 2020