减少领取救济金排队的长度是一个严重的问题,The New National Green Labour Rhinoceros
Party (这个党派)依据如下规则.
每天来领取救济金的人排成一个大圆环.任选一人标识为1,其他的人按照逆时针顺序开始标识,一直到N(第N个人在第一个人的左边).
一个官员逆时针从编号为1的人开始数,数K人后结束,另外一个官员从N开始,顺时针开始,数m人结束.
俩个被选中的人从圆环里拿出来.如果俩个官员选中的是同一个人,那么这个人送去从政,每个官员然后从下一个可用的人开始,
继续数,直到没有人剩下,注意两个被选 中的人是同时走掉的，所以就有可能两个官员选中一个人
输入
读取三个数,N,k,m（k,m>0）,计算出被选中人的顺序,0 0 0代表输入结束
输出
对每一个三元组,输出一行表示被选中人的编号的顺序,每一个数字应该占三个字符,俩个被选中人,逆时针被选中人的编号在前面,
每一对之间以逗号分开
#include<stdio.h>
#include<iostream>
using namespace std; struct Node
{
Node* next;
Node* pre;
int data;
};
Node* init(const int n);
void printNode(const int n, const Node* kNode, const Node* mNode);
int main()
{
freopen("d:\\1.txt", "r", stdin);
int n, k, m;
while (cin)
{
cin >> n >> k >> m;
if(n == 0 && k == 0 && m == 0)
{
return 0;
}
Node* head = init(n);
Node* tail = head->pre;
while (n--)
{
Node* kNode = head;
Node* mNode = tail;
for(int i = 1; i < k; i++)
{
kNode = kNode->next;
}
for(int i = 1; i < m; i++)
{
mNode = mNode->pre;
}
printNode(n, kNode, mNode); kNode->pre->next = kNode->next;
kNode->next->pre = kNode->pre;
head = kNode->next;
if(kNode == mNode)
{
tail = kNode->pre;
}
else
{
tail = mNode->pre;
mNode->next->pre = mNode->pre;
mNode->pre->next = mNode->next;
if(head==mNode)
head = mNode->next;
n--;
}
}
cout << endl;
} return 0;
} Node* init(const int n)
{
Node* head = NULL;
Node* next = NULL;
for(int i = 1; i <= n; i++)
{
Node* node = new Node;
node->data = i;
if(i == 1)
{
head = node;
next = node;
continue;
}
next->next = node;
node->pre = next;
next = node;
}
next->next = head;
head->pre = next;
return head;
}
void printNode(const int n, const Node*kNode, const Node* mNode)
{
if(kNode == mNode)
{
if(n == 0)
{
printf("%3d", kNode->data);
}
else
{
printf("%3d,", kNode->data);
}
}
else
{
if(n == 1)
{
printf("%3d%3d", kNode->data, mNode->data);
}
else
{
printf("%3d%3d,", kNode->data, mNode->data);
}
}
}
相关题,约瑟夫环,做DP再做