infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: FMI Razvan Birisan din Februarie 26, 2013, 16:31:36



Titlul: Divide et Impera
Scris de: FMI Razvan Birisan din Februarie 26, 2013, 16:31:36
(http://24.media.tumblr.com/tumblr_l0t8wanlHR1qb1aw7o1_500.jpg)

Am învățat recent metoda "Divide et Impera".Am înțeles-o(sau cel puțin așa cred). :wink:
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). :oops:

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. :fool:

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 ? :)


Titlul: Răspuns: Divide et Impera
Scris de: fdproxy din Februarie 26, 2013, 18:31:00
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.


Titlul: Răspuns: Divide et Impera
Scris de: FMI Razvan Birisan din Februarie 26, 2013, 19:51:56
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:
(http://img255.imageshack.us/img255/3822/sirz.png)
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 :)


Titlul: Răspuns: Divide et Impera
Scris de: fdproxy din Februarie 26, 2013, 22:21:20
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.


Titlul: Răspuns: Divide et Impera
Scris de: Andrei Grigorean din Februarie 27, 2013, 00:29:12
Cine naiba scrie manualele astea? Sunt de o absurditate strigatoare la cer.


Titlul: Răspuns: Divide et Impera
Scris de: fdproxy din Februarie 27, 2013, 13:33:26
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.


Titlul: Răspuns: Divide et Impera
Scris de: FMI Razvan Birisan din Februarie 27, 2013, 16:35:31
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. :peacefingers:


Titlul: Răspuns: Divide et Impera
Scris de: Radu-Andrei Szasz din Februarie 28, 2013, 16:50:56
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.


Titlul: Răspuns: Divide et Impera
Scris de: FMI Razvan Birisan din Februarie 28, 2013, 17:06:49
-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)


Titlul: Răspuns: Divide et Impera
Scris de: FMI Razvan Birisan din Martie 08, 2013, 16:51:53
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


Titlul: Răspuns: Divide et Impera
Scris de: Costinnel din Martie 11, 2013, 15:24:34
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);


Titlul: Răspuns: Divide et Impera
Scris de: FMI Razvan Birisan din Martie 11, 2013, 16:16:14
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. :-k
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 ? ???


Titlul: Răspuns: Divide et Impera
Scris de: Costinnel din Martie 12, 2013, 20:03:56
Ahh stai, n-am fost atent.Ma gandeam la altceva cand am scris codul  :thumbdown:...
In fine, dat fiind ca suprafata nu are conturul "regulat" , nu cred ca poti rezolva problema prin DivideEtImpera  :?.


Titlul: Răspuns: Divide et Impera
Scris de: FMI Razvan Birisan din Martie 12, 2013, 20:16:00
Sincer....asta am zis și eu. :thumbup:
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 )


Titlul: Răspuns: Divide et Impera
Scris de: Avramescu Cristia din Martie 25, 2013, 19:59:34
mda....oricum DEI este o metoada destul de folositoare.