Padrões de algoritmos
Os exemplos a seguir seguem um mesmo padrão abstrato de solução que, sujeito a particularidades de cada caso, pode ser descrito assim:
É dado um conjunto de objetos. Examine cada elemento do conjunto e para cada um deles efetue um mesmo procedimento. Mostre o resultado correspondente.
Este padrão simples, vamos chamá-lo de método iterativo, cobre a maior parte de procedimentos que você vai encontrar em seu dia a dia. Mas existem situações em que é preciso seguir outros padrões de procedimentos, como veremos mais tarde.
Vejamos alguns exemplos para ilustrar este padrão abstrato.
É dado um diretório D contendo arquivos tipo texto (.txt). Deseja-se saber quantas palavras são contidas nestes arquivos.
Neste problema iremos seguir o padrão duas vêzes, uma primeira onde o conjunto de objetos são os arquivos texto em D, e uma segunda onde o conjunto de objetos são os caracteres que compõem um arquivo texto.
Temos portanto um problema principal e um problema secundário ocorrendo dentro do problema principal.
Num nível "externo" temos um diretório contendo arquivos. Para cada arquivo conte seu número de palavras e retorne o total de todos arquivos.
Num nível "interno", formando um sub problema, temos um arquivo texto cheio de caracteres e queremos processar cada caractere formando "palavras", retornando a contagem destas palavras.
Em ambos níveis vemos que o padrão iterativo de procedimento se aplica feito luva.
Para implementar a solução em pseudo código vamos assumir que o sub problema já foi resolvido e programado em uma função que recebe um nome de arquivo texto e devolve seu número de palavras:
num = numero_palavras(nome_arquivo)
Com isto a solução do problema no nivel externo ficaria assim:
numero = 0
para cada arquivo A no diretorio D:
numero = numero + numero_palavras(A)
imprime(numero)
Agora falta só programar a solução do sub problema interno. Precisamos definir o que é uma "palavra".
Para este exemplo vamos assumir que uma palavra é qualquer sequencia de caracteres alfanuméricos precedida e seguida por caracteres separadores ou "whitespace". Estes separadores são essencialmente espaço, tabulação, certos caracteres de contrôle, etc. Vamos assumir que existe uma função separador(L) que retorna "verdadeiro" ou "falso" conforma L seja um caracter separador ou não.
Com esta função o procedimento básico consiste em percorrer todos caracteres do texto verificando se o caracter é separador ou letra. Repare que a cada caracter lido podemos estar em um de dois possíveis estados: dentro de uma palavra ou entre palavras.
Então, dado um caracter C que é uma letra verificamos se estamos dentro ou "fora" de uma palavra neste ponto. Se já estamos dentro de uma palavra nada será feito, passe para o caracter seguinte.
Se estamos fora de uma palavra (e C é uma letra) então acabamos de encontrar um início de nova palavra. Anotamos que uma palavra foi iniciada e incrementamos a contagem de palavras.
Se o caracter C for um separador novamente temos dois casos, dependendo se estamos dentro ou "fora" de uma palavra neste ponto. Se estamos fora de uma palavra nada será feito, passe para o caracter seguinte.
Se porem estamos dentro de uma palavra (e C é um separador) então acabamos de encontrar o final da palavra. Anotamos que nenhuma palavra está iniciada.
Repita o procedimento até terminar de percorrer todos os caracteres do texto.
Vejamos o pseudo código:
palavras = 0 # o numero de palavras encontrado
em_palavra = falso # indica que estamos numa palavra ou não
para cada caracter C no texto:
se separador(C) for falso: # C é uma letra
se em_palavra for falso: # estamos fora de palavra
palavras = palavras + 1 # comecou uma nova palavra
em_palavra = verdadeiro
se separador(C) for verdadeiro: # C é um separador
se em_palavra for verdadeiro: # estamos numa palavra
em_palavra = falso # terminou uma palavra
imprima( palavras)
Para completar o nossa solução do problema basta colocar este procedimento como uma função, seguindo nossa convenção para pseudo código:
define numero_palavras(A):
texto = leia_arquivo(A)
palavras = 0
em_palavras = falso
para cada caracter C em texto:
se separador(C):
se em_palavra == falso:
palavras = palavras + 1
em_palavra = verdadeiro
senão:
se em_palavra == verdadeiro:
em_palavra = falso
retorna(palavras)
E este algoritmo iterativo resolve o problema.
No comments:
Post a Comment