Problema 4.15

Estes problemas sobre árvores genealógicas baseiam-se numa organização simples em dicionário: a chave é um nome, o valor a lista dos descendentes. Neste problema, o nosso objectivo é determinar de duas pessoas são irmãs. Por definição, sê-lo-ão se tiverem o mesmo progenitor. Com a organização definida, encontrar o progenitor de uma pessoa corresponde a encontrar a chave associada a um elemento da lista correspondente ao valor. Não é o modo natural de procurar num dicionário e, por isso, é preciso alguma ginástica.

view sourceprint?

1.def progenitor(dic, nome):

2.  """ Devolve o progenitor do nome."""

3.  for chave, valor in dic.items():

4.      if nome in valor:

5.          return chave

6.  return None

A solução encontrada mostra como percorremos os itens do dicionário na procura da chave. Como necessitamos das duas componentes do par, a procura faz-se recorrendo a dic.items(). Obtemos assim um par (chave, valor). É por este último facto que podemos colocar dois nomes entre o for e o in! Deste modo, se em cada etapa do ciclo se aceder a um par, por exemplo, ('jorge', ['luis','ana','vasco']), chave fica associada ao primeiro elemento, neste exemplo a 'jorge', e o valor ao segundo, neste caso ['luis','ana','vasco']. Depois é só fazer o teste (linha 4) e devolver o resultado mal este seja encontrado (linha 5). Relembro que mal é encontrada uma instrução de return o programa termina devolvendo o valor associado.

Com este programa auxiliar, é agora trivial resolver a nossa questão inicial.

view sourceprint?

1.def irmaos(dic,nome1,nome2):

2.  """ Têm o mesmo progenitor?"""

3.  prog1 = progenitor(dic, nome1)

4.  prog2 = progenitor (dic,nome2)

5.  return prog1 == prog2

Este exemplo simples serve para ilustrar um princípio básico da programação: a abstracção. Posso começar pela definição e construir a minha solução abstracta que pressupõe, neste caso, que tenho o comando progenitor. Implemento depois o comando, caso ele não exista. Esta forma de programar, do topo para a base, por recurso a camadas de abstracção, recebeu o nome de Programação Descendente.