约瑟夫问题

游啊游

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

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

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

0 0

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

1. 
   
2. #include<iostream>
   
3. using namespace std;
   
4. struct node
   
5. {
   
6.         int number;
   
7.         node* next;
   
8. };
   
9. int main()
   
10. {
    
11.         int n,m,i;
    
12.         while(1)
    
13.         {
    
14.                 cin>>n;
    
15.                 cin>>m;
    
16.                 if(n==0&&m==0)break;
    
17.                 node* first=new node;
    
18.                 first->number=1;
    
19.                 first->next=NULL;
    
20.                 node* s=first;
    
21.                 for(i=2;i<=n;i++)  //建立链表
    
22.                 {
    
23.                         node* temp=new node;
    
24.                         temp->number=i;
    
25.                         temp->next=NULL;
    
26.                         s->next=temp;
    
27.                         s=temp;
    
28.                 }
    
29.                 s->next=first;  //生成循环链表
    
30.                 node* run=first;
    
31.                 while(1)
    
32.                 {
    
33.                         if(run->next==run)
    
34.                         {
    
35.                                 cout<<run->number<<endl;
    
36.                                 break;
    
37.                         }
    
38.                         else
    
39.                         {
    
40.                                 for(i=1;i<m-1;i++)
    
41.                                 {
    
42.                                         run=run->next;
    
43.                                 }
    
44.                                 node* b=run->next;
    
45.                                 run->next=b->next;
    
46.                                 run=run->next;
    
47.                                 delete(b);
    
48.                         }
    
49.                 }
    
50.         }
    
51.         return 0;
    
52. }
    

复制代码

迷雾少年

迷雾少年

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

迷雾少年

LZ你看看 ，应该没错了

1. 
   
2. #include<iostream>
   
3. using namespace std;
   
4. struct node
   
5. {
   
6.         int number;
   
7.         node* next;
   
8. };
   
9. int main()
   
10. {
    
11.         int n,m,i;
    
12.         while(1)
    
13.         {
    
14.                 cin>>n;
    
15.                 cin>>m;
    
16.                 if(n==0&&m==0)break;
    
17.                 node* first=new node;
    
18.                 first->number=1;
    
19.                 first->next=NULL;
    
20.                 node* s=first;
    
21.                 node *end = NULL;//指向末端
    
22.                 for(i=2;i<=n;i++)  //建立链表
    
23.                 {
    
24.                         node* temp=new node;
    
25.                         temp->number=i;
    
26.                         temp->next=NULL;
    
27.                         s->next=temp;
    
28.                         s=temp;
    
29.                 }
    
30.                 s->next=first;  //生成循环链表
    
31.                 end = s;
    
32.                 node* run=end;
    
33. 
    
34.                 while(1)
    
35.                 {
    
36.                         if(run->next==run)
    
37.                         {
    
38.                                 cout<<run->number<<endl;
    
39.                                 break;
    
40.                         }
    
41.                         else
    
42.                         {
    
43.                                  for(i=1;i<m;i++)
    
44.                                 {
    
45.                                         run=run->next;
    
46.                                 }
    
47. 
    
48.                                  /*
    
49.                                 node* b=run->next;
    
50.                                 run->next=b->next;
    
51.                                 run=run->next;
    
52.                                 */
    
53.                                 node* b =  run->next; //Delete
    
54.                                 run->next = run->next->next;
    
55. 
    
56. 
    
57.                                 delete(b);
    
58.                         }
    
59.                 }
    
60.         }
    
61.         return 0;
    
62. }
    

复制代码

游啊游

迷雾少年 发表于 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#