约瑟夫问题

游啊游

自己在电脑上编译通过，对于样例输出的答案也正确，但是oj一直WA........求指教

描述
约瑟夫问题：有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下的猴子再接着从1开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的编号。

输入
每行是用空格分开的两个整数，第一个是 n, 第二个是 m ( 0 < m,n <=300)。最后一行是：

0 0

输出
对于每行输入数据（最后一行除外)，输出数据也是一行，即最后猴王的编号
样例输入
6 2
12 4
8 3
0 0
样例输出
5
1
7

#include<iostream>
using namespace std;
struct node
{
        int number;
        node* next;
};
int main()
{
        int n,m,i;
        while(1)
        {
                cin>>n;
                cin>>m;
                if(n==0&&m==0)break;
                node* first=new node;
                first->number=1;
                first->next=NULL;
                node* s=first;
                for(i=2;i<=n;i++)  //建立链表
                {
                        node* temp=new node;
                        temp->number=i;
                        temp->next=NULL;
                        s->next=temp;
                        s=temp;
                }
                s->next=first;  //生成循环链表
                node* run=first;
                while(1)
                {
                        if(run->next==run)
                        {
                                cout<<run->number<<endl;
                                break;
                        }
                        else
                        {
                                for(i=1;i<m-1;i++)
                                {
                                        run=run->next;
                                }
                                node* b=run->next;
                                run->next=b->next;
                                run=run->next;
                                delete(b);
                        }
                }
        }
        return 0;
}

迷雾少年

迷雾少年

输入4 1 是不是应该输出4

迷雾少年

LZ你看看 ，应该没错了

#include<iostream>
using namespace std;
struct node
{
        int number;
        node* next;
};
int main()
{
        int n,m,i;
        while(1)
        {
                cin>>n;
                cin>>m;
                if(n==0&&m==0)break;
                node* first=new node;
                first->number=1;
                first->next=NULL;
                node* s=first;
                node *end = NULL;//指向末端
                for(i=2;i<=n;i++)  //建立链表
                {
                        node* temp=new node;
                        temp->number=i;
                        temp->next=NULL;
                        s->next=temp;
                        s=temp;
                }
                s->next=first;  //生成循环链表
                end = s;
                node* run=end;

                while(1)
                {
                        if(run->next==run)
                        {
                                cout<<run->number<<endl;
                                break;
                        }
                        else
                        {
                                 for(i=1;i<m;i++)
                                {
                                        run=run->next;
                                }

                                 /*
                                node* b=run->next;
                                run->next=b->next;
                                run=run->next;
                                */
                                node* b =  run->next; //Delete
                                run->next = run->next->next;


                                delete(b);
                        }
                }
        }
        return 0;
}

游啊游

迷雾少年 发表于 2016-8-21 15:54
LZ你看看 ，应该没错了

加入end指针的意义是什么？循环链表还要指定表尾？

游啊游

游啊游 发表于 2016-8-21 17:12
加入end指针的意义是什么？循环链表还要指定表尾？

明白了，谢谢

游啊游

迷雾少年 发表于 2016-8-21 15:41
输入4 1 是不是应该输出4

是

迷雾少年

游啊游 发表于 2016-8-21 17:20
明白了，谢谢

解决了就把问题设为解决吧

紫瞰

学习一下

iszhuangsha

支持4#