SHARE
TWEET

DICTOMICA

a guest Nov 22nd, 2019 97 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. 2. Cerca dicotòmica
  2. Enunciat: Feu una funció
  3. int posicio(double x, const vector<double>& v, int esq, int dre);
  4. que retorni la posició on es troba x dins del subvector v[esq..dre] . Si x no apareix a v[esq..dre] o
  5. esq > dre , cal retornar -1 .
  6. Podem suposar que
  7. • El vector v està ordenat creixentment.
  8. • Inicialment (0 <= esq) and (dre < v.size()) .
  9. Nota: En canvi, esq <= dre pot no ser cert ni al principi: Penseu quina crida faríeu per ordenar una taula
  10. de mida 0.
  11.  
  12.  
  13. Solució recursiva:
  14. // Pre: (0 <= esq) and (dre < v.size()) and (v esta ordenat creixentment)
  15. // Post: retorna i tal que, o be esq<=i<=dre i v[i]==x, o be i==-1 i x no es a v[esq..dre]
  16. int posicio(double x, const vector<double>& v, int esq, int dre) {
  17. if (esq > dre) return -1;
  18. int pos = (esq + dre)/2;
  19. // posicio central de v[esq..dre]
  20. if (x < v[pos]) return posicio(x, v, esq, pos - 1);
  21. if (x > v[pos]) return posicio(x, v, pos + 1, dre);
  22. return pos;
  23. }
  24.  
  25.  
  26. Solució iterativa:
  27. // Pre: (0 <= esq) and (dre < v.size()) and (v esta ordenat creixentment)
  28. // Post: retorna i tal que, o be esq<=i<=dre i v[i]==x, o be i==-1 i x no es a v[esq..dre]
  29. int posicio(double x, const vector<double>& v, int esq, int dre) {
  30. int pos;
  31. bool trobat = false;
  32. // Inv: (0 <= esq), (dre < v.size()),
  33. // si x es a v[E..D], llavors es a v[esq..dre]
  34. // on E i D son els valors inicials d'esq i dre,
  35. // i a mes trobat indica que hem trobat x a pos
  36. while (not trobat and esq <= dre) {
  37. pos = (esq + dre)/2;
  38. // posicio central de v[esq..dre]
  39. if (x < v[pos]) dre = pos - 1;
  40. else if (x > v[pos]) esq = pos + 1;
  41. else trobat = true;
  42. }
  43. if (trobat) return pos;
  44. else return -1;
  45. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top