thejosephuwreathproblemsolves.txt

The Josephu wreath problem solves

	置标志
 #include<stdio.h>

void priList(int *prilist,int count)  //打印表prilist的前count的元素
{
      int priloop;
      for(priloop=0;priloop<count;priloop++)
      {
	       printf("%-4d",prilist[priloop]);
      }
      printf("\n****************************************\n");
}

void  Josephu()        //Josephu算法求解
{
      int listlen,position,stand; //记录表长，所求元素位置，和引入间隔数
      int loop;         //循环计数器
      int newpos;     //记录前进步伐
      int *Joselist,*newlist;
      printf("\n####### N REPRENT THE LENTH OF THE LIST########\n");
      printf("N=");     //提示输入表长度
      scanf("%d",&listlen);        
      printf("########## X REPRENT WHO WILL STAND UP#########\n");
      printf("X=");      //输入间隔数
      scanf("%d",&stand);
      Joselist=(int *)malloc(listlen*sizeof(int));      //根据输入的长度分配空间大小
      newlist=(int*)malloc(listlen*sizeof(int));      //建新表
      for(loop=0;loop<listlen;loop++)     //按顺序将Joselist添满
	  Joselist[loop]=loop+1;
      printf("****************************************\n");  //打印出原表
      printf("            PRIMARY LIST             \n");
      priList(Joselist,listlen);
      newpos=0;        
      position=0;        
      while(newpos<listlen)        //寻找所求元素
      {
	   loop=0;
	    while(loop<stand-1)
	    {
	      while(Joselist[position]==-1)
		      position=(position+1)%listlen;
	      position=(position+1)%listlen;
	      loop++;
	    }
	    while(Joselist[position]==-1)
	        position=(position+1)%listlen;     //找到所求
	    newlist[newpos++]=Joselist[position];    //所求元素进新表
	    Joselist[position]=-1;                 //在该元素在原表中的位置添加标志-1
      }
      printf("****************************************\n");
      printf("            NEW LIST             \n"); //打印新表即所求
      priList(newlist,listlen);
}

main()
{
    Josephu();
}