Desafio

["Lennon Machado" <lennonx@hotmail.com>]

Prof. Yoshi,

Andei pensando sobre o desafio e tenho a seguinte ideia:

1-implementar um vetor de inteiros com os numeros de todas as pessoas
2-implementar uma lista que aponta para o numero da pessoa viva e para a 
proxima pessoa viva
3-se m>numero de pessoas vivas seria necessario dar uma ou mais voltas 
completas no circulo de pessoas restante, porem basta saber o resto da 
divisao de m pelo numero de pessoas vivas para saber quantos passos 
andar.
4-calcular o indice da pessoa a ser assassinada por:
indice_proximo=resto da divisao de (indice_atual+numero_de_passos(item 
3)-1) por numero_de_pessoas_vivas

Ex:
n=8 m=4
           |------------------------------
           \/                             |
lista:     p1->p2->p3->p4->p5->p6->p7->p8-
           |   |   |   |   |   |   |   |  
           \/  \/  \/  \/  \/  \/  \/  \/
numeracao: 1   2   3   4   5   6   7   8

apos uma iteracao:
           |------------------------------
           \/                             |
lista:     p1->p2->p3----->p5->p6->p7->p8-
           |   |   |       |   |   |   |  
           \/  \/  \/      \/  \/  \/  \/
numeracao: 1   2   3   4   5   6   7   8

Ate que nao haja mais sobreviventes.

Eis o programa:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

typedef struct aponta aponta, *ptr_aponta;

struct aponta
{
int*  pessoa;
ptr_aponta prox;
};

int main(void)
{
int   m,n,indice,ct;
int*  numeracao;
ptr_aponta lista,proc;
char opcao[3];
do
  {
  printf("\nQuantas pessoas participarao do genocidio ? (maximo 
2000)\n");
  gets(opcao);
  sscanf(opcao,"%d",&n);
  printf("\nQual o passo de contagem para a execucao ?\n");
  gets(opcao);
  sscanf(opcao,"%d",&m);
  if((m<=0)||(n<=0)||(n>2000))
    printf("\nAssim nao tem graca...\n");
  else
    {
    if(!(numeracao=(int*)malloc(n*sizeof(int))) ||
       !(lista=(ptr_aponta)malloc(n*sizeof(aponta))))
      printf("\nNao ha memoria suficiente para %d pessoas\n",n);
    else
      {
      for(indice=0;indice<=n;indice++)
	{
	*(numeracao+indice)=indice;
	(lista+indice)->pessoa=numeracao+indice;
	(lista+indice)->prox=lista+indice+1;
	}
      (lista+indice-1)->prox=lista;

      printf("\nPara %d pessoas, com passo %d, temos :\n",n,m);
      indice=1;
      while(n)
	{
	if(!(indice=(indice+m%n-1)%n))
	  indice=n;
	for(proc=lista,ct=0;ct<indice-1;ct++)
	  proc=proc->prox;
	printf("%d, ",*((proc->prox)->pessoa));
	proc->prox=(proc->prox)->prox;
	n--;
	}
      }
    printf("\n");
    }
  free(numeracao);
  free(lista);
  printf("\nDeseja Continuar (Qualquer tecla=Sim / N=Nao) : ");
  gets(opcao);
  }while((opcao[0]!='n')&&(opcao[0]!='N'));
return(0);
}

Tambem tentei deixar o laco for mais inteligente, mas realizei medidas 
de tempo para situacoes semelhantes e para 0<n<2001 e m>0 nao causou 
beneficios, pelo contrario, aumento em quase 1 segundo o tempo de 
execucao do algoritmo:

      printf("\nPara %d pessoas, com passo %d, temos :\n",n,m);
      indice=1;
      proc=lista->prox;
      ct=1;
      while(n)
	{
	if(!(indice=(indice+m%n-1)%n))
	  indice=n;
	if(ct>indice-1)
	  {
	  proc=lista;
	  ct=0;
	  }
	for(;ct!=indice-1;ct=++ct%n)
	  proc=proc->prox;
	printf("%d, ",*((proc->prox)->pessoa));
	proc->prox=(proc->prox)->prox;
	n--;
	}

Qual a opiniao sobre o programa ? Melhorias ? Criticas ? Sugestoes ?

Lennon Machado
3/3/99 11h05min
retransmitido em
9/3/99 7h50min

______________________________________________________
Get Your Private, Free Email at http://www.hotmail.com