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> Î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 ) Cred ca o astfel de cerinta are doar scop educativ. In lumea reala poate ca ar arata asa: Cod: void reverse( char* s ) 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 ) 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> 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) 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 Cod: 0 0 0 1 1 0 0 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.
|