celebridade

Prévia do material em texto

Caso Base: 
Se uma festa tem 1 pessoa então essa pessoa é a celebridade. 
Assim, uma festa com 1 pessoa é necessário 0 perguntas para descobrir quem é 
a celebridade. 
Logo, a fórmula é válida n=1, ou seja, 3*0 = 0 perguntas para encontrar a 
celebridade, se houver uma, com 
3(n-1) perguntas. 
Hipótese de Indução: 
Uma festa com n-1 pessoas são necessários  para encontrar a celebridade, se 
houver uma,3(n-1-1) perguntas, ou seja, 3(n-2). 
Passo de indução: 
Suponha uma festa com n pessoas, temos que mostrar que podemos encontrar a 
celebridade, se houver uma, 
com 3(n-1) perguntas. 
Seja S o conjunto de todas as pessoas. 
Escolha duas pessoas x e y do conjunto S  de pessoas. 
Se x conhece y então 
    Logo, x não é uma celebridade 
    Faça S' = S - {x}. Dessa maneira, S' tem n-1 pessoas 
    Por hipótese de indução, podemos encontrar a celebridade z, se houver, 
com 3(n-2) perguntas. 
    Se não houver uma celebridade em S' então S não tem celebridade 
    Senão Para z ser uma celebridade de toda a festa, ela não pode conhecer 
x e x conhece z. 
    O total de perguntas foram 1+ 3(n-2) + 2 = 1 + 3n -6 +2 = 3n -3 = 3(n-1) 
Senão 
    Logo, y não é uma celebridade. 
    Faça S' = S - {y}. Dessa maneira S' tem n-1 pessoas. 
     Por hipótese de indução, podemos encontrar a celebridade z, se houver, 
com 3(n-2) perguntas. 
    Se não houver uma celebridade em S' então S não tem celebridade 
    senão para z ser uma celebridade de toda a festa, ela não pode conhecer 
y e y conhece z. 
    O total de perguntas foram 1+ 3(n-2) + 2 = 1 + 3n -6 +2 = 3n -3 = 3(n-1) 
int celebridade(S) 
Seja S um conjunto de pessoas. 
se length(S) == 1 então 
   return z que está em  S 
senão 
   x,y <- escolha duas pessoas da lista 
   se x conhece y então 
      S' = S - {x} 
      z = celebridade(S') 
      if( !pergunta(z,x) && pergunta(x,z)) return z; 
      else return -1; 
   senao 
      S' = S - {y} 
      z = celebridade(S') 
      if( !pergunta(z,y) && pergunta(y,z)) return z; 
      else return -1; 
Wladimir Araujo Tavares 
*Federal University of Ceará <http://lia.ufc.br/%7Ewladimir/> 
Homepage <http://lia.ufc.br/%7Ewladimir/> | 
Maratona<https://sites.google.com/site/quixadamaratona/>| 
* 
    Reply     Reply to author      Forward        
Report spam
	
	
	
	
		
	
	
	
	Wladimir Tavares  
		View profile   Translate to English
	 More options Sep 19, 5:33 pm
	
	
Caros alunos, 
Faltou um teste!! 
int celebridade(S) 
   //Seja S um conjunto de pessoas. 
   se length(S) == 1 então 
   return z que está em  S 
senão 
   x,y <- escolha duas pessoas da lista 
   se x conhece y então 
      S' = S - {x} 
      z = celebridade(S') 
      *if(z==-1) return -1;* 
      else if( !pergunta(z,x) && pergunta(x,z)) return z; 
      else return -1; 
   senao 
      S' = S - {y} 
      z = celebridade(S') 
     * if(z==-1) return -1;* 
      else if( !pergunta(z,y) && pergunta(y,z)) return z; 
      else return -1;