Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Divide et Impera  (Citit de 3061 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
TheNechiz
De-al casei
***

Karma: 28
Deconectat Deconectat

Mesaje: 109



Vezi Profilul
« : Februarie 26, 2013, 16:31:36 »



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). Embarassed

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" ?  Huh

Dacă NU : Cum se face altfel ? Smile
« Ultima modificare: Martie 11, 2013, 16:17:57 de către Birisan Razvan » Memorat
fdproxy
Strain
*

Karma: 10
Deconectat Deconectat

Mesaje: 30



Vezi Profilul
« Răspunde #1 : 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.
« Ultima modificare: Februarie 26, 2013, 18:38:20 de către fdproxy » Memorat
TheNechiz
De-al casei
***

Karma: 28
Deconectat Deconectat

Mesaje: 109



Vezi Profilul
« Răspunde #2 : 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:

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

Î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 Smile
Memorat
fdproxy
Strain
*

Karma: 10
Deconectat Deconectat

Mesaje: 30



Vezi Profilul
« Răspunde #3 : 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.
« Ultima modificare: Februarie 27, 2013, 13:35:41 de către fdproxy » Memorat
wefgef
Echipa infoarena
Nu mai tace
*****

Karma: 1012
Deconectat Deconectat

Mesaje: 2.974


razboinicu' luminii


Vezi Profilul
« Răspunde #4 : Februarie 27, 2013, 00:29:12 »

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

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
fdproxy
Strain
*

Karma: 10
Deconectat Deconectat

Mesaje: 30



Vezi Profilul
« Răspunde #5 : 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.
Memorat
TheNechiz
De-al casei
***

Karma: 28
Deconectat Deconectat

Mesaje: 109



Vezi Profilul
« Răspunde #6 : 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 Smile ,î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
Memorat
repp4radu
Nu mai tace
*****

Karma: 118
Deconectat Deconectat

Mesaje: 204



Vezi Profilul
« Răspunde #7 : 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.
Memorat
TheNechiz
De-al casei
***

Karma: 28
Deconectat Deconectat

Mesaje: 109



Vezi Profilul
« Răspunde #8 : 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)
Memorat
TheNechiz
De-al casei
***

Karma: 28
Deconectat Deconectat

Mesaje: 109



Vezi Profilul
« Răspunde #9 : Martie 08, 2013, 16:51:53 »

Am mai lucra la Divide et Impera Smile. 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
Memorat
costi_.-.
Strain
*

Karma: 2
Deconectat Deconectat

Mesaje: 30



Vezi Profilul
« Răspunde #10 : 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);
Memorat
TheNechiz
De-al casei
***

Karma: 28
Deconectat Deconectat

Mesaje: 109



Vezi Profilul
« Răspunde #11 : 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. Think
Dar nu am înțeles cum îți dai seama ce trebuie să marchezi și ce nu trebuie să marchezi. Neutral

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. Confused Ce îți afișează pentru testul de mai sus ? Huh
Memorat
costi_.-.
Strain
*

Karma: 2
Deconectat Deconectat

Mesaje: 30



Vezi Profilul
« Răspunde #12 : Martie 12, 2013, 20:03:56 »

Ahh stai, n-am fost atent.Ma gandeam la altceva cand am scris codul  Thumb down...
In fine, dat fiind ca suprafata nu are conturul "regulat" , nu cred ca poti rezolva problema prin DivideEtImpera  Confused.
Memorat
TheNechiz
De-al casei
***

Karma: 28
Deconectat Deconectat

Mesaje: 109



Vezi Profilul
« Răspunde #13 : Martie 12, 2013, 20:16:00 »

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


Karma: 2
Deconectat Deconectat

Mesaje: 11



Vezi Profilul
« Răspunde #14 : Martie 25, 2013, 19:59:34 »

mda....oricum DEI este o metoada destul de folositoare.
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines