7-34 猴子选大王 (20分)

一群猴子要选新猴王。新猴王的选择方法是：让N只候选猴子围成一圈，从某位置起顺序编号为1~N号。从第1号开始报数，每轮从1报到3，凡报到3的猴子即退出圈子，接着又从紧邻的下一只猴子开始同样的报数。如此不断循环，最后剩下的一只猴子就选为猴王。请问是原来第几号猴子当选猴王？

输入格式：

输入在一行中给一个正整数N（

输出格式：

在一行中输出当选猴王的编号。

输入样例：

输出样例：

7


此题我用了三种方法，当然第三种最好，第一种就是利用数组来标记在内还是不在内的，好处是一眼就能看懂，坏处是跟这个N有关，如果N太大就。。。
第二种是利用链表 其实和数组大致相同只不过要找到被删除的前一个,这样方便删除，直到最后一个为止。
第三种办法是最优解，只不过这题的n最大的时候也太小，显现不出来。他实质上是将每次编号重拍  然后最后剩下的编号一定为0  反推回来   最好不要用递归
因为如果递归深度过大，会系统栈益出。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct lnode
{
 int data;
 struct  lnode *next;  
}lnode ;
//约瑟夫环经典问题 
//数组标记法   
int arr(int n,int m)
{
 int a[n];
 int i,j;
 memset(a,0,n*sizeof(int));
 int count=n;
 for(i=0,j=0;count!=0;i=(i+1)%n)
 {
  if(a[i]==0)
  {
   j++;
   if(j%m==0)
   {
    j=0;
    a[i]=1;
    count--;
   } 
  }
  
 }
 printf("%d\n",(i-1+n)%n+1);
 
 
 } 
 
 //链表 
 int clnode(int n,int m)
 {
  int count=0;
  int i;
  lnode *l=malloc(sizeof(lnode));
  l->next=NULL; 
  lnode *s;
  lnode *p=l;
  for(i=1;i<=n;i++)
  {
   s=malloc(sizeof(lnode));
   s->data=i;
   s->next=p->next;
   p->next=s;
   p=s; 
   
   
  }
  p->next=l->next; 
  free(l); 
  while(p!=p->next)
  {
   count=0;
   while(count<m-1)
   {
    count++;
    p=p->next;
   }
  s=p->next;
  p->next=s->next;
  free(s); 
   
   
  }
  printf("%d\n",p->data); 
  return 1;
 }
 int ysf(int n,int m)    //最有解  将每次编号重拍  然后最后剩下的编号一定为0  反推回来   最好不要用递归 
 {
  int i;
  int x=0; 
  for(i=2;i<=n;i++)
  x=(x+m)%i;
  printf("%d\n",x+1);
  return x;
  
  } 
  
int main()
{
 int n;
 scanf("%d",&n);
// arr(n,3);
// clnode(n,3);
 ysf(n,3);
 return 0;
 }

7-34 猴子选大王 (20分)

输入格式：

输出格式：

输入样例：

输出样例：

推荐阅读