约瑟夫环问题，C++，循环链表法，递归法，循环法

循环法的代码量极为简单，递归法也简单，循环链表的代码量就很大了
Java有ArrayList可以很方便的做这道题，但还未尝试，日后补充。

#include <iostream>
#include <stdio.h>
#include <stdlib.h>

using namespace std;

//循环链表
void LinkedList(int amount,int count)
{
    struct Node
    {
        int number;
        struct Node * next;
    };
    //构造链表
    Node *head = (Node *)malloc(sizeof(Node));//构造头部
    Node *s = (Node *)malloc(sizeof(Node));//用于存放数据的新节点
    Node *temp;                            //用于记录保存节点地址的中介节点
    s = head;
    for(int i=1; i<=amount; ++i)
    {
        if(i == 1)                         //单独赋值head节点
        {
            s->number = i;
            continue;
        }
        temp = (Node *)malloc(sizeof(Node));
        temp->number = i;
        s->next = temp;                  //尾插法
        s = temp;
    }
    temp->next = head;                   //尾部指向头部，形成循环

    //按号删除节点
    Node *kill = temp;                   //提前将头部的前一个节点保存在kill里
    Node *q;                             //用于记录kill地址，方便释放点到的地址；
    for(int i=0;i<amount;++i)
    {
        for(int j=0;j<count;++j)
        {
            temp = kill;
            kill = kill->next;
        }
        cout<<kill->number<<"  ";
        q = kill;                       //记录kill地址
        temp->next = kill->next;
        kill = temp;
        delete q;
    }

}



//递归方法
int Joseph(int amount,int count)
{
    if(amount == 1)
        return 0;
    else
        return (Joseph(amount-1,count)+count)%amount;
}
//递归分步
int Joseph_Step(int amount,int count,int i)
{
    if(i == 1)
        return (amount+count-1)%amount;
    else
        return (Joseph_Step(amount-1,count,i-1)+count)%amount;
}



//循环方法
int Loop(int amount,int count)
{
    int result = 0;
    for(int i=2 ; i<=amount ; ++i)
    {
        result = (result + count)%i;
    }
    return result;
}

int main()
{
    int amount,count;
    cout<<"请输入人数（大于1）：";
    cin>>amount;
    cout<<"出列序号为：";
    cin>>count;

    //循环
    cout<<"循环所得结果为：";
    cout<<Loop(amount,count)+1<<endl;

    //递归
    cout<<"递归所得结果为：";
    cout<<Joseph(amount,count)+1<<endl;

    //约瑟夫分步
    cout<<"递归算法所得队列为：";
    for(int i = 1; i <= amount; ++i)
        cout<<Joseph_Step(amount,count,i)+1<<"  ";
    cout<<endl;

    //循环链表
    cout<<"循环链表所得队列为：";
    LinkedList(amount,count);

    return 0;
}