[Prévia] [Próxima] [Prévia por assunto] [Próxima por assunto]
[Índice cronológico]
[Índice de assunto]
Solucao do Desafio de Josephus com arvores binarias balanceadas
- Subject: Solucao do Desafio de Josephus com arvores binarias balanceadas
- From: Lennon de Almeida Machado <lennonx@hotmail.com>
- Date: Fri, 26 Mar 1999 08:45:38 -0300
Prof Yoshi e colegas,
Segue aqui uma implementacao do desafio de Josephus baseada na "PEQUENA"
dica dada na aula de 15/3/99. Agora entendo o sentido de N log N, pois o
primeiro algoritmo com listas eliminava n pessoas dando passos de m em
m,
assim tinhamos um tempo proporcional a n*m, com minha tentativa houve
uma
reducao de passos a serem realizados, mas estes ainda dependiam de m (so
nao sei exatamente com qual funcao); agora com a arvore binaria temos
que
eliminar n pessoas, porem como a arvore e cria de modo a deixa-la
balanceada
sua profundidade sera log n (se nao fosse balanceada,ou seja todos os
elementos a serem inseridos ja chegassem ordenados, teriamos uma lista
ligada,
ou uma arvore desbalanceada com profundidade n), assim a busca eh feita
num tempo proporcional a log n, chegando, no total a um algoritmo com
tempo
proporcional a n log n.
Obs: este programa foi feito no Turbo C++ versao 3.0 e testado em
ambiente
Windows NT / DOS, por favor me avise de quaisquer problemas no Linux.
Lennon Machado
16/3/99 9h00min
#include<stdio.h>
#include<stdlib.h>
/*criando os tipos que serao os nos da arvore binaria, semelhante as
listas ligadas*/
typedef struct aponta aponta, *ptr_aponta;
struct aponta
{
int pessoa;
int tamanho;
ptr_aponta prox_esq;
ptr_aponta prox_dir;
};
/*cria uma arvore binaria balanceada com as n pessoas*/
ptr_aponta faz_arvore(ptr_aponta raiz,int min,int max);
/*insere cada no da arvore com a correspondente pessoa*/
ptr_aponta insere_no(ptr_aponta raiz,int pess);
/*procura o numero da pessoa a ser assassinada atraves do indice*/
int buscaindice(ptr_aponta raiz,int indice);
/*remove um no da arvore*/
ptr_aponta remove(ptr_aponta raiz,int morto);
/*remove o no com o menor elemento de uma arvore ou sub-arvore*/
ptr_aponta remove_minimo(ptr_aponta no);
int main(void)
{
int m,n,indice=1,ct;
ptr_aponta lista=NULL;
char opcao[20];
do
{
printf("\nQuantas pessoas participarao do genocidio ? (maximo
20000)\n");
gets(opcao);
sscanf(opcao,"%d",&n);
printf("\nQual o passo de contagem para a execucao ?\n");
gets(opcao);
sscanf(opcao,"%d",&m);
/*verifica se os valores passados nao sao validos*/
if((m<=0)||(n<=0)||(n>20000))
printf("\nAssim nao tem graca...\n");
/*se forem validos*/
else
{
/*tenta criar a arvore binaria balanceada*/
if(!(lista=faz_arvore(lista,1,n))) /*se nao deu certo avisa e sai*/
printf("\nNao ha memoria suficiente para %d pessoas\n",n);
/*com a arvore criada*/
else
{
printf("\nPara %d pessoas, com passo %d, temos :\n",n,m);
while(n)
{
/*calcula o indice como explicado anteriormente*/
if(!(indice=(indice+m%n-1)%n))
indice=n;
/*verifica o numero da pessoacorrespondente aquele indice*/
ct=buscaindice(lista,indice);
/*imprime a pessoa*/
printf("%d, ",ct);
/*retira da arvore a pessoa*/
lista=remove(lista,ct);
/*decrementa o numero de pessoas*/
n--;
}
}
printf("\n");
}
/*opcao para rodar novamente o programa*/
printf("\nDeseja Continuar (Qualquer tecla=Sim / N=Nao) : ");
gets(opcao);
}while((opcao[0]!='n')&&(opcao[0]!='N'));
return(0);
}
/*cria uma arvore binaria balanceada com as n pessoas*/
ptr_aponta faz_arvore(ptr_aponta raiz,int min,int max)
{
/*calcula o ponto medio da arvore para que exista o mesmo numero
de elementos em cada lado na melhor distribuicao possivel*/
int centro=(min+max)/2;
/*se for um no valido*/
if(min<=max)
{
raiz=insere_no(raiz,centro); /*insere o novo no com a pessoa
central*/
raiz=faz_arvore(raiz,min,centro-1); /*cria sub-arvores com as pessoas
inferiores*/
raiz=faz_arvore(raiz,centro+1,max); /*a pessoa central (a esquerda) e
superiores*/
} /*(a direita)*/
/*retorna a raiz da arvore ou sub-arvore*/
return(raiz);
}
/*insere cada no da arvore com a correspondente pessoa*/
ptr_aponta insere_no(ptr_aponta raiz,int pess)
{
/*se estamos no nivel do no a ser criado*/
if(raiz==NULL)
{
if(!(raiz=(ptr_aponta)malloc(sizeof(aponta)))) /*tenta alocar espaco*/
return(NULL); /*no caso de erro nao retorna nada*/
raiz->pessoa=pess; /*inclui o numero da pessoa*/
raiz->tamanho=1; /*variavel que auxilia na busca,indica o numero de
nos da sub-*/
/*arvore iniciada nele, ate as folhas da arvore*/
raiz->prox_esq=NULL; /*inicializa os ponteiros para os nos esquerdo*/
raiz->prox_dir=NULL; /*e direito*/
return(raiz);
}
/*caso nao esteja no nivel correto*/
else
{
/*se o valor a ser inserido for menor que o do no atual*/
if(raiz->pessoa>pess)
raiz->prox_esq=insere_no(raiz->prox_esq,pess);/*vai p/ a sub arvore
esquerda*/
else
{
/*se for menor*/
if(raiz->pessoa<pess)
raiz->prox_dir=insere_no(raiz->prox_dir,pess);/*vai p/ a sub
arvore direita*/
}
}
/*incrementa o numero de nos existentes para cada sub-arvore*/
(raiz->tamanho)++;
/*retorna a raiz da arvore ou sub-arvore*/
return(raiz);
}
/*procura o numero da pessoa a ser assassinada atraves do indice*/
int buscaindice(ptr_aponta raiz,int indice)
{
/*se a arvore estiver vazia*/
if(raiz==NULL)
return(NULL); /*retorna vazio*/
/*verifica o numero de nos existentes a esquerda da raiz*/
int esq=(raiz->prox_esq!=NULL)? raiz->prox_esq->tamanho : 0;
/*se o indice da pessoa for menor ou igual ao numero de nos*/
if(indice<=esq)
return(buscaindice(raiz->prox_esq,indice)); /*continua para a
sub-arvore esquerda*/
/*se o indice for igual ao numero de nos mais um*/
if(indice==esq+1)
return(raiz->pessoa); /*encontou a pessoa*/
/*se o indice e maior calcula o novo indice para a sub-arvore direita e
continua*/
return(buscaindice(raiz->prox_dir,indice-esq-1));
}
/*remove um no da arvore*/
ptr_aponta remove(ptr_aponta raiz,int morto)
{
/*se a arvore esta vazia*/
if(raiz==NULL)
return(NULL); /*retorna vazio*/
/*se a pessoa a ser assassinada e menor que a do no atual*/
if(raiz->pessoa>morto)
raiz->prox_esq=remove(raiz->prox_esq,morto); /*continua na sub-arvore
esquerda*/
else
{
/*caso seja maior*/
if(raiz->pessoa<morto)
raiz->prox_dir=remove(raiz->prox_dir,morto);/*continua na sub-arvore
direita*/
/*se for igual*/
else
{
/*verifica se ha dois ramos inferiores, se houver utiliza o seguinte
algoritmo para
manter a arvore binaria balanceada*/
if((raiz->prox_esq!=NULL)&&(raiz->prox_dir!=NULL))
{
/*procura o menor elemento (mais a esquerda) da sub-arvore direita
e coloca neste no*/
raiz->pessoa=buscaindice(raiz->prox_dir,1);
/*remove o menor elemento (mais a esquerda) da sub-arvore
direita*/
raiz->prox_dir=remove_minimo(raiz->prox_dir);
}
/*senao, se o ramo esquerdo nao for nulo o retira, caso contrario
retira o direito*/
else
return((raiz->prox_esq!=NULL)? raiz->prox_esq : raiz->prox_dir);
}
}
/*decrementa o numero de nos existentes para cada sub-arvore*/
(raiz->tamanho)--;
/*retorna a raiz da arvore ou sub-arvore*/
return(raiz);
}
/*remove o no com o menor elemento de uma arvore ou sub-arvore*/
ptr_aponta remove_minimo(ptr_aponta no)
{
/*se sub-arvore esta vazia*/
if(no==NULL)
return(NULL); /*retorna vazio*/
/*se nao ha ramo esquerdo*/
if(no->prox_esq==NULL)
return(no->prox_dir); /*remove o ramo direito*/
/*senao remove o menor elemento (mais a esquerda)*/
no->prox_esq=remove_minimo(no->prox_esq);
/*decrementa o numero de nos existentes para cada sub-arvore*/
(no->tamanho)--;
/*retorna a nova sub-arvore apos a remocao do no*/
return(no);
}