Notițe algoritmi de baza: (Imagini pentru explicații în curând!)

• Curs-0   Citire de nr.

  Varianta I - citire pană la 0:

  cin >> n;
  while(n){
      // prelucrare n
      // ...
      cin >> n;
  }

  Varianta II - citire a n nr:

  cin >> n;
  for(i=1;i<=n;i++){
      cin >> x;
      // prelucrare x
      // ...
  }

  Varianta III - pană la finalul fișierului (End Of File):

  // ! Nu uita sa imporți librăria !
  #include <fstream>
  ifstream f("fisier.txt");

  while(f>>n){
      // prelucrare n
  }

• Curs-1   Suma cifrelor

  s = 0;
  while(n != 0){
      s = s + n % 10;
      n = n / 10;
  }

  sau

  s = 0;
  while(n)
      s += n % 10, n /= 10;

• Curs-2   Oglinditul/Inversul/Răsturnatul.

  ogl = 0;
  while(n != 0){
      ogl = ogl * 10 + n % 10;
      n = n / 10;
  }

• Curs-3   Suma divizorilor.

  Varianta I:

  nrd = 0;
  for(d = 1; d<=n; d++)
      if(n % d == 0)
          nrd++;

  Varianta II (eficientă):

  s = 0;
  for(d = 1; d * d < n; d++)
      if(n % d == 0)
          s = s + d + n / d;
  if(d * d == n)
      s = s + d;

• Curs-4   Verificare nr. prim

  Varianta I:

  nrd = 0;
  for(d = 1; d <= n; d++)
      if(n % d == 0)
          nrd++;
  if(nrd == 2)
      // prelucrare n
      // ...

  Varianta II (eficientă):

  nrd = 0;
  for(d = 1; d * d < n; d++)
      if(n % d == 0)
          nrd = nrd + 2;
  if(d * d == n)
      nrd++;
  if(nrd == 2)
      // prelucrare n
      // ...

• Curs-5   cmmdc/cmmmc

  Varianta I - împarțiri repetate (Euclid):

  if(a * b == 0)
      cmmdc = a + b;
  else {
      D = a;
      I = b;
      R = D % I;
      while(R != 0){
          D = I;
          I = R;
          R = D % I;
      }
      cmmdc = I;
  }
  cmmmc = a * b / cmmdc;

  Varianta II - scăderi repetate:

  if(a * b == 0)
      cmmdc = a + b;
  else {
      while(a != b)
          if(a > b)
              a = a - b;
          else
              b = b - a;
      cmmdc = a;
  }
  cmmmc = ca * cb / cmmdc;

• Curs-6   Factori primi

  90=2^1*3^2*5^1

  n	d	p
  90	2	0
  45		1
  ----	---	---
  15	3	0
  5		1
  		1
  ----	---	---
  	4	0
  ----	---	---
  1	5	0
  		1

  Varianta I:

  d = 2;
  while(n != 1){
      p = 0;
      while(n % 2 == d){
          n = n/d;
          p++;
      }
      if(p != 0)
          // prelucrare p, d
          // ...
      d++;
  }

  Varianta II (eficientă):

  d = 2;
  while(d * d <= n){
      p = 0;
      while(n % d == 0){
          p++;
          n = n / d;
      }
      if(p != 0){
          // prelucrare p, d
          // ...
      }
      d++;
  }
  if(n != 1){
      // prelucrare n^1
      // ...
  }

• Curs-7   Șirul lui Fibonacci

      c  b  a
  ex: 1, 1, 2, 3, 5, 8, 13, ...
        +  =

  if(n == 1){
      // n face parte
      // ...
  } else {
      c = b = 1;
      a = 0;
      while(a < n){
          a = b + c;
          c = b;
          b = a;
      }
      if(n == a){
          // n face parte
          // ...
      }
  }

• Curs-8   Transformări

  a) din baza 10 in baza 2

  69 (baza 10) = ? (baza 2)

  int n = 69;
  
  int nrb = 0;
  int p = 1;
  while(n != 0) {
      nrb = nrb + p * (n % 2);
      n = n / 2;
      p = p * 10;
  }
  
  output=>1000101

  b) din baza 2 in baza 10

  ex: 1000101 (baza 2) = ? (baza 10)

  int n = 1000101;
  
  int nrb = 0;
  int p = 1;
  while(n != 0) {
      nrb = nrb + p * (n % 10);
      n = n / 10;
      p = p * 2;
  }
  
  output=>69

  c) din baza a in baza b

  ex: 123 (baza a) = ? (baza b)

  int n = 123; // Număr în baza a
  int a = 10; // Baza numărului
  int b = 2; // Baza dorita
  
  int nrb = 0;
  int p = 1;
  while(n != 0) {
      nrb = nrb + p * (n % b);
      n = n / b;
      p = p * a;
  }
  
  output=>1111011

• Curs-vectori-1   Introducre

  (tablouri unidimensionale)

  Declarare:

  • intregi: int v[100], n, i;
  • reali: float v[100]; int n, i;

  Citire: - tastatură

  cin >>n;
  for(i=0;i<n;i++){
      cin >> v[i];
  }

• Curs-vectori-2   Ordonare (Sortare)

  Varianta I:

  for(i=0;i<n-1;i++)
      for(j=i+1;j<n;j++)
          if(v[i]>v[j]) // <- descresc sau if(v[i]<v[j]) <- cresc
              swap(v[i],v[j]);

  Varianta II - bubble sort:

  do {
      OK=1;
      for(i=0;i<n-1;i++){
          if(v[i]>v[i+1]){
              OK=0;
              swap(v[i],v[i+1]);
          }
      }
  } while(OK==0);

• Curs-vectori-3   Eliminare / Adaugare în vector

  Eliminare:

  for(i=0;i<n;i++){
      if(v[i]%2==1){ // daca e impar
          for(j=i;j<n;j++)
              v[j]=v[j+1];
          n--;
          i--;
      }
  }

  Adaugare:

  for(i=0;i<n;i++){
      if(v[i]%2==1){ // daca e impar
          for(j=n;j>i;j--) // for(j=n;j>i+1;j--) pt adaugare dupa
              v[j]=v[j-1];
          n++;
          v[i]=2*v[i]; // pt adaugre 2*v[i]
          i++;
      }
  }

• Curs-vectori-4   Căutare binară

  (se aplică șirurior ordonate)

  OK=0;
  ls=0;
  ld=n-1;
  do {
      mij = (ls+ld) / 2;
      if(v[mij]==x){
          OK=1;
      } else {
          if(v[mij]<x)
              ls = mij + 1;
          else
              ld = mij - 1;
      }
  } while(OK=0 && ls<=ld);

• Curs-vectori-5   Interclasare

  (se aplică șirurior ordonate)

  i=0;
  j=0;
  k=0;
  while(i<n && j<m){
      if(a[i]<b[j]){
          c[k]=a[i]; // sau c[k++]=a[i++]
          k++;
          i++;
      } else {
          c[k]=b[j]; // sau c[k++]=b[j++]
          k++;
          j++;
      }
      /*
      sau in loc de else {...} pt a nu repeta nr:
      
      if(a[i]>b[i]){
          c[k++]=b[j++];
      } else {
          c[k++]=a[i++];
          j++;
      }
      */
  }
  while(i<n){c[k]=a[i];k++;i++}
  while(j<m){c[k]=b[j];k++;j++}

• Curs-matrici   În curând!