学步园

和之前说的猴子选大王一样，一共N个人报数，报道M的人出列，之后继续从1开始报数，直到最后就剩一个人

之前说了一下数组的实现方法，其实还有很多实现的方法，这里说一下链表剔除的方法以及C++队列函数的实现方法

先说链表实现吧

#include<stdio.h>
#include<malloc.h>
#define LEN sizeof(struct monkey)
struct monkey
{
    int num;
    struct monkey*next;
};
struct monkey*creat(int n)
{
    int i;
    struct monkey*head,*p1,*p2;
    head=NULL;   /*先建立一个空链表*/
    for(i=1;i<=n;i++)
    {
        p1=(struct monkey*)malloc(LEN);
        p1->num=i;
      /*下面就是动态的建立链表了！*/
        if(i==1)
        head=p1;
        else
        p2->next=p1;
        p2=p1;
    }
    p2->next=head;/*最后一个猴子的下一个又是第一个猴子，围成一个环*/
    return head;
}
struct monkey *cut(struct monkey*head,int n)
{
    int m,i=1; /*第一个猴子已经数了一个数了*/
    struct monkey *p1,*p2,*p3;
    scanf("%d",&m);
    if(m==1)/*特殊情况的单独考虑*/
    {
        printf("%d",n);
        return 0;
    }
    p1=head;
    while(n>1)
    {
       if(i==m-1)
       {
           /*删除链接的办法剔除猴子*/
           p1->next=p1->next->next;
           i=0;             /*然后后面的猴子数数*/
           n--;
       }
       else
       {/*那么就开始数数*/
           i++;
           p1=p1->next;
       }
    }
    printf("%d",p1->num);
    free(p1);
}
int main()
{
    struct monkey*head,*p;
    int n;
    scanf("%d",&n);
    head=creat(n);
    p=cut(head,n);
    return 0;
}

下面说一下队列实现吧，这里先给大家介绍一下C++的队列函数

queue<int>x 定义一个名字为x的队列

x.front()   这个队列的第一个元素

x.pop()删除队首元素

x.pop(*)  往队列最后插入元素(*代表元素)

下面给出代码

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
#include<queue>
int main()
{
     int m,n;
     int i;
     while(scanf("%d%d",&n,&m)!=EOF)
     {
         queue<int>monkey;/*定义在内部每次初始化*/
         for(i=0;i<n;i++)
            monkey.push(i+1);
          /*这里就要往队列里加猴子了*/
         while(n>1)
         {
             for(i=1;i<m;i++)
             {
                 monkey.push(monkey.front());/*没有数到m的猴子放到队列后*/
                 monkey.pop ();/*在队列前删除这个猴子*/
                 /*这两步其实就等于将一个猴子移动到了队列之后*/
             }
             monkey.pop();/*删除数到m的猴子*/
             n--;
         }
         printf("%d\n",monkey.front());
     }
     return 0;
}

约瑟夫问题其实是一个很有意思的问题，还有一些公式解法，在这里就不多说了~