[Exercici] Unimodal
Inaguram amb aquesta entrada un nou apartat del blog, els exercicis de programació. Estau convidats a resoldre el problema (emprant pseudocodi o el vostre llenguatge preferit) i a compartir la vostra solució als comentaris.
Dificultat: Fàcil (1/5)
Enunciat: Es diu que una seqüència A = (a1,..., an) de longitud n >= 3 és unimodal si existeix un índex p, 1 <= p <=n, tal que a1 < a2 < ··· < ap i ap > ap+1 > ··· > an. A l'element ap se l'anomena pic. Escriu un algorisme de dividir i vèncer que donat un vector que conté una seqüència unimodal trobi el pic de la seqüència, amb cost O(log n).
Extret de: Col·lecció de problemes de Anàlisi i Disseny d'Algorismes
3 comentaris:
Pista? Fa dies que li dóno voltes i no se m'ocor. I no puc fer búsquedes a Google perque potser me surt la solució completa! >_<
Molt be, m'encanta que algú s'animi! :D
La solució és molt semblant a la cerca binària. En el cas de que el valor intermig (a_{m}) sigui menor que el següent(a_{m+1}, el pic ha de ser necessàriament al vector (a_{m+1},a{max}).
Pensa en adaptar la típica cerca binària recursiva per la seqüència unimodal, queda un codi molt curtet i mono!
Ànims, i a veure si t'animes a proposar qualque exercici al teu antic blog!
Però si els costos han de ser lg(n) no vol dir que per un vector de vuit elements sols puc fer tres consultes? No veig com puc determinar-ho sempre amb aquest cost.
Publica un comentari