Solucao do Desafio de Josephus com arvores binarias balanceadas

[Lennon de Almeida Machado <lennonx@hotmail.com>]

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);
}