Descompunere numar, rezolvare ecuatie

Combinari n,k - programare dinamica

# include <conio.h>;
# include <iostream.h>;

# define MAX 50

int a,b;
int c[MAX][MAX];
int i,j;

int comb(int n,int k)
{
if(c[n][k]>=1) return c[n][k];
else
 {
  c[n][k]=comb(n-1,k)+comb(n-1,k-1);
  c[n][n-k]=c[n][k];
  return c[n][k];
 }
}

void main(void)
{
clrscr();

cout<<"Intr n,k :\n";
 cin>>a>>b;

for(i=0;i<a;i++)
 for(j=0;j<b;j++)
  c[i][j]=-1;

for(i=0;i<a;i++)
{
c[i][0]=1;
c[i][i]=1;
if(i>=1)
 {
 c[i][1]=i;
 c[i][i-1]=i;
 }
}

cout<<"\ncomb("<<a<<","<<b<<")= "<<comb(a,b);

getche();
}

Combinari n,k - recursiv

# include <conio.h>;
# include <iostream.h>;

int a,b;

int comb(int n,int k)
{
if(k==n) return 1;
else if(k<=1) return n;
else return (comb(n-1,k)+comb(n-1,k-1));
}

void main(void)
{
clrscr();

cout<<"Intr n,k :\n";
 cin>>a>>b;
cout<<"\ncomb("<<a<<","<<b<<")= "<<comb(a,b);

getche();
}

Sortare Selectie

# include <iostream.h>;
# include <conio.h>;

# define MAX 10

int n,i,j,k;
int sch;
typedef int sir[MAX];
sir s;

void main(void)
{
clrscr();
 cout<<"Intr nr de elemente: ";
  cin>>n;

 for(i=0;i<n;i++)
  cin>>s[i];

 for(k=0;k<n-1;k++)
 {
  sch=0;
  i=k;
  for(j=k+1;j<n;j++)
   if(s[j]<s[i])
    {
     i=j;
     sch=1;
    }
   if(sch)
   {
    s[i]=s[i]^s[k];
    s[k]=s[i]^s[k];
    s[i]=s[i]^s[k];
   }
 }

cout<<"\nSirul sortat este:\n";
for(i=0;i<n;i++)
 cout<<s[i]<<" ";

getche();
}

Fib - programare dinamica

//fib(75) = OK

# include <conio.h>;
# include <iostream.h>;

# define MAX 5000

int n;
long int f[MAX];
long int i;

long int fib(long int n)
{
if(f[n]!=-1) return f[n];
else
 {
  f[n]=fib(n-1)+fib(n-2);
  return f[n];
 }
}

void main(void)
{
clrscr();

for(i=0;i<MAX;i++)
  f[i]=-1;
f[0]=f[1]=1;

cout<<"Intr n :\n";
 cin>>n;
cout<<"\nfib("<<n<<")= "<<fib(n);

getche();
}

Interclasare Fisiere

# include <stdio.h>;
# include <conio.h>;

FILE *pf1, *pf2, *pf3;
int n1,n2,n3;

void main(void)
{
clrscr();

pf1=fopen("fis1.txt","r");
pf2=fopen("fis2.txt","r");
pf3=fopen("fis3.txt","w+");

fscanf(pf1,"%d",&n1);
fscanf(pf2,"%d",&n2);

int f=0;

while(!feof(pf1)&&(!feof(pf2)))
{
 if(f==1)
  fscanf(pf1,"%d",&n1);
 if(f==2)
  fscanf(pf2,"%d",&n2);
 if(n1<n2)
  {
   fprintf(pf3,"%d\n",n1);
   f=1;
  }
 else
  {
   fprintf(pf3,"%d\n",n2);
   f=2;
  }
}

FILE * aux;
int n=0;

if(feof(pf1) && (!feof(pf2)))
 {
  aux=pf2;
  while(n2<=n1)
  {
   fprintf(pf3,"%d\n",n2);
    fscanf(pf2,"%d",&n2);
  }
  fprintf(pf3,"%d\n",n2);

 }
else if((!feof(pf1)) && feof(pf2))
 {
  aux=pf1;

  while(n1<=n2)
  {
   fprintf(pf3,"%d\n",n1);
    fscanf(pf1,"%d",&n1);
  }
  fprintf(pf3,"%d\n",n1);

 }

while(!feof(aux))
 {
  fscanf(aux,"%d",&n);
  fprintf(pf3,"%d\n",n);
 }

fclose(pf1);
fclose(pf2);
fclose(pf3);

getche();
}

2 la N - vectori

# include<stdio.h>
# include<conio.h>

# define MAX 100

int i,k,j,n,r[MAX],fr[MAX];
int nrcif=1;

int main(void)
{
//clrscr();

printf("Intr n: ");
 scanf("%d",&n);

r[0]=1;
fr[0]=1;

for(k=0;k<n;k++)
 {
 r[0]=(2*r[0])%10;
 i=1;
 while(i<=nrcif)
  {
   r[i]=(2*r[i])%10+(2*fr[i-1])/10;
   i++;
  }
 if(2*r[nrcif-1]>=10) nrcif++;
 for(j=0;j<i;j++) fr[j]=r[j];
 }

printf("\n");

for(j=0;j<nrcif;j++)
 printf("%d ",r[j]);

getche();
return 0;
}

Functie MAIN cu argumente

//Pt executia prg. trebuie sa fie setata optiunea:
// Options->Compiler->Source->Borland C++ (in ANSI mai intervine un parametru)
//
//Programul se ruleaza din File->Dos Shell cu comanda, ex: par_main 2 13 41
// nu cu Ctrl+F9
# include <stdio.h>;
# include <conio.h>;
# include <stdlib.h>;
void main(int argc,char ** argv)
{
clrscr();
//Variabilele de apel sunt depuse pe stiva de la dreapta spre stanga

//argv==matrice, tablou de pointeri la siruri

++argv;//*argv=="c:\....\pra_main.exe"
++argv;//*argv==argc (de tip char*=string=char[])

//arrgc=nr. de parametri inclusiv numele prg. de apel plus nr de
// parametri(2 - vezi ex.)
--argc;
--argc;
while(argc--)
 {
 printf("%s",*argv);
 printf(" %d\n",atoi(*argv));
 argv++;
 }
getche();
}

Sortare prin insertie - iterativ

# include <iostream.h>;
# include <conio.h>;

# define MAX 10

int n,i,j,aux;
typedef int sir[MAX];
sir s;

void main(void)
{
clrscr();
 cout<<"Intr nr de elemente: ";
  cin>>n;

 cin>>s[0];
 for(i=1;i<n;i++)
  {
   j=i;
   cin>>s[i];
   aux=s[i];
   while((aux<s[j-1])&&(j>=0))
   {
   s[j]=s[j-1];
   j--;
   }
   s[j]=aux;
  }

cout<<"\nSirul sortat este:\n";
for(i=0;i<n;i++)
 cout<<s[i]<<" ";

getche();
}

Inmultire matrici

# include <iostream.h>;
# include <conio.h>;

# define MAX 50

int i,j,m,n,p;
float a[MAX][MAX],b[MAX][MAX],c[MAX][MAX];

void inm(int xs_A,int ys_A,int xd_A,int yd_A,int xs_B,int ys_B,int xd_B,int yd_B)
{
 if( ((xd_A-xs_A<=1)&&(yd_A-ys_A<=1))
    && ((xd_B-xs_B<=1)&&(yd_B-ys_B<=1)) )
    {
     if((xs_A==xd_A)||(xs_B==xd_B))
       c[xs_A][ys_A]=a[xs_A][ys_A]*b[xs_B][ys_B]+a[xs_A][yd_A]*b[xs_B][yd_B];

     if((xs_A==yd_A)||(xs_B==yd_B))
       c[xs_A][yd_A]=a[xs_A][ys_A]*b[xs_B][yd_B]+a[xs_A][yd_A]*b[xd_B][yd_B];

     if((xd_A==ys_A)||(xd_B==ys_B))
       c[xd_A][ys_A]=a[xd_A][ys_A]*b[xs_B][ys_B]+a[xd_A][yd_A]*b[xd_B][ys_B];

     if((ys_A==yd_A)||(ys_B==yd_B))
       c[xd_A][yd_A]=a[xd_A][ys_A]*b[xs_B][yd_B]+a[xd_A][yd_A]*b[xd_B][yd_B];
    }

/* else if() //64 cazuri
  {
   ...
  }*/

 else
  {
   int xm_A,ym_A,xm_B,ym_B;
   xm_A=(xs_A+xd_A)/2;
   ym_A=(ys_A+yd_A)/2;
   xm_B=(xs_B+xd_B)/2;
   ym_B=(ys_B+yd_B)/2;

   inm(xs_A,ys_A,xm_A,ym_A,xs_B,ys_B,xm_B,ym_B);
   inm(xs_A,ym_A,xm_A,yd_A,xs_B,ym_B,xm_B,yd_B);
   inm(xm_A,ys_A,xd_A,ym_A,xm_B,ys_B,xd_B,ym_B);
   inm(xm_A,ym_A,xd_A,yd_A,xm_B,ym_B,xd_B,yd_B);
  }

}

void main(void)
{
clrscr();

//Citire matici
cout<<"Intr dimensiunile primei matrici:\n";
 cin>>m>>n;
cout<<"\nIntr dimensiunile celei de a doua matrici:\n";
 cin>>n>>p;
cout<<"\nIntr elementele din prima matrice:\n";
for(i=0;i<m;i++)
 for(j=0;j<n;j++)
  cin>>a[i][j];
cout<<"\nIntr elementele din a doua matrice:\n";
for(i=0;i<n;i++)
 for(j=0;j<p;j++)
  cin>>b[i][j];


//
 inm(0,0,m-1,n-1,0,0,n-1,p-1);
//


//Afisare rezultat
cout<<"\nMatricea produs este:\n";
for(i=0;i<m;i++)
 {
  for(j=0;j<p;j++)
    cout<<c[i][j]<<" ";
  cout<<"\n";
 }

getche();
}

FOR - recursiv

# include <iostream.h>;
# include <conio.h>;

int n;

void forr(int i)
{
 if(i>n) return;
 forr(i+1);
 cout<<i<<" ";
}

void forr2(int j)
{
if(j<=0) return;
forr2(j-1);
forr(j);
cout<<"\n";
}

void main(void)
{
clrscr();
cout<<"Intr n= ";
 cin>>n;

 forr2(n);

getche();
}

Turnurile din HANOI - recursiv

//TURNURILE DIN HANOI
#include<iostream.h>
#include<conio.h>
#include<stdio.h>

int n;
char a,b,c;
void hanoi(int n,char a,char b,char c)
{ if(n==1)
     cout<<"\n"<<a<<b;
   else
    { hanoi(n-1,a,c,b);
     cout<<"\n"<<a<<b;
     hanoi(n-1,c,b,a);
    }
    }


void main()
{ cout<<"Numarul de discuri n=";  cin>>n;
  a='A';
  b='B';
  c='C';
   hanoi(n,a,b,c);
  getch();
}

Determinare puncte SA dintr-o matrice

//Program care determina punctele SA intr-o matrice

# include <iostream.h>;
# include <conio.h>;
# include <values.h>;

# define MAX 10

int i,j,n;
int m[MAX][MAX];
int minmax,max;
int min,poz;

void main(void)
{
clrscr();

//Citire date
cout<<"\nIntr dimensiunea matr. :\n";
 cin>>n;
for(i=0;i<n;i++)
 for(j=0;j<n;j++)
 {
 cout<<"m["<<i<<","<<j<<"]= ";
 cin>>m[i][j];
 }

//Cautam cel mai mic maxim pe coloane
minmax=MAXINT;
for(i=0;i<n;i++)
 {
 max=-MAXINT;
 for(j=0;j<n;j++)
  if(m[j][i]>max) max=m[j][i];
 if(minmax>max) minmax=max;
 }
//Cautam un minim pe linie egal cu cel mai mic maxim pe coloane
for(i=0;i<n;i++)
 {
 min=MAXINT;
 for(j=0;j<n;j++)
  if(min>m[i][j]) {min=m[i][j];poz=j;}
 if(min==minmax) cout<<"\nPunct SA pe poazitia ("<<i<<","<<poz<<")\n";
 }

cout<<"\nGATA...";
getche();
}

Parcurgere circulara matrice

#include<iostream.h>
#include<conio.h>
void main()
{ int i,j,a[100][100],n;
cout<<"se citeste matricea:";
cout<<"n=";   cin>>n;
for(i=0;i<n;i++)
 for(j=0;j<n;j++)
 {cout <<"a["<<i<<"]["<<j<<"]=";
  cin>>a[i][j];
 }
 //k=14;
 for(i=0;i<=n/2;i++)
 {for(j=i;j<=n-i-1;j++)   cout<<a[i][j];   //a[i][j]=k+5;
  for(j=i+1;j<=n-i-1;j++)   cout<<a[j][n-i-1]; //k+4
  for(j=n-i-2;j>=i+1;j--) cout<<a[n-i-1][j];   //k+5
  for(j=n-i-1;j>=i+1;j--) cout<<a[j][i];      //k+4
  }
  getch();

  }

Maxim sir - Divide et Impera - Iterativ

# include <stdio.h>;
# include <conio.h>;
# include <values.h>;

# define MAX 100 //maxim 100 de elemente in sir

int i,n,val,a[MAX];

void main(void)
{
clrscr();

printf("Intr nr de elemente din sir: ");
 scanf("%d",&n);
printf("\nIntr elementele sirului:\n");
 for(i=0;i<n;i++)
  scanf("%d",&a[i]);

int s,d,mij;
int max,max1,max2;

s=0;
d=n;
mij=(s+d)/2;

max=max1=max2=-MAXINT;

int gasit=1;
while((s<=d)&&(gasit==1))
 {
  gasit=0;
  s=0;
  d=n;
  mij=(s+d)/2;


  while(a[mij+1]>max) {max1=a[mij+1]; s=mij+1;gasit=1;}
  while(a[mij-1]>max) {max2=a[mij-1]; d=mij-1;gasit=1;}
  if(max1>max2) max=max1;
  else max=max2;
 }

printf("\nMAX din sir este: %d",max);

getche();
}

Parcurgere matrice in spirala

//parcurgerea matricei in spirala
#include<iostream.h>
#include<stdio.h>
#include<conio.h>
FILE*f;
int g(int &k)
{
 int i,gata=0,s=0,aux=0;
 i=k;
  while(gata==0)
 {
 gata=0;
 s=0;
 aux=i;
 while(aux!=0){
 s=s+aux%10;
 aux=aux/10;
   }
  if(s%5==0)
   gata=1;
 i++;
 }
 k=i-1;
 return k;
}
void main()
{
int a[20][20],n,i,j,k;
clrscr();
f=fopen("matrice.txt","r");
/*fscanf(f,"%d",&n);
for(i=0;i<n;i++)
  for(j=0;j<n;j++)
    fscanf(f,"%d",&a[i][j]);*/
     cout<<"Dati n=";
   cin>>n;
    k=13;
for(i=0;i<n;i++)
 {
   for(j=i;j<n-i;j++)
     a[i][j]=g(++k);
   for(j=i+1;j<n-i;j++)
     a[j][n-1-i]=g(++k);
   for(j=n-i-2;j>i;j--)
     a[n-1-i][j]=g(++k);
   for(j=n-i-1;j>i;j--)
     a[j][i]=g(++k);
   }

   for(i=0;i<n;i++) {
     for(j=0;j<n;j++)
       cout<<a[i][j]<<" ";
       cout<<endl;
       }
       fclose(f);
   getch();
}

Operatii cu multimi, vectori caracteristici

//
//Operatii cu vectori caracteristici
//

# include <stdio.h>;
# include <conio.h>;

int a[100],b[100],c[100],d[100];
int i,j,k,n,m,val;

void main(void)
{
clrscr();

printf("Introduceti nr de elemente din prima multime: ");
 scanf("%d",&m);
printf("\nIntroduceti nr de elemente din a doua multime: ");
 scanf("%d",&n);

//Citirea primei multimi / sir
int aux1=m;
printf("\nIntroduceti prima multime:\n");
for(i=0;i<aux1;i++)
 {
  scanf("%d",&val);
  a[val]=1;
  if(val>m) m=val;
 }

//Citirea celei de a doua multimi
int aux2=n;
printf("\nIntroduceti a doua multime:\n");
for(i=0;i<aux2;i++)
 {
  scanf("%d",&val);
  b[val]=1;
  if(val>n) n=val;
 }

//Determinare intersectie
for(k=0;k<n;k++)
 if((a[k]==1)&&(b[k]==1))
  c[k]=1;

//Afisare intersectie
printf("\nIntersectia celor doua multimi este:\n");
for(k=0;k<n;k++)
 if(c[k]==1)
    printf("%d ",k);

getche();
}

//Reuniune, Diferenta TEMA

Verificare numar prim

//Prg care verifica daca un nr e prim
# include <stdio.h>;
# include <conio.h>;
# include <math.h>;

int n,i,ep; //i= variabila de contor, ep= este prim

void main(void)
{
clrscr();//curata ecranul
printf("Intr n: ");
 scanf("%d",&n);

ep=1;//presupunem ca este prim
 for(i=2;i<= floor( sqrt(n) );i++)
  if((n%i) == 0) //daca am gasit un divizor atunci
   ep=0; //n nu mai este prim

//Afisez rezultatul
if(ep) printf("\nNumarul este prim");
else   printf("\nNumarul NU este prim");

getche();//mentine ecranul de executie pana la apasarea unei taste
}`

Interclasare siruri sortate

# include <stdio.h>;
# include <conio.h>;

int n,m,a[100],b[100],c[200];
int i,j,k;

void main(void)
{
clrscr();

//Citire vectori
printf("Intr nr de elem din primul sir: ");
 scanf("%d",&n);
printf("Intr nr de elem din al doilea sir: ");
 scanf("%d",&m);
printf("\nIntr elementele primului sir:\n");
for(i=0;i<n;i++)
 scanf("%d",&a[i]);
printf("\nIntr elementele din al doilea sir:\n");
for(j=0;j<m;j++)
 scanf("%d",&b[j]);

//Interclasare
i=0;
j=0;
k=0;
while((i<n)&&(j<m))
{
if(a[i]<b[j])
 c[k++]=a[i++];
else
 c[k++]=b[j++];
}
//Copierea elementelor ramase
if(i>=n)
 for(i=j;i<m;i++)
  c[k++]=b[i];
if(j>=m)
 for(j=i;j<n;j++)
  c[k++]=a[j];

//Afisare rezultat
printf("\nVectorii interclasati :\n");
for(k=0;k<m+n;k++)
printf("%d ",c[k]);

getche();
}

Cautare binara clasica

# include <stdio.h>;
# include <conio.h>;

# define MAX 100 //maxim 100 de elemente in sir

int i,n,val,a[MAX];

void main(void)
{
clrscr();

printf("Intr nr de elemente din sir: "); //pp sirul sortat
 scanf("%d",&n);
printf("\nIntr elementele sirului:\n");
 for(i=0;i<n;i++)
  scanf("%d",&a[i]);
printf("\nIntr valoarea cautata: ");
 scanf("%d",&val);

int s,d,mij;
int gasit;

s=0;
d=n;
mij=(s+d)/2;
gasit=0; //pp ca valoarea nu se afla in sir

while((s<=d)&&(gasit==0))
 {
  mij=(s+d)/2;
  if(val==a[mij]) {gasit=1; printf("\Val gasita pe poz %d",mij);}
  else if(a[mij]<val) s=mij+1;
  else if(a[mij]>val) d=mij-1;
 }
if(gasit==0) printf("\nValoarea nu se afla in sir !!!");

getche();
}

Cautare secventiala

//Cautare secventiala
# include <iostream.h>;
# include <conio.h>;
# include <stdlib.h>; //pt functia random(...)

# define N 100
//dimensiunea - nr de elemente din sir

int i,n,val,poz,v[N];

void main(void)
{
clrscr();
cout<<"Intr nr de elemente din sir: ";
 cin>>n;

//Generez elemente aleatoare
for(i=0;i<n;i++)
 v[i]=random(n);
//genereaza numere aleatoare intre 0 si n-1

//Afisez elementele
for(i=0;i<n;i++)
 cout<<v[i]<<" ";

cout<<"\nIntroduceti valoarea cautata: ";
 cin>>val;

poz=-1;//pp ca nu exista in sir

//Parcurg secvential tot sirul si compar
for(i=0;i<n;i++)
 if(v[i]==val) poz=i;
//se retine ultima aparitie

cout<<"\nValoarea cautata se afla pe pozitia "<<poz+1;

getche();
}