1067: 顺序排号

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 31  Solved: 16
[Submit][Status][Web Board]

Description

有n人围成一圈,顺序排号。从第1个人开始报数(从1到3报数),凡报到3的人退出圈子,问最后留下的是原来的第几号的那位。

Input

初始人数n

Output

最后一人的初始编号

Sample Input

3

Sample Output

2

HINT

 

Source


 
  水题,约瑟夫环
  最近快考试了,趁机刷刷水题,正好夯实一下基础。
  思路:用链表做的,写的时候很容易出问题。
  代码
 #include <iostream>

 using namespace std;
struct Node{
int data;
Node* next;
};
int main()
{
Node *head = new Node;
Node *p = head;
int i,n;
cin>>n;
for(i=;i<=n;i++){
if(i==){
p->data=i;
p->next = NULL;
continue;
}
//cout<<p<<endl;
Node *t = new Node;
t->data = i;
t->next = NULL;
p->next = t;
p = p->next;
}
p->next = head;
p = head;
/* 输出测试
int t = head.data;
do{
cout<<p->data<<' ';
p = p->next;
}while(p->data!=t);
cout<<endl;
*/
//模拟报数
int num = ;
while(){
if(num==){
if(p->next->next==p)
break;
else{
Node * t = new Node;
t = p->next;
p->next = t->next;
//cout<<t->data<<endl;
delete(t);
p = p->next;
num=;
}
}
else{
p = p->next;
num++;
}
}
cout<<p->data<<endl;
return ;
}

Freecode : www.cnblogs.com/yym2013

05-08 15:50