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

Zone

Matrice patratica

Diagonala secundara

• 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

• 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 )

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

Sortere prin interchimbare directa

for(i=1;i<=n-1;i++)
 {
    for(j=i+1;j<=n;j++)
    {
       if(v[i]>v[j])
       {
          aux=v[i];
          v[i]=v[j];
          v[j]=aux;
       }
    }
 }

Sortarea de tip bubble

#include <iostream>
using namespace std;
int main()
{

    int n,i,v[100],ok,aux;
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>v[i];
    do
    {
        ok=0;
        for(i=1;i<n;i++)
            if(v[i]>v[i+1])
            {
                aux=v[i];
                v[i]=v[i+1];
                v[i+1]=aux;
                ok=1;
            }
    }
    while(ok==1);
    for(i=1;i<=n;i++)
    cout<<v[i]<<' ';
    return 0;
}

Obs.

1. În cazul în care toate elementele sunt ordonate crescător, algoritmul realizează n-1 comparații și nicio interschimbare.

2. În cazul în care toate elementele sunt ordonate descrescător, algoritmul realizează:

n*(n-1) comparații

((n-1)*n)/2 interschimbări