约瑟夫问题
自己在电脑上编译通过，对于样例输出的答案也正确，但是oj一直WA........求指教{:10_272:}描述
约瑟夫问题：有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下的猴子再接着从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;
}
本帖最后由 迷雾少年 于 2016-8-21 15:45 编辑
{:10_266:} 输入4 1 是不是应该输出4 本帖最后由 迷雾少年 于 2016-8-21 16:16 编辑
LZ你看看{:10_266:} ，应该没错了
#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指针的意义是什么？循环链表还要指定表尾？
明白了，谢谢{:10_256:} 迷雾少年 发表于 2016-8-21 15:41
输入4 1 是不是应该输出4
是{:10_243:} 游啊游 发表于 2016-8-21 17:20
明白了，谢谢
解决了就把问题设为解决吧{:10_277:} 学习一下 支持4#
页:
[1]