使用禁忌搜索法约求解瑟夫环改进算法.txt

使用禁忌搜索法约求解瑟夫环改进算法

/*这个程序有两个大问题：一、在程序中通过把出圈的人的编号置为0的方法来表示出圈，这样就改变了其原来的编号，不符合游戏规则；二、如果要知道所有的出圈顺序，显然在原来的程序中稍作修改，就可以了。但是如果想要知道任意个出圈的人的编号（比如第6个出圈的人的编号），原来的程序就不能满足了。想了一下，如果采用禁忌搜索法则可以轻易解决这个问题。

       禁忌搜索法：使用一个禁忌表，记录下不允许搜索的元素。在后面的搜索中，根据禁忌表来决定如何处理当前元素。用在约瑟夫环中，我们可以用一个数组记录下已经出圈的人的编号，这样再数数时，可以根据禁忌表来判断此人是否还在圈内。*/




#define N 100
void yuesefu1(int data[],int result[],int sum,int k)
{
   int i=0,j=0,count=0;
   int n;
   while(count<sum)
   {
     for(n=0;n<count;n++)/*根据禁忌表判断此人是否还在圈内*/
        if(result[n]==data[i])
           break;
     if(n>=count)/*若此人还在圈内*/
           j++;
     if(j==k)
     {
         result[count++]=data[i];/*把出圈的人的编号存入禁忌表*/
         j=0;
     }
     i++;
     if(i==sum)
         i=0;
   }
}

void main()
{
   int data[N];
   int result[N]={0};
   int i,j,total,k;
   printf("\nPlease input the number of every people.\n");
   for(i=0;i<N;)
   {
      int input;
      scanf("%d",&input);
      if(input==0)
           break;
      for(j=0;j<i;j++)
         if(data[j]==input)
           break;
      if(j>=i&&input>0)
      {
         data[i]=input;
         i++;
      }
      else
           printf("\nData error.Re-input:");
   }
   total=i;
   printf("\nYou have input:\n");
   for(i=0;i<total;i++)
   {
     if(i%10==0)
           printf("\n");
     printf("%4d",data[i]);
   }
   printf("\nPlease input a number to count:");
   scanf("%d",&k);
   yuesefu1(data,result,total,k);
   printf("\nThe sequence is:\n");
   for(i=0;i<total;i++)
     printf("%d  ",result[i]);
}