N个人坐成一个圆环(编号为1 - N),从第S个人开始报数,数到K的人出列,后面的人重新从1开始报数。问最后剩下的人的编号。
创新互联坚信:善待客户,将会成为终身客户。我们能坚持多年,是因为我们一直可值得信赖。我们从不忽悠初访客户,我们用心做好本职工作,不忘初心,方得始终。十余年网站建设经验创新互联是成都老牌网站营销服务商,为您提供网站设计制作、成都网站制作、网站设计、HTML5建站、网站制作、高端网站设计、小程序制作服务,给众多知名企业提供过好品质的建站服务。例如:N = 3,K = 2,S = 1。2号先出列,然后是1号,最后剩下的是3号。
要求使用循环链表实现。
【输入】测试数据有多组
每组包括3个数N、K、S,表示有N个人,从第S个人开始,数到K出列。(1<= N<= 10^6,1<= K<= 10, 1<= S<= N)
【输出】出列的人的编号
【输入样 例】13 3 1
3 2 1
3 6 9 12 2 7 11 4 10 5 1 8 13
2 1 3
#includeusing namespace std;
class ListNode{
public:
int data;
ListNode* next;
ListNode() {
next = NULL;
}
};
class LinkList{
int len;
ListNode* head;
public:
int n, k, s;
LinkList() {
head = new ListNode();
}
~LinkList() {
delete head;
}
void CreateList();
void Test();
};
void LinkList::CreateList()
{
len = n;//传入len
ListNode* p = head;//从头结点开始
ListNode* q;
for (int i = 1; i<= n; i++)//因为此时插入一个更新一个,所以不存在,之前的插入问题
{
q = new ListNode();
q->data = i;//传入数据
p->next = q;//指向q这个新结点
p = p->next;//移动到当前最新的一位
}
p->next = head;//构成循环
}
void LinkList::Test()
{
int i;
ListNode* p = head;
for (i = 1; i< s ; i++)//找到要开始的那一位,是index的作用
p = p->next;
while (len)//直到出列完成
{
if (p->next == head)//删除结点使得p->next为头节点,则p要多移一次。
p = p->next;
for (i = 1; i< k; i++)//从1开始报数,报到k-1位
{
p = p->next;
if (p->next == head)//在p向后位移的时候如果遇到头结点,多移一次。
p = p->next;
}
ListNode* q = p->next;//上一个for循环找到了要删除的节点的前一位,这时候用q代表要删除的结点
cout<< q->data;
p->next = q->next;//先变指针域,改为删去的节点的下一位
delete q;
len--;
if (len != 0) {
cout<< " ";
}
}
cout<< endl;
}
int main()
{
int N, K, S;
while (cin>>N>>K>>S)
{
LinkList myList;
myList.n = N;
myList.k = K;
myList.s = S;
myList.CreateList();
myList.Test();
}
return 0;
}
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧