1:约瑟夫环问题
- 查看
- 提交
- 统计
- 提问
总时间限制:
1000ms
内存限制:
1000kB
描述
约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
输入
8 1 3 (n=8 k=1 m=3 )
输出
7 (剩下的那个)
样例输入
8 3 1
样例输出
7
这题比较坑，因为我用的是带头节点的循环链表，所以让这题很麻烦，在头节点那里需要特判，而且这题的数据会有一个坑就是起始的编号可能会大于n。
#include<cstdio>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<functional>
#include<cstring>
#include<string>
#include<cstdlib>
#include<iomanip>
#include<numeric>
#include<cctype>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<list>
#include<set>
#include<map>
using namespace std;
int sum=0,s;
template <class T>struct Node
{T data;Node<T> *next;
};
template <class T>
class List
{Node<T> *first;
public:List();List(int n); List(T a[],int n,int k);void display();T del(int be,int n);int Len();
};
template <class T>
List<T>::List()
{first=new Node<T>;first->next=NULL;
}
template <class T>
List<T>::List(int n) ///头插法
{first=new Node<T>;first->next=first;Node<T> *s;for(int i=n;i>=1;i--){s=new Node<T>;s->data=i;s->next=first->next;first->next=s;}
}
template <class T>
T List<T>::del(int be,int k)
{Node<T> *temp=first;T x;for(int i=1;i<be;i++){temp=temp->next;if(temp==first)i--;}while(Len()>0){for(int i=1;i<k;i++){temp=temp->next;if(temp==first) i--;}if(temp->next==first) temp=temp->next;Node<T> *q;q=temp->next;x=q->data;temp->next=q->next;delete q;sum++; if(sum==s){cout<<x;break;}}return x;}
template <class T>
void List<T>::display()
{Node<T> *temp=first;if(first!=NULL){do{temp=temp->next;}while(temp!=first);}
}
template <class T>
int List<T>::Len()
{Node<T> *temp=first;int j=0;if(first!=NULL){do {temp=temp->next;j++;}while(temp!=first);}return j-1;
}
int main()
{int n,m,be;while(scanf("%d%d%d",&n,&be,&m)!=-1){sum=0;s=n;List<int> l1(n);l1.del(be,m);}return 0;
}