Aula 12

Aula 12

                 ------------------------------------
                 Pesquisa sequêncial e sua eficiência
                  Pesquisa binária e sua eficiência
                 ------------------------------------

Nota. Ver mais informação sobre ordenação nos "slides" das aulas teóricas.


Eficiência <--> tempo de execução

Medindo a eficiência da procura de x em v[] (n elementos):

   c(n): Número de comparações entre x e v[].

Pesquisa sequêncial:
   Quando v não pertence a v[0..n-1]:
      Pior caso:  c(n) =
      Caso médio: c(n) = 
   Quando v pertence a v[0..n-1]:
      Pior caso:  c(n) =
      Caso médio: c(n) = 


Pesquisa binária: Em cada passo (comparação) o intervalo de pesquisa é
  aproximadamente dividido a meio

          31 -> 15 -> 7 -> 3 -> 1 -> 0

  c(n) = ... (aproximadamente)


Programa da pesquisa binária
----------------------------
  => Hipótese: v[] ordenado por ordem crescente (ou não decrescente)

  Proposição: 

           ** se x está em v[0..n-1] está em v[a..b] **


  Para ser verdadeira:
    - inicialmente:  a=0, b=n-1

    - em cada passo: m=(a+b)/2
            comparamos x com v[m]
      i     a  a+1  a+2      m      b
            ----------------------------
     v[i]      <           v[m]   >
            ----------------------------

    ...

Programa:

Exercícios
----------
(um caso típico em que o máximo cuidado na programação não é de mais!) 


 1)  Escreva uma versão iterativa da pesquisa binária
        b-a+1 vai diminuindo num ciclo... até


 2)  Escreva uma versão recursiva da pesquisa binária

==================================================================


Exercício
---------
Escreva um programa que leia os caracteres de um ficheiro com a
instrução getchar() (redireccionando a entrada padrão) e escreva o
número de ocorrências de cada letra (minúscula ou maiúscula)
por ordem de número de ocorrências, por exemplo:

     letra e:  310 ocorrência(s)
     letra s:  300 ocorrência(s)
     letra a:  185 ocorrência(s)
     ....
     letra w:    1 ocorrência(s)

Método
------

     1) contar em cont[i] o número de ocorrências de cada letra
     2) formar o vector carac[0]='a', carac[1]='b', ...
   * 3) ordenar por ordem decrescente cont[], ordenando
        simultaneamente o correspondente carac[]
     4) Imprimir os resultados

Funções: 
     - int minusc(int cc): letra c convertida para minúscula,
                           0 se c não é letra
     - void conta(int cont[]), cada vector com 26 elementos...
     * void ordena(int cont[],int carac[]), 
       cada vector com 26 elementos...
     - void imprime(cont[],carac[])

------------------------------------------
ESCREVA AS FUNÇÔES!

main(){
  int cont[NLETRAS]={0},carac[NLETRAS],i;

  for(i=0;i<NLETRAS;i++) carac[i]='a'+i;

  conta(cont);
  ordena(cont,carac);
  imprime(cont,carac);
}
------------------------------------------


bom... ainda não sabemos ordenar... para já sem ordenação...


Nota. Use #define NLETRAS 26


==========================================================

Como ordenar vectores?
----------------------

Aula 12