A41004. 幸运儿
填空题
较难
知识点
题目描述
幸运儿
题目描述
n 个人围成一圈, 并依次编号1～n，从编号为1 的人开始，按顺时针方向每隔一人选出一个，当一圈结束之后，剩下的人重新围成一圈，再次从编号1的人开始，如此循环直到剩下两人，这剩下的两人就是幸运儿。如果你想成为最后两个幸运儿，请问开始时应该站在什么位置？（设3<=n<=50）
输入格式
有多个测试序列。每行是开始时的人数n
输出格式
第1 行是选出顺序，第2 行是两名幸运儿的开始位置（按升序排列），位置编号之间用一个空格分开。
样例输入
12
20
样例输出
2 4 6 8 10 12 3 7 11 5
1 9
2 4 6 8 10 12 14 16 18 20 3 7 11 15 19 5 13 9
1 17
参考答案
#include <stdio.h>
#include <malloc.h>
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LinkNode;
void CreateList(LinkNode *&L,ElemType a[],int n) //采用尾插法保存元素
{
LinkNode *s,*r;
L=(LinkNode *)malloc(sizeof(LinkNode));
r=L;
for(int i=0;i<n;i++)
{
s=(LinkNode *)malloc(sizeof(LinkNode));
s->data=a[i];
r->next=s;
r=s;
}
r->next=NULL;
}
void DispList1(LinkNode *&L)
{
LinkNode *p=L->next;
int index=-1; //及第一个元素标记为-1
while(p!=NULL)
{
if(index==1) //如果标记为1
{
printf("%d ",p->data); //输出这个元素
p->data=0; //把这个元素置位0,表示不在考虑
}
p=p->next; //访问下一个元素
index=index*-1; //控制释放元素
}
LinkNode *pre=L,*q;
q=L->next;
while(q!=NULL)
{
if(q->data==0) //如果这个元素为0,及已经被用过，释放该元素
{
pre->next=q->next;
free(q);
q=pre->next;
}
else
{
pre=q;
q=q->next;
}
}
}
void DispList2(LinkNode *L) //输出最后两个幸运儿
{
LinkNode *p=L->next;
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
}
int ListLength(LinkNode *L) //返回还有几个元素
{
int n=0;
LinkNode *p=L;
while(p->next!=NULL)
{
n++;
p=p->next;
}
return n;
}
int main()
{
int n;
LinkNode *L;
while(scanf("%d",&n)!=EOF)
{
int a[n];
for(int i=0;i<n;i++)
{
a[i]=i+1;
}
CreateList(L,a,n);
while(ListLength(L)!=2) //如果剩余元素量不等于2
{
DispList1(L); //释放元素
}
printf("\n");
DispList2(L); //输出幸运儿
printf("\n");
}
}
上一题
下一题