猴子选大王.txt

数据结构的线性表及其应用

约瑟夫问题的实现：n只猴子要选猴王，所有猴子按1，2，…，n编号围坐一圈，从第1号开始按1,2, …，m报数，凡报到m号的猴子退出圈外，如此循环报数，直到圈内剩下一只猴子时，这个猴子就是猴王。编写一个程序实现上述过程，n和m由键盘输入。

   采用顺序表存储。使用一个数组A，最多可存放MaxSize个元素，初始时A[i]可存放猴子的编号i+1,计数器count的值为0。从A[i]开始循环报数，每报一次，计数器的值加1，报到m时便打印出A[i]的值，同时将A[i]的值改为0，计数器的值重新赋为0。该过程一直进行到n只猴子全部退出到圈外为止，最后退出的便于是猴王。实现本题功能的程序如下：


   /*顺序表应用*/
  #include<stdio.h>
int main(){/*定义变量*/
       int A[10000]={0};                    /*这里定义一个数组存放猴子退出状态，
                                          1为已经退出，0为未退出，初始值都为0*/
       int a = 0;                                          /*a为数的数，初始值为0*/
       int n=0,b=0,Count=0,m=0;                 /*n为猴子的总数，初始值为0
                                                  b为剩下猴子数，初始值为0
                                                  Count为循环计数量，初始值为0*/
       printf("输入猴子总数n:");
       scanf("%d",&n);                                    
       printf("数到哪个编号的猴子退出:");
       scanf("%d",&m);
       b=n;
       while( b > 1 ){                         /*剩下的猴子多余1个，循环*/
       if( A[Count] == 0 ){    /*没有退出的猴子才数数*/
       a++;                     /*猴子数数*/                                  
 }
       if( a == m){                            /*数到m*/
       A[Count] = 1;             /*让数到m的猴子退出*/
       b--;                          /*剩下的猴子减一*/
       a = 0;                             /*重新数数*/
      }
       Count++; 
       if( Count == n ){    /*如果数到最后一只猴子了，从头再开始*/
       Count = 0;
      }            
     }
/*找到最后一只猴子的位置，并打印*/
       a=0; 
       while( 1 ){
       if( A[a++] == 0 ){        /*找到没有退出的猴子*/
       printf("被选为猴王的猴子的编号是：%d\n",a);
       break;    
      }    
    }
   }