循环链表解决约瑟夫问题（简化版）

http://blog.csdn.net/jw903/article/details/38965477

约瑟夫环是一个经典的数学的应用问题：已知N个人（以编号1，2，3...N分别表示）围坐在一张圆桌周围。从编号为1的人开始报数，数到M的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

这个代码非常简短，但还是利用循环链表完成了求解约瑟夫问题的功能

代码如下：

[cpp] view plain copy

#include<iostream>  

#include<cassert>  

using namespace std;  

typedef struct Node  

{  

    int item;  

    struct Node *next;  

}ListNode,*List;  

int main()  

{  

    int M;//规则（隔M个数）  

    int N;//人数（N个人）  

    int a;//编号  

    int i;  

    cout<<"input the N and M"<<endl;  

    cin>>N>>M;  

    List head=(List)malloc(sizeof(ListNode));  

    assert(head!=NULL);  

    cin>>a;  

    head->item=a;  

    head->next=head;  

    ListNode *p=head;  

    for(i=2;i<=N;i++)//构造循环链表，值为1的结点为链表头  

    {  

        cin>>a;  

        p->next=(List)malloc(sizeof(ListNode));  

        p=p->next;  

        p->item=a;  

        p->next=head;  

    }  

    while(p!=p->next)//while循环开始时，p指向链表的尾结点  

    {  

        for(i=1;i<M;i++)  

            p=p->next;  

        ListNode *targetnode=p->next;  

        cout<<targetnode->item<<"出局"<<endl;  

        p->next=p->next->next;  

        free(targetnode);  

    }  

    cout<<p->item<<endl;  

    return 0;  

}  

总结

以上是生活随笔为你收集整理的循环链表解决约瑟夫问题（简化版）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。