小弟我的用链表编的 人围圈踢人有关问题 最后记录留下人的位置 大家讨论讨论
我的用链表编的 人围圈踢人问题 最后记录留下人的位置 大家讨论讨论
题目:n 个人围成一圈, 并依次编号1～n，。从编号为1 的人开始，按顺时针方向每隔一人选出一个，
剩下的人重新围成一圈，如此循环直到剩下两人，这剩下的两人就是幸运儿。如果你想成为最后两个
幸运儿，请问开始时应该站在什么位置？（设3 <=n <=50）
我的想法,主要算法 ,没有经过调试
struct Tnode
{
int pos;//位置
Tnode *next;
}Tnode *head;
Tnode *p=head;
int count;//人的个数
...
while(count!=2)//最后留下的2个人
{
if(*p-> next-> next==NULL) //判断从下一个循环是踢第一个人,还是跳一个人,踢下一个
*p=head; //设置下循环踢人的位置
else
*p=head-> next;
for( ;*p-> next!=NULL||*p-> next-> next!=NULL;*p=*p-> next-> next)
{
DelNode(p); //删除当前节点
count--; //人数减1
}
}
count> > head.pos> > head-> next.pos;//输出
因为要记录人的幸运位置 所以我觉得用链表简单些,用数组应该也行,但是我不知道如何处理数组中让元素踢出数组.
大家有什么好想法 来说说啊~
------解决方案--------------------
/*约瑟夫环*/
#include <stdlib.h>
#include <stdio.h>
typedef struct node
{
int data;
struct node *next;
}LNode;
main()
{
LNode* Create(int,int);
LNode* GetNode(LNode *);
int Print(LNode *,int);
LNode *p;
int n,k,m;
do
{
printf ( "输入总人数 ");
scanf ( "%d ",&n);
}
while (n <=0);
do
{
printf ( "输入开始人的序号(1~%d) ",n);
scanf ( "%d ",&k);
}
while (k <=0 || k> n);
do
{
printf ( "输入间隔数字 ");
scanf ( "%d ",&m);
}
while(m <=0);
p=Create(n,k);
Print(p,m);
return 0;
}；
LNode* Create(int n,int k)/*创建循环链表*/
{
int start=k-1;
LNode *s,*p,*L=0,*t;
if (start==0) start=n;
while (n!=0)
{
s=(LNode *)malloc(sizeof(LNode));
if (L==0) p=s;
if (n==start) t=s;
s-> data=n;
s-> next=L;
L=s;
n--;
}
p-> next=L;
return t;
}
LNode* GetNode(LNode *p)/*出队函数*/
{
LNode *q;
for (q=p;q-> next!=p;q=q-> next);
q-> next=p-> next;
free (p);
return (q);
}
Print(LNode *p,int m)/*输出函数*/
{
int i;
printf ( "出队编号:\n ");
while (p-> next!=p)
{
for (i=1;i <=m;i++)
p=p-> next;
printf ( "%d ",p-> data);
p=GetNode(p);
}
printf( "%d\n ",p-> data);
return 0;
}
------解决方案--------------------
return (q);//这个是不能返回堆指针的
-------------------------------------
只要不是在函数体内用malloc分配的内存，就能返回，否则才需要双指针
题目:n 个人围成一圈, 并依次编号1～n，。从编号为1 的人开始，按顺时针方向每隔一人选出一个，
剩下的人重新围成一圈，如此循环直到剩下两人，这剩下的两人就是幸运儿。如果你想成为最后两个
幸运儿，请问开始时应该站在什么位置？（设3 <=n <=50）
我的想法,主要算法 ,没有经过调试
struct Tnode
{
int pos;//位置
Tnode *next;
}Tnode *head;
Tnode *p=head;
int count;//人的个数
...
while(count!=2)//最后留下的2个人
{
if(*p-> next-> next==NULL) //判断从下一个循环是踢第一个人,还是跳一个人,踢下一个
*p=head; //设置下循环踢人的位置
else
*p=head-> next;
for( ;*p-> next!=NULL||*p-> next-> next!=NULL;*p=*p-> next-> next)
{
DelNode(p); //删除当前节点
count--; //人数减1
}
}
count> > head.pos> > head-> next.pos;//输出
因为要记录人的幸运位置 所以我觉得用链表简单些,用数组应该也行,但是我不知道如何处理数组中让元素踢出数组.
大家有什么好想法 来说说啊~
------解决方案--------------------
/*约瑟夫环*/
#include <stdlib.h>
#include <stdio.h>
typedef struct node
{
int data;
struct node *next;
}LNode;
main()
{
LNode* Create(int,int);
LNode* GetNode(LNode *);
int Print(LNode *,int);
LNode *p;
int n,k,m;
do
{
printf ( "输入总人数 ");
scanf ( "%d ",&n);
}
while (n <=0);
do
{
printf ( "输入开始人的序号(1~%d) ",n);
scanf ( "%d ",&k);
}
while (k <=0 || k> n);
do
{
printf ( "输入间隔数字 ");
scanf ( "%d ",&m);
}
while(m <=0);
p=Create(n,k);
Print(p,m);
return 0;
}；
LNode* Create(int n,int k)/*创建循环链表*/
{
int start=k-1;
LNode *s,*p,*L=0,*t;
if (start==0) start=n;
while (n!=0)
{
s=(LNode *)malloc(sizeof(LNode));
if (L==0) p=s;
if (n==start) t=s;
s-> data=n;
s-> next=L;
L=s;
n--;
}
p-> next=L;
return t;
}
LNode* GetNode(LNode *p)/*出队函数*/
{
LNode *q;
for (q=p;q-> next!=p;q=q-> next);
q-> next=p-> next;
free (p);
return (q);
}
Print(LNode *p,int m)/*输出函数*/
{
int i;
printf ( "出队编号:\n ");
while (p-> next!=p)
{
for (i=1;i <=m;i++)
p=p-> next;
printf ( "%d ",p-> data);
p=GetNode(p);
}
printf( "%d\n ",p-> data);
return 0;
}
------解决方案--------------------
return (q);//这个是不能返回堆指针的
-------------------------------------
只要不是在函数体内用malloc分配的内存，就能返回，否则才需要双指针