Metoda Divide et Impera – Problema cautarii binare

Prezentare generala:
Divide et Impera se bazează pe principiul descompunerii problemei în două sau mai multe subprobleme (mai ușoare), care se rezolvă, iar soluția pentru problema inițială se obține combinând soluțiile subproblemelor. De multe ori, subproblemele sunt de același tip și pentru fiecare din ele se poate aplica aceeași tactică a descompunerii în (alte) subprobleme, până când (în urma descompunerilor repetate) se ajunge la probleme care admit rezolvare imediată.

Nu toate problemele pot fi rezolvate prin utilizarea acestei tehnici. Se poate afirma că numărul celor rezolvabile prin “divide et impera” este relativ mic, tocmai datorită cerinței ca problema să admită o descompunere repetată.

Divide et impera este o tehnică ce admite o implementare recursivă. Principiul general prin care se elaborează algoritmi recursivi este: “ce se întâmplă la un nivel, se întâmplă la orice nivel” (având grijă să asigurăm condițiile de terminare). Așadar, un algoritm prin divide et impera se elaborează astfel: la un anumit nivel avem două posibilități:

1. s-a ajuns la o problemă care admite o rezolvare imediată (condiția de terminare), caz în care se rezolvă și se revine din apel;
2. nu s-a ajuns în situația de la punctul 1, caz în care problema curentă este descompusă în (două sau mai multe) subprobleme, pentru fiecare din ele urmează un apel recursiv al funcției, după care combinarea rezultatelor are loc fie pentru fiecare subproblemă, fie la final, înaintea revenirii din apel.

Se citeşte un şir de n elemente numere întregi ordonate crescător şi o valoare întreagă key. Să se decidă dacă valoarea key se găseşte printre valorile şirului de elemente şi în caz afirmativ să se tipărească indicele componentei care conţine acea valoare.


#include "stdio.h"
int a[10],n,key;

void caut(int i, int j)
{
  if(key == a[(i+j)/2])
    printf("Valoarea a fost gasita la indicele %d\n",(i+j)/2);
  else
    if(i < j)       if(nr < a[(i+j)/2])         caut(i, (i+j)/2-1);       else         caut((i+h)/2+1,j); } Continue reading

Metoda Divide et Impera – Elementul maxim intr-un sir

Prezentare generala:
Divide et Impera se bazează pe principiul descompunerii problemei în două sau mai multe subprobleme (mai ușoare), care se rezolvă, iar soluția pentru problema inițială se obține combinând soluțiile subproblemelor. De multe ori, subproblemele sunt de același tip și pentru fiecare din ele se poate aplica aceeași tactică a descompunerii în (alte) subprobleme, până când (în urma descompunerilor repetate) se ajunge la probleme care admit rezolvare imediată.

Nu toate problemele pot fi rezolvate prin utilizarea acestei tehnici. Se poate afirma că numărul celor rezolvabile prin “divide et impera” este relativ mic, tocmai datorită cerinței ca problema să admită o descompunere repetată.

Divide et impera este o tehnică ce admite o implementare recursivă. Principiul general prin care se elaborează algoritmi recursivi este: “ce se întâmplă la un nivel, se întâmplă la orice nivel” (având grijă să asigurăm condițiile de terminare). Așadar, un algoritm prin divide et impera se elaborează astfel: la un anumit nivel avem două posibilități:

1. s-a ajuns la o problemă care admite o rezolvare imediată (condiția de terminare), caz în care se rezolvă și se revine din apel;
2. nu s-a ajuns în situația de la punctul 1, caz în care problema curentă este descompusă în (două sau mai multe) subprobleme, pentru fiecare din ele urmează un apel recursiv al funcției, după care combinarea rezultatelor are loc fie pentru fiecare subproblemă, fie la final, înaintea revenirii din apel.

Se citeşte un şir de n elemente numere întregi. Să se găsească maximul elementelor acestui şir utilizând metoda divide et impera.

#include "stdio.h"
int a[10],n;
int max(int i, int j)
{
  int a,b;
  if(i == j)
    return a[i];
  else
  {
    a=max(i,(i+j)/2);
    b=max((i+j)/2+1,j);
    if(a > b)
      return (a);
    else
      return (b);
  }
}
Continue reading

Metoda Divide et Impera – Problema Turnurilor din Hanoi

Prezentare generala:
Divide et Impera se bazează pe principiul descompunerii problemei în două sau mai multe subprobleme (mai ușoare), care se rezolvă, iar soluția pentru problema inițială se obține combinând soluțiile subproblemelor. De multe ori, subproblemele sunt de același tip și pentru fiecare din ele se poate aplica aceeași tactică a descompunerii în (alte) subprobleme, până când (în urma descompunerilor repetate) se ajunge la probleme care admit rezolvare imediată.

Nu toate problemele pot fi rezolvate prin utilizarea acestei tehnici. Se poate afirma că numărul celor rezolvabile prin “divide et impera” este relativ mic, tocmai datorită cerinței ca problema să admită o descompunere repetată.

Divide et impera este o tehnică ce admite o implementare recursivă. Principiul general prin care se elaborează algoritmi recursivi este: “ce se întâmplă la un nivel, se întâmplă la orice nivel” (având grijă să asigurăm condițiile de terminare). Așadar, un algoritm prin divide et impera se elaborează astfel: la un anumit nivel avem două posibilități:

1. s-a ajuns la o problemă care admite o rezolvare imediată (condiția de terminare), caz în care se rezolvă și se revine din apel;
2. nu s-a ajuns în situația de la punctul 1, caz în care problema curentă este descompusă în (două sau mai multe) subprobleme, pentru fiecare din ele urmează un apel recursiv al funcției, după care combinarea rezultatelor are loc fie pentru fiecare subproblemă, fie la final, înaintea revenirii din apel.

Legenda acestei probleme spune că Brahma a fixat pe Pământ trei tije de diamante şi pe una din ele a pus în ordine crescătoare 64 de discuri de aur de dimensiuni diferite, cu discul cel mai mare jos. Singura operaţiune permisă călugărilor era mutarea a câte unui singur disc de pe o tijă pe alta, astfel încât niciodată să nu se pună un disc mai mare peste unul mai mic. Legenda spune că atunci când călugării vor muta toate cele 64 de discuri respectând regulile de maa sus, atunci va veni sfârşitul lumii. Presupunând că în fiecare secundă se mută un disc, lucrând fără întrerupere, cele 64 de discuri nu pot fi mutate nici în 500 de miliarde de ani de la începutul acţiunii!

Vom considera trei tije verticale notate Stânga, Mijloc, Dreapta. Pe tija Stânga se găsesc aşezate n discuri de diametre diferite, în ordinea descrescătoare a diametrelor, privind de jos în sus. Iniţial, tijele Mijloc şi Dreapta sunt goale. Să se afişeze toate mutările prin care discurile de pe tija Stânga se mută pe tija Mijloc, în aceeaşi ordine, respectând următoarele reguli:
• la fiecare mişcare se mută un singur disc
• un disc mai mare nu poate fi plasat peste un disc cu diametrul mai mic
• un disc mai mare nu poate fi plasat peste un disc cu diametrul mai mic
Continue reading

Metoda Divide et Impera – Suma elementelor unui sir

Prezentare generala:
Divide et Impera se bazează pe principiul descompunerii problemei în două sau mai multe subprobleme (mai ușoare), care se rezolvă, iar soluția pentru problema inițială se obține combinând soluțiile subproblemelor. De multe ori, subproblemele sunt de același tip și pentru fiecare din ele se poate aplica aceeași tactică a descompunerii în (alte) subprobleme, până când (în urma descompunerilor repetate) se ajunge la probleme care admit rezolvare imediată.

Nu toate problemele pot fi rezolvate prin utilizarea acestei tehnici. Se poate afirma că numărul celor rezolvabile prin “divide et impera” este relativ mic, tocmai datorită cerinței ca problema să admită o descompunere repetată.

Divide et impera este o tehnică ce admite o implementare recursivă. Principiul general prin care se elaborează algoritmi recursivi este: “ce se întâmplă la un nivel, se întâmplă la orice nivel” (având grijă să asigurăm condițiile de terminare). Așadar, un algoritm prin divide et impera se elaborează astfel: la un anumit nivel avem două posibilități:

1. s-a ajuns la o problemă care admite o rezolvare imediată (condiția de terminare), caz în care se rezolvă și se revine din apel;
2. nu s-a ajuns în situația de la punctul 1, caz în care problema curentă este descompusă în (două sau mai multe) subprobleme, pentru fiecare din ele urmează un apel recursiv al funcției, după care combinarea rezultatelor are loc fie pentru fiecare subproblemă, fie la final, înaintea revenirii din apel.


#include "stdio.h"
#incude "conio.h"
int a[20];
int divide(int ls, int ld)
{
  int mijloc,d1,d2;
  if(ls != ld)
  {
    mijloc=(ls+ld)/2;
    d1=divide(ls, mijloc);
    d2=divide(mijloc+1,ld);
    return(d1+d2);
  }
  else
    return(a[ls]);
}
Continue reading

Backtracking – problema mingii

Se dă un teren parcelat cu porţiuni de teren pătrate, fiecare având o anumită cotă. Cotele se citesc de la tastatură şi se reţin într-o matrice de m/n poziţii. O bilă se găseşte într-o poziţie iniţială, având nişte coordonate iniţiale ce se citesc de la tastatură. Se ştie că bila poate sări de la o cotă mai mare spre o cotă mai mică, pe orizontală, verticală şi pe diagonale, rostogolindu-se astfel către marginea terenului. Se cere să se afişeze toate variantele de deplasare a mingii până la atingerea unei margini.


#include "stdio.h"
#include "conio.h"
int a[8]={1,1,0,-1,-1,-1,0,1}, b[8]={0,1,1,1,0,-1,-1,-1};
//tablou va păstra cotele iar drum drumul
//parcurs de minge (folosind valori 0 şi 1)
int tablou[10][10],drum[10][10],m,n;
//funcţia de afişare a soluţiei void afiseaza(void)
{
  int p,r;
  for(p=0;p < m;p++)   {   for(r=0;r < n;r++)     printf("%d",drum[p][r]);   putchar("\n");   }   putchar("\n");   getch(); } Continue reading

Backtracking – problema calului

Se consideră o tablă de şah având m/n câmpuri. Se plasează un cal în colţul din stânga sus. Calul se mişcă conform regulilor din şah. Se cere să se găsească toate variantele (dacă există) de a acoperi întreaga tablă, adică să se determine un număr de m*n-i mutări astfel încât fiecare câmp să fie vizitat o singură dată.


#include "stdio.h"
#include "conio.h"
//şirurile pentru cele 8 salturi
int a[8]={2,1,-1,-2,-2,-1,1,2}, b[8]={1,2,2,i,-1,-2,-2,-1};
//matricea t va conţine drumul
int t[10][10],m,n;
//funcţia de afişare a soluţiei
void afiseaza(void)
{
  int p,r;
  for(p=0;p < m;p++)   {     for(r=0;r < n;r++)     printf("%d",t[p][r]);   putchar("\n");   }   getch(); } Continue reading

Backtracking – problema labirintului

Se dă un labirint reprezentat sub forma unei matrici cu n linii şi m coloane, conţinând doar valori 0 şi 1. O succesiune de 1 reprezintă un drum iar o reprezintă zid. Dintr-un punct iniţial, a cărui coordonate se citesc, porneşte o persoană. Să se afişeze toate posibilităţile ca acea persoană să iasă din labirint (să atingă una din marginile matricei), ştiind că deplasarea se poate face doar prin valori 1 ale matricei, iar salturile se pot face în stânga, dreapta, jos şi sus.


#include "stdio.h"
#include "conio.h"
//matricea a conţine valorile labirintului iar în matricea rez vom păstra drumul
//parcurs în cadrul unei posibile soluţii
int a[10][10],rez[10][10],n;
void scrie(void)
{
  int i,j;
  for(i=0;i < n;i++)   {     //afişăm matricea drumului de ieşire; succesiunea de 1 reprezintă drumul     for(j=0;j < n;j++)     printf("%d",rez[i][j]);     putchar("\n");   }   putchar("\n");   //după fiecare soluţie se aşteaptă apăsarea unei taste   getch(); } Continue reading

Backtracking – problema reginelor

Fiind dată o tablă de şah, de dimensiune n/n, se cer toate soluţiile de aranjare a n dame, astfel încât să nu se afle două dame pe aceeaşi linie, coloană sau diagonală (damele să nu se atace reciproc).


#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
int a[10],nr=0,n;
//funcţia de afişare a soluţiei
void scrie(void)
{
  int i;
  printf("Solutia numărul: %d\n",nr++);
  for(i=0;i < n;i++)   printf("Regina de pe linia %d pe coloana %d\n",(i+1),a[i]+1);   putchar("\n"); } Continue reading

Backtracking – combinari

Se citesc 2 numere naturale nenule k,n unde k < n. Să se afişeze toate combinările a k numere din mulţimea (1,2,. ..n}.
#include “stdio.h”
#include “conio.h”
int m,n,a[20];
//funcţia de afişare a soluţiei
void scrie(void)
{
  int i;
  for(i=0;i < n;i++)   printf("%d ",a[i]+1);   //deoarece lucrăm cu indici de la 0, vom adăuga 1 la valorile rezultate   putchar("\n"); } //funcţia recursivă de generare a combinărilor void comb(int k) {   int i;   //vom încerca să aşezăm pe poziţia curentă, pe rând, toate valorile de la 0 la m-1   for(i=0;i < m;i++)   //încercăm pe poziţia curentă valoarea i   {     a[k]=i;     //dacă este prima valoare aşezată sau dacă ea este mai mare decât     //precedenta putem continua; în caz contrar vom încerca o altă valoare     //a lui i pe poziţia curentă     if((k == 0)||(a[k] > a[k-1]))
      if(k == n-1)
      //dacă am aşezat n valori (de la 0 la n-1) am ajuns la soluţie
      scrie();
    else
      //dacă nu, apelăm funcţia de aşezare a următoarei poziţii
      comb(k+1);
  }
}

void main(void)
{
  printf(“Introdu pe m:”);
  scanf(“%d”,&m);
  printf(“Introdu pe n:”);
  scanf(“%d”,&n);
  //apelăm funcţia recursivă comb încercând să aşezăm primul element
  comb(0);
  getch();
}

Backtracking – aranjamente

Să se genereze toate aranjamentele de n numere luate câte p. Se consideră mulţimea A={1,2,…n} şi un număr natural k, k < n. Se vor genera toate submulţimile mulţimii A care au k elemente, considerând submulţimi distincte cazurile având aceleaşi elemente dar poziţii diferite. Practic este necesară obţinerea tuturor combinărilor de k elemente din mulţimea A, iar pentru fiecare mulţime astfel obţinută se vor genera toate permutările ei.
#include “stdio.h”
int n,st[100],p,i;
//functia care ne va afisa intr-un final sirul
void afiseaza()
{
for(i=0;i < p;i++)   printf("%d", st[i]); } //functia care verifica daca elementele sunt diferite int valid() { for(i=1;i < k;i++)   if(st[i] == st[k])     return 0;   return 1; } void backtracking(int k) {   if(k > p)
    afiseaza();
  else
    for(i=0;i < n;i++)       {       st[k]=i;       if(valid(k))         backtracking(k+1);       } } int main() { printf("Numarul de elemente: "); scanf("%d", n); prinf("Numarul de moduri"); scanf("%d", p); backtracking(1); getch(); }