PUC-Rio Departamento de Informática
Prof. Marcus Vinicius S. Poggi de Aragão
Período: 2001.2
22 de outubro de 2001
Horário: 2a.-feira 18-20
ESTRUTURAS DISCRETAS (INF 1308)

1o Trabalho

Uma celebridade em um grupo é uma pessoa que todos conhecem e que não conhece ninguém. Assuma que todas as possíveis perguntas ``i conhece j ?'' são feitas e que as respostas estejam disponíveis em uma matriz onde seus elementos, conhece[i,j], assumem o valor 1, se i conhece j, e 0, caso contrário (a diagonal não é usada). Deseja-se determinar se em um dado grupo de pessoas existe ou não uma celebridade e, em caso afirmativo, determinar quem é a celebridade.
  1. Enuncie o teorema que atesta que sabe-se resolver este problema.
  2. Prove este teorema por indução (simples).
  3. Escreva o algoritmo correspondente à sua prova para o teorema.
  4. Implemente o algoritmo do item 3. Utilize como chamada do seu algoritmo em "C" ou equivalente: "int celebridade(int n, int conhece[ ][ ])"

    celebridade retorna 0 caso não haja celebridade ou o índice da celebridade no grupo caso exista. n é o número de pessoas no grupo, o valor n indica que foram consideradas as pessoas 1, 2, ..., n. Finalmente, "conhece" é a matriz que caracteriza o grupo. Esta matriz é sempre passada com todos os elementos do problema. Implemente o seu algoritmo recursivamente.
This document was translated from LATEX by HEVEA.