A apărut o eroare în acest obiect gadget

joi, 7 februarie 2013

Probleme Divide Et Impera



1. Calculaţi suma elementelor pare dintr-un vector de numere întregi .
2. Calculaţi suma elementelor situate pe poziţii pare dintr-un vector de numere întregi .
3. Calculaţi numărul elementelor pare dintr-un vector de numere întregi .
4. Calculaţi numărul elementelor pare şi numărul elementelor impare dintr-un vector de numere întregi .
5. Verificaţi dacă un vector de numere întregi  conţine cel puţin un element par.
6. Verificaţi dacă un vector de numere întregi  conţine toate  elementele pare.
7. Calculaţi suma cifrelor unui număr natural.
8. Calculaţi suma cifrelor pare ale unui număr natural.
9. Determinaţi min dintr-un vector de numere întregi.
10. Determinaţi min şi max dintr-un vector de numere întregi.
11.Determinaţi suma elemetelor de pe diagonala principală a unei matrici de numere întregi pătratică.
12.Determinaţi suma elemetelor de pe diagonala secundară  a unei matrici de numere întregi pătratică.
13.Căutarea binară
14 Sortarea rapidă
15.Sortarea prin interclasare
16.Turnurile lui Hanoi



joi, 17 ianuarie 2013

Probleme olimpiada clasa IXa (intensiv) aXa (neintensiv)

Scaderea numerelor mari
Numerele naturale cu foarte multe cifre se pot memora cu ajutorul vectorilor. Sa se calculeze si sa se afiseza diferenta a doua numere naturale memorate in 2 vectori a si b cu n si respectiv m elemente.
Cifrele numerelor se vor introduce de la tastatura fara spatiu intre ele.
Exemplu: vezi figura alaturata

#include<iostream>
using namespace std;

void citire(int a[1000], int &n)
{
	char cif;
	int i;
	cin>>n;
	for(i=n;i>=1;i--)
		{ cin>>cif;
	      a[i]=cif-48;//transform sin cifra in numar (cifa este caracter)
		} 
}

int maimare(int a[1000], int n, int b[1000], int m)
{
	int i;
	if(n>=m) return 1;
		else if(n<m) return 0;
	         else
			 { 
				 i=m;
				 while(a[i]==b[i]) i--;
				 if(a[i]>=b[i]) return 1;
                 else return 0;				 
			 }				 
}

int main()
{
	int a[1000],b[1000],s[1000],n,m,p,i,k,semn,aux;
	citire(a,n);
	citire(b,m);
	if(maimare(a,n,b,m)==0)
	{//b>a
		p=m;
	    for(i=n+1;i<=m;i++) a[i]=0;
	    for(i=1;i<=p;i++) s[i]=b[i]; //pun pe b in s
		semn=-1;
		for(i=1;i<=p;i++) b[i]=a[i];// pun pe a in b;
	}
	else //a>b
	{	p=n;
		for(i=m+1;i<=n;i++) b[i]=0;
		for(i=1;i<=p;i++) s[i]=a[i]; //pun pe a in s;
	}
	for(i=1;i<=p;i++)
	{
		if(s[i]>=b[i]) s[i]=s[i]-b[i];
		else
		{ //ma imprumut
			k=i+1;
			while(s[k]==0) { s[k]=9; k++;}
			s[k]--;
			s[i]=10+s[i]-b[i];
		}
	}
	if(semn==-1) cout<<"-";
	while(s[p]==0) p--;
	for(i=p;i>=1;i--) cout<<s[i];
	return 0;
}
 

Probleme combinatorica


1. Sa se genereze si sa numere toate numerele formate din p cifre distincte avand cifrele ordonate crescator.
#include<iostream>

using namespace std;

int x[100],p,nr=0;

void Write()
{ for(int i=1;i<=p;i++) cout<<x[i];
  cout<<endl;
  nr++;
}

void Comb(int k)
{ for(int i=x[k-1]+1;i<=9;i++)
     { x[k]=i;
       if(k==p) Write();
       else Comb(k+1);
      }
}           

int main()
{ cin>>p;
  Comb(1);
  cout<<nr;
 
}

2. Sa se genereze si sa numere toate permutarile multimii {1,2,3,...,n} care incep cu valoarea 1.  
#include<iostream>
 
using namespace std;
 
int x[100],pus[100],n,nr=0;
 
void Write()
{ for(int i=1;i<=n;i++) cout<<x[i]<<" ";
  cout<<endl;
  nr++;
}
void Perm(int k)
{  for(int i=1;i<=n;i++)
     if(!pus[i])
        { x[k]=i;
          pus[i]=1;
          if(k==n) Write();
          else Perm(k+1);
          pus[i]=0;
          } 
}
 
int main()
{ cin>>n;
  x[1]=1;
  pus[1]=1;
  Perm(2);
  cout<<nr;
  }  
3. Sa se genereze si sa numere toate permutarile multimii {1,2,3,...,n} care au proprietatea ca oricare doua elemente alaturate au paritate diferita.
Ex: pentru n=4:
1 2 3 4
1 4 3 2
2 1 4 3
...
4 3 2 1

#include<iostream>

using namespace std;

int x[100],pus[100],n,nr=0;

void Write()
{ for(int i=1;i<=n;i++) cout<<x[i]<<" ";
  cout<<endl;
  nr++;
}
void Perm(int k)
{  for(int i=1;i<=n;i++)
     if(!pus[i])
        { x[k]=i;
          pus[i]=1;
          if(x[k]%2!=x[k-1]%2 || k==1)
             if(k==n) Write();
             else Perm(k+1);
          pus[i]=0;
          }
}

int main()
{ cin>>n;
  Perm(1);
  cout<<nr;
 

} 
4. Sa se genereze si sa numere toate submultimile multimii {1,2,3,...,n}.

#include<iostream>

using namespace std;

int x[100],pus[100],n,nr=0;

void Write()
{ for(int i=1;i<=n;i++) if(x[i]) cout<<i<<" ";
  cout<<endl;
  nr++;
}

void Sub(int k)
{ for(int i=1;i>=0;i--)
   {
          x[k]=i;;
          if(k==n) Write();
          else Sub(k+1);
   }     
}
int main()
{ cin>>n;
  Sub(1);
  cout<<nr;
  system("pause");
  return 0;
} 
5. Sa se genereze si sa numere toate permutarile multimii {1,2,3,...,n}.

#include<iostream>

using namespace std;

int x[100],pus[100],n,nr=0;

void Write()
{ for(int i=1;i<=n;i++) cout<<x[i]<<" ";
  cout<<endl;
  nr++;
}
void Perm(int k)
{  for(int i=1;i<=n;i++)
     if(!pus[i])
        { x[k]=i;
          pus[i]=1;
          if(k==n) Write();
          else Perm(k+1);
          pus[i]=0;
          }
}

int main()
{ cin>>n;
  Perm(1);
  cout<<nr;
 
} 
6. Sa se genereze si sa numere toate aranjamentele de cate p elemente ale multimii {1,2,3,...,n}.

#include<iostream>

using namespace std;

int x[100],pus[100],n,p,nr=0;

void Write()
{ for(int i=1;i<=p;i++) cout<<x[i]<<" ";
  cout<<endl;
  nr++;
}
void Aranj(int k)
{  for(int i=1;i<=n;i++)
     if(!pus[i])
        { x[k]=i;
          pus[i]=1;
          if(k==p) Write();
          else Aranj(k+1);
          pus[i]=0;
          }
}

int main()
{ cin>>n>>p;
  Aranj(1);
  cout<<nr;
  system("pause");
  return 0;
} 
7. Sa se genereze si sa numere toate submultimile de cate p elemente ale multimii {1,2,3,...,n}.

#include<iostream>

using namespace std;

int x[100],n,p,nr=0;

void Write()
{ for(int i=1;i<=p;i++) cout<<x[i]<<" ";
  cout<<endl;
  nr++;
}

void Comb(int k)
{ for(int i=x[k-1]+1;i<=n;i++)
     { x[k]=i;
       if(k==p) Write();
       else Comb(k+1);
      }
}           

int main()
{ cin>>n>>p;
  Comb(1);
  cout<<nr;
 
} 
8. Se citeste un numar natural n si un numar natural p mai mic decat n. Sa se descompuna n in toate modurile ca suma de p numere naturale.

#include<iostream>

using namespace std;

int x[100],n,p,nr=0;

void Write()
{  
     for(int i=1;i<=p;i++) cout<<x[i]<<" ";
     cout<<endl;
     nr++;
}

int suma(int k)
{
    int s=0;
    for(int i=1;i<=k;i++) s=s+x[i];
    return s;
}

void Comb(int k)
{ for(int i=x[k-1]+1;i<=n;i++)
     { x[k]=i;
       if(suma(k)<=n)
          if(k<p) Comb(k+1);
          else
            if(k==p) if (suma(k)==n) Write();
      }
}           

int main()
{ cin>>n>>p;
  Comb(1);
  cout<<nr;
 

} 
9. Sa se genereze toate numerele formate din 5 cifre impare distincte.

#include<iostream>

using namespace std;

int x[100],pus[100],n,nr=0;

void Write()
{ for(int i=1;i<=n;i++) cout<<x[i];
  cout<<endl;
  nr++;
}
void Perm(int k)
{  for(int i=1;i<=9;i=i+2)
     if(!pus[i])
        { x[k]=i;
          pus[i]=1;
          if(k==n) Write();
          else Perm(k+1);
          pus[i]=0;
         }
}

int main()
{ n=5;
  Perm(1);
  cout<<nr;
 
} 
10. Se citeste un cuvant format doar din litere mici distincte. Sa se genereze anagramele lui.

#include<iostream>

using namespace std;

int x[100],pus[100],n,nr=0;
char s[100];

void Write()
{ for(int i=1;i<=n;i++) cout<<s[x[i]-1];
  cout<<endl;
  nr++;
}
void Perm(int k)
{  for(int i=1;i<=n;i++)
     if(!pus[i])
        { x[k]=i;
          pus[i]=1;
          if(k==n) Write();
          else Perm(k+1);
          pus[i]=0;
         }
}

int main()
{ cin>>s;
  n=strlen(s);
  Perm(1);
  cout<<nr;
 
}