Matrici patratice

Simetrii

  • Fata de diagonala principala  
    • for(i=1;i<=n&&ok;i++)
      for(j=1;j<=n;j++)
      if(a[i][j]!=a[j][i])ok=0;

 

  • Fata de diagonala secundara
    • for(i=1;i<=n-1&&ok;i++)
      for(j=1;j<=n-i;j++)
      if(a[i][j]!=a[n+1-j][n+1-i])ok=0;

 

  • Fata de axa Ox
    • for(i=1;i<=n/2&&ok;i++)
      for(j=1;j<=n;j++)
      if(a[i][j]!=a[n+1-i][j])ok=0;

 

  • Fata de axa Ox
    • for(i=1;i<=n&&ok;i++)
      for(j=1;j<=n/2;j++)
      if(a[i][j]!=a[i][n+1-j])ok=0;

 

 

Matrice patratica

Diagonala secundara

diag sec.PNG

  • Pe diagonala:

Forma: a[i][j]  cu  i+j=n+1  ( i=1,n ; j=1,n )    => j=n+1-i

  • Deasupra diagonalei:

 

Forma:  a[i][j]  cu  i+j<n+1  ( i=1,n ; j=1,n )   => j<n+1-i

Eficient: a[i][j]  cu  ( i=1,n-1 ; j=1,n-i )

  • Sub diagonala secundara:

 

Forma: a[i][j]  cu  i+j>n+1   ( i=1,n ; j=1,n )   => j>n+1-i

Eficient: a[i][j]  cu  ( i+2,n ; j=n+2-i,n )

Matrice patratica

Diagonala principala

diag princ.PNG

  • Pe diagonala:

Forma: a[i][j]  cu  i=j  ( i=1,n  ;  j=1,n )

Eficient: a[i][i]  cu ( i=1,n )

  • Deasupra diagonalei principale:

 

Forma: a[i][j]  cu  i<j  ( i=1,n  ;  j=1,n )

Eficient: a[i][j]  cu  ( i=1,n-1  ;  j=i+1,n )

  • Sub diagonala principala:

 

Forma: a[i][j]  cu  i>j  ( i=1,n  ;  j=1,n )

Eficient: a[i][j]  cu   ( i=2,n  ;  j=1,i-1 )

Matrici

Matricile reprezinta tablouri bidimensionale.

Fie A matrice cu 3 linii si 4 coloane. Atunci:

  • A[1] = linia 1;
  • A[2] = linia 2;
  • A[3] = linia 3;
  • A[1][2] = elementul de pe linia 1 coloana 2;
  • A[2][3] = elementul de pe linia 2 coloana 3;
  • A[4][2] = elementul de pe linia 4 coloana 2;

Asadar,

  • A = intreaga matrice;
  • A[i] = vector = linia i;
  • A[i][j] = elementul de pe linia i coloana j;

Declarare

tip variabila [dim1][dim2];

exemple:

  • int a[4][5] – matrice cu 4 linii si 5 coloane, elemente intregi, liniile numerotate de la 0 la 3 si coloanele de la 0 la 4;
  • float b[10][20] – matrice cu 10 linii numerotate de la 0 la 9, 20 de coloane numerotate de la 0 la 19 si elemente de tip real;

Declarare + initializare

  • int a[3] [2] = { {1,2}, {3,4}, {5,6} };

 

Vectori de frecventa/caracteristici

Pasii ce trebuiesc urmati pentru utilizarea vectorilor caracteristici/de frecventa sunt:

  1. identificarea lungimii vectorului (v[10], v[100]…);
  2. initializarea vectorului cu 0;
  3. citirea datelor de intrare si actualizarea vectorului de frecventa;
  4. parcurgerea vectorului de frecv si afisarea modificarilor.

Astfel:

  • i = numar;
  • v[i] = frecventa numarului.

 

De exemplu ,acest algoritm va forma cel mai mic numar format din cifrele unui numar citit la tastatura:

int main()
{
 int v[10],c,i;
 long long x;
 for(i=0;i<=9;i++)
 v[i]=0;
 fin>>x;
 while(x!=0)
 {
    c=x%10;
    x=x/10;
    v[c]++;
 }
 for(i=9;i>=0;i--)
 if(v[i]!=0){fout<<i;v[i]--;}
 return 0;
}

sau, pentru a forma numarul cu cifrele distincte:

int main()
{
 int v[10],c,i;
 long long x;
 for(i=0;i<=9;i++)
 v[i]=0;
 fin>>x;
 while(x!=0)
 {
 c=x%10;
 x=x/10;
 v[c]=1;
 }
 for(i=9;i>=0;i--)
 if(v[i])fout<<i;
 return 0;
}

Interclasare

   Metoda interclasarii foloseste cel putin 2 vectori ordonati pentru a creea un alt vector ordonat ce contine toate elementele acestora.

Acest exemplu foloseste 2 vectori ordonati crescator si formeaza un al treilea continand toatele elementele lor in ordine crescatoare.

int main()
{
 int a[20],b[30],c[50],m,n,i,j,k;
 cin>>n>>m;
 for(i=1;i<=n;i++)fin>>a[i];
 for(j=1;j<=m;j++)fin>>b[j];
 i=1;j=1;k=0;
 while(i<=n&&j<=m)
 {
     if(a[i]<=b[j])c[++k]=a[i++];
     else c[++k]=b[j++];
 }
 while(i<=n)c[++k]=a[i++];
 while(j<=m)c[++k]=b[j++];
 for(i=1;i<=k;i++)
     cout<<c[i]<<' ';
 return 0;
}

explicatie: a=1,3,5,7,8;       b=2,4,6,8;        c=1,2,3,4,5,6,7,8.

-a crescator;                                                                                                                                                           b descrescator;                                                                                                                                                     c crescator:

int main()
{
 int a[20],b[30],c[50],i,j,n,m,k;
 fin>>n>>m;
 for(i=1;i<=n;i++)fin>>a[i];
 for(j=1;j<=m;j++)fin>>b[j];
 i=1;j=m;k=0;
 while(i<=n&&j>=1)
 {
     if(a[i]<b[j])c[++k]=a[i++];
     else c[++k]=b[j--];
 }
 while(i<=n)c[++k]=a[i++];
 while(j>=1)c[++k]=b[j--];
 for(i=1;i<=k;i++)fout<<c[i]<<' ';
 return 0;
}

-a descrescator;                                                                                                                                                     b descrescator;                                                                                                                                                     c crescator:

int main()
{
 int a[20],b[30],c[50],n,m,j,i,k;
 fin>>n>>m;
 for(i=1;i<=n;i++)fin>>a[i];
 for(j=1;j<=m;j++)fin>>b[j];
 i=n;j=m;k=0;
 while(i>=1&&j>=1)
 {
     if(a[i]<b[j])c[++k]=a[i--];
     else c[++k]=b[j--];
 }
 while(i>=1)c[++k]=a[i--];
 while(j>=1)c[++k]=b[i--];
 for(i=1;i<=k;i++)
     fout<<c[i]<<' ';
 return 0;
}

-a crescator;                                                                                                                                                           b descrescator;                                                                                                                                                     c descrescator:

int main()
{
 int a[20],b[30],c[50],m,n,i,j,k;
 fin>>n>>m;
 for(i=1;i<=n;i++)fin>>a[i];
 for(j=1;j<=m;j++)fin>>b[j];
 i=n;
 j=1;k=0;
 while(i>=1&&j<=m)
 {
 if(a[i]>b[j])c[++k]=a[i--];
 else if(a[i]==b[j]){c[++k]=a[i--];j++;}
 else c[++k]=b[j++];
 }
 while(i>=1)c[++k]=a[i--];
 while(j<=m)c[++k]=b[j++];
 for(i=1;i<=k;i++)
 fout<<c[i]<<' ';
 return 0;
}

Sortare prin selectie

Sortare prin selectia elementului maxim:

int main()
 {
 int maxi,p,i,n,v[100],j,aux;
 cin>>n;
 for(i=1;i<=n;i++)
  cin>>v[i];
 for(i=n;i>=2;i--)
 {
  maxi=v[1];p=1;
  for(j=1;j<=i;j++)
  if(v[j]>maxi)
  {
   maxi=v[j];
   p=j;
  }
  aux=v[i];
  v[i]=v[p];
  v[p]=aux;
 }
 for(i=1;i<=n;i++)
  cout<<v[i]<<' ';
 return 0;
 }

Sortare prin selectia elementului minim:

int main()
{
 int n,i,mini,p,j,aux,v[100];
 cin>>n;
 for(i=1;i<=n;i++)
  cin>>v[i];
 for(i=1;i<=n-1;i++)
 {
  mini=v[i];
  p=i;
  for(j=i+1;j<=n;j++)
  if (v[j]<mini)
  {
   mini=v[j];
   p=j;
  }
  aux=v[i];
  v[i]=v[p];
  v[p]=aux;
 }
 for(i=1;i<=n;i++) cout<<v[i]<<' ';
 return 0;
}