Divide et Impera

[•TheNechiz]

Am învățat recent metoda "Divide et Impera".Am înțeles-o(sau cel puțin așa cred).
Am rezolvat aplicații de genul : determinarea maximului (minimului) dintr-un vector , determinarea maximului și minimul dintr-un vector(simultan),verificarea dacă un vector este ordonat, determinarea numărului de divizori ai unui număr,suma (produsul) elementelor unui vector,factorialul unui număr ,etc.

Însă , am zăbovit destul de mult pe un enunț (simplu,ca celelalte).

Să se inverseze literele unui cuvânt dat de la tastatură.

După mai multe încercări...Am scris primul cod care a reușit să afișeze inversul cuvântului.

Cod:

# include <iostream>
# include <cstring>
using namespace std;

char cuvant[21],inv[21],n;
void invers(int i,int j)
{
    int m = (i+j)/2;
    if( i == j )
    {
        inv[n-i] = cuvant[i];
    }
    else
    {
        invers(i,m);
        invers(m+1,j);
    }
}

main()
{
    cout << "Cuvant:";
    cin.get(cuvant,21);
    n = strlen(cuvant);
    inv[n] = NULL;
    --n;
    invers(0,n);
    cout << inv;
}

Împart vectorul de caractere până ajung la subsecvențe de un sigur element.Construiesc un tablou auxiliar de caractere în care memorez pe poziția n-i ,caracterul din cuvânt de pe poziția i.

Rezolvarea mea se încadrează în "Divide et Impera" ? 

Dacă NU : Cum se face altfel ?

[•fdproxy]

Cod:

void reverse( char* s , int i, int j )
{
  if ( i < j )
  {
    std::swap( s[i], s[j] );
    reverse( s, i+1, j-1 );
  }
}

Cred ca o astfel de cerinta are doar scop educativ. In lumea reala poate ca ar arata asa:

Cod:

void reverse( char* s )
{
  if ( ! s )
    return;
  char* e = s;
  while ( *e )
    ++e;
  for ( --e; s < e; ++s, --e )
  {
    char t = *s;
    *s = *e;
    *e = t;
  }
}

Succes.

[•TheNechiz]

Cod:

void reverse( char* s , int i, int j )
{
  if ( i < j )
  {
    std::swap( s[i], s[j] );
    reverse( s, i+1, j-1 );
  }
}

Am vorbit despre această idee de rezolvare la ora de info,am convenit că nu implică "Divide et Impera".
Din câte am înțeles,algoritmul procedează astfel:

Cum o conving eu pe doamna profesoară că această rezolvare folosește metoda "Divide et Impera" ?

În clasă facem probleme cu "Divide et Impera" în scop didactic.În afară de problemele clasice,nu cred că am făcut o problemă a cărei rezolvare optimă să implice această metodă.

Mersi oricum

[•fdproxy]

Am vorbit despre această idee de rezolvare la ora de info,am convenit că nu implică "Divide et Impera".

Asa e. M-am uitat intr-o carte de algoritmi si nu este conform definitiei. Implementarea de mai jos este conform definitiei (desi absurd de costisitoare).

Cod:

#include <string>
// ...
string reverse( string s )
{
  if ( s.size() < 2 )
    return s; // am ajuns la baza
  // subproblema "stanga"
  string l = reverse( s.substr( s.size() / 2, s.size() - 1 ) );
  // subproblema "dreapta"
  string r = reverse( s.substr( 0, s.size() / 2 ) );
  // combinarea celor doua solutii
  string c = l + r;
  return c;
}

Definitia zice cam asa:
- problema trebuie rezolvata recursiv
- la fiecare nivel se parcurg urmatorii pasi:
  o "Divide" problema curenta se divide in cel putin doua subprobleme.
  o "Impera" subproblemele sunt rezolvate recursiv.
  o Rezultatele subproblemelor sunt combinate rezultand solutia problemei curente.

[•wefgef]

Cine naiba scrie manualele astea? Sunt de o absurditate strigatoare la cer.

[•fdproxy]

Cine naiba scrie manualele astea? Sunt de o absurditate strigatoare la cer.

Nu stiu... Pare a fi cea mai simpla problema ce ilustreaza algoritmul, dar cred ca nu se poate rezolva fara a sti cate ceva despre <string>. Pe de alta parte, sper ca la momentul angajarii, elevul de acum sa stie ca nu asa se inverseaza un sir; sa stie ca exista metode mult mai putin costisitoare.

[•TheNechiz]

Cine naiba scrie manualele astea? Sunt de o absurditate strigatoare la cer.

Nu stiu... Pare a fi cea mai simpla problema ce ilustreaza algoritmul, dar cred ca nu se poate rezolva fara a sti cate ceva despre <string>. Pe de alta parte, sper ca la momentul angajarii, elevul de acum sa stie ca nu asa se inverseaza un sir; sa stie ca exista metode mult mai putin costisitoare.

Cred că elevii știu asta ,însă am mulți colegi care nu înțeleg de ce trebuie să abordeze unele probleme cu "Divide et Impera".Bine, în cazul ăsta e stupid (dacă nu ți se cere în enunț ) să te apuci să rezolvi problema cu metoda asta,dar mai sunt și unele probleme care se rezolvă optim folosind DEI.

[•repp4radu]

Mie mi se pare f amuzant ca se fac toate chestiile astea ca aplicatie la Divide et impera, dar nu se preda, de exemplu, Merge Sort.

[•TheNechiz]

-Merge Sort (eu l-am învățat dintr-un manual).
-În clasă am făcut : turnurile din Hanoi și sortare rapidă. S-a vorbit puțin și despre problema tăieturilor,dar am făcut mai multe aplicații de genul celor de mai sus.(Cam astea se dau la un test din DEI)

[•TheNechiz]

Am mai lucra la Divide et Impera . Am făcut aproape toate exercițiile din culegere,însă au fost 2 pe care nu am reușit să le rezolv.

1.Se dă o matrice pătratică de dimensiuni 2^n x 2^n cu elementele 0 sau 1.Să se identifice folosind metoda "Divide et Impera" cea mai mare zonă din matrice ce conține un număr par de elemente 1.Se vor afișa coordonatele colțului stânga-jos și ale colțului dreapta-sus.

2.Se dă o matrice binară.Scrieți un program pentru umplerea unui suprafețe închise (FILL) folosind metoda "Divide et Impera".

Știu că algoritmul pentru FILL este:

Cod:

algoritm fill(X, Y)
dacă A[X][Y] = 0 atunci
A[X][Y] ← 2
fill(X, Y + 1)
fill(X + 1, Y)
fill(X, Y - 1)
fill(X - 1, Y)
sfârșit dacă
sfârșit algoritm

[•costi_.-.]

Uite o idee pentru a doua :


void FILL (int xs,ys,xj,yj)
{
   daca esti pe o singura celula:
         marcheaza celula;
  altfel
  {
     xm=(xs+xj)/2;
     ym=(ys+yj)/2;         //Imparti matricea in 4 submatrici
    
     FILL(xs,ys,xm,ym);
     FILL(xm,ym+1,xj,yj)
     //aici pui celelalte 2
   }
}

Apelezi cu coordonatele coltului din stanga sus(1,1) si dreapta jos(n,m);

[•TheNechiz]

Deci... "tai" matricea la mijloc până când ajungi la un sigur element.Asta înseamnă că matricea trebuie să aibă dimensiunea 2^n*2^n.
Dar nu am înțeles cum îți dai seama ce trebuie să marchezi și ce nu trebuie să marchezi.

Am descris algoritmul standard pentru umplerea unei suprafețe închise. (mai sus)
Dacă se dă matricea :

Cod:

0 0 0 1 1 0 0
0 0 1 0 0 1 0
0 1 0 1 0 0 1
1 0 0 0 0 1 0
1 0 0 1 1 0 0
0 1 1 0 0 0 0

și se apelează funcția fill pentru X = 4 , Y = 3, obținem:

Cod:

0 0 0 1 1 0 0
0 0 1 2 2 1 0
0 1 2 1 2 2 1
1 2 2 2 2 1 0
1 2 2 1 1 0 0
0 1 1 0 0 0 0

(am marcat cu 2 suprafața colorată)
Nu cred că am înțeles ideea ta. Ce îți afișează pentru testul de mai sus ?

[•costi_.-.]

Ahh stai, n-am fost atent.Ma gandeam la altceva cand am scris codul  ...
In fine, dat fiind ca suprafata nu are conturul "regulat" , nu cred ca poti rezolva problema prin DivideEtImpera  .

[•TheNechiz]

Sincer....asta am zis și eu.
Am primit problema asta la clasă.M-am gândit la ea ceva timp...apoi am renunțat.
Am întrebat care este rezolvarea  , nu am primit un răspuns.
Mi s-a zis că se poate face,enunțul e luat dintr-o culegere. ( ăsta e singurul argument care dovedește că problema are cel puțin o soluție )

[•cristiavra]

mda....oricum DEI este o metoada destul de folositoare.