查看:3226|回复：14
有n个人围城一圈，顺序排号。从第一个人开始报数（从1到3报数），凡是报到3的人全部退出圈子，试问：最后留下的是原来第几号的那位？
用代码实现？
还是脑际急转弯啊？
现在我还没有高明白它的大概意思，希望能得到指点。
原题：m个人围城一个圈，依次1，2报数...数到3的人退出圈子，下一个接着从1开始报数，依次进行下去，求最后留在圈子里的人原来的序号？
请教一下该怎么样用程序实现呢？复制内容到剪贴板代码:#include &stdio.h&
#include &malloc.h&
#define LEN sizeof(struct a)
int main(void)
typedef struct a
struct a *
DATA *head,*p1,*p2,*p0;
scanf(&%d&,&n);
for(i=1;i&=n;i++)
p1=p2=(DATA *)malloc(LEN);
head-&num=i;
head-&next=NULL;
p2=(DATA *)malloc(LEN);
p1-&next=p2;
p2-&num=i;
int k=1;int num=n;
while(num!=1)
p0-&next=p2;
printf(&%d\n&,p1-&num);
getchar();
搜索一下很多的复制内容到剪贴板代码:#include &stdio.h&
#define N& & 50 // 排队人数(可任意更改)
#define CAL& &3 //凡报3的人出列(可任意更改)
//下面是排队编号函数:从h 开始的n个人依次编号1到n
void& &stdline(int *h,int n)
for(i=1;i&n+1;i++) *(h+i-1)=i;
/*下面函数表示从指针h处开始的人数为boy个人排队，从1报数，每报到call的人出列*/
void outline(int *h,int boy,int call)
int *p, chu,
& && && && &&&/*说明:
& && && && & p& && &&&工作指针，表示从头依次指向每个元素，点名
& && && && & chu& && &计数器，记录出列的人数
& && && && & callnum 计数器，记录点名次序
& && && &&&*/
callnum=0;//各计数器清零
p=h;& && &//开始时，工作指针指向数组首
printf(&出列顺序是：\n&);
while(chu&boy)& &
& && && & if(*p!=0) callnum++; //每次加报数
& && && & if(callnum==call)& &&&//如果某一个人报到出列数call...
& && && & {
& && && && && &&&printf(&%5d&,*p); //打印编号，表示出列
& && && && &&&chu++;& && && && &//出列人数加1
& && && && && &if(chu==boy)//如果全部出列....
& && && && && && &&&{
& && && && && && && && &&&*h=*p;& & //把最后一个出列人的编号记入地址开始处
& && && && && && && && && &//结束
& && && && && && &&&}
& && && && & if(chu%10==0)printf(&\n&);//每输出10个换行
& && && && && &callnum=0; //出列后,重新报数
& && && && && &*p=0;& & //出列后,将其编号赋零,以示区别
& && && & }
& && && &p++; //工作指针移向下一个人,即下一个数组元素
& && && &if(p&h+boy-1)p=h;/*如果移到最后一个元素的后面,则让指向地址开头继续报数*/
void main()
int a[N]; //用数组模拟队列,每个元素代表一个人
stdline(a,N);//编号
outline(a,N,CAL);//计算并打印出列顺序
printf(&\n最后留下来的是 %d 号\n&,*a);/*在函数中,已经把最后一个人的编号写入了数组首地址处,
& && && && && && && && && && && && && && && && && && && & 这里输出就可以了*/
请百度 约瑟夫环。
补充一句，这也是个经典问题。
本帖最后由 yuzhibokaixi 于
12:55 编辑
谢谢了 ，仔细学习下
实习版主，我想弱弱的问下这个题目的意思是不是开始的1有可能变成后面的2或者3，不是固定的1？
引用:原帖由 mymirror 于
13:21 发表
实习版主，我想弱弱的问下这个题目的意思是不是开始的1有可能变成后面的2或者3，不是固定的1？ 就是说第一个人开始报数
第一个人：1
第二个人：2
第三个人：3
为3那么退出
第四个人（原来 队列的第4人）：重新报：1
第六人：3：退出
约瑟夫环问题，很经典，基本解决方案是用循环链表。百度百科讲的很详细
闲着无聊用C++实现的；不过写的很烂复制内容到剪贴板代码:#include&iostream&
struct node
& & & & node*
int main()
& & & & int N;
& & & & cout&&&please enter the total of people:&;
& & & & cin&&N;
& & & & cout&&
& & & & cout&&&please enter the number of begining:&;
& & & & cin&&k;
& & & & cout&&
& & & & cout&&&please enter the number looking for:&;
& & & & cin&&
& & & & cout&&
& & & & node* list=NULL,*p=NULL,*r=NULL;
& & & & for(int i=0;i&N;i++)
& & & & & & & & p=new node();
& & & & & & & & p-&data=i+1;
& & & & & & & & if(list==NULL)list=p;
& & & & & & & & else r-&next=p;
& & & & & & & & r=p;
& & & & for(int i=0;i&k;i++)
& & & & & & & & r=p;
& & & & & & & & p=p-&
& & & & cout&&&the sort of out:&&&
while(p-&next!=p)
for(int i=0;i&iout-1;i++)
& & & & r=p;
& & & & p=p-&
cout&&p-&data&&' ';
r-&next=p-&
cout&&&the last number is: &&&p-&data&&
约瑟夫环么？
大家都挺感兴趣啊，
& &版主要不要来个每日ACM一题啊·
引用:原帖由 Tyrante 于
11:13 发表
约瑟夫环么？
大家都挺感兴趣啊，
& &版主要不要来个每日ACM一题啊· 呵呵， 我那里有一个
你有兴趣的话，欢迎回答
中级工程师
嘿嘿,谢谢你对C/C++版块的支持哈,ACM的话对算法的要求比较高,我们现在主要是为初学者服务,不过以后还是可以考虑这么干的,多谢你的建议＾＾引用:原帖由 Tyrante 于
11:13 发表 约瑟夫环么？ 大家都挺感兴趣啊，& &版主要不要来个每日ACM一题啊·
The best of man is like water
Which benefits all things, and does not contend with them
Which flows in places that others disdain
Where it is in harmony with the Way
引用:原帖由 Tyrante 于
11:13 发表
约瑟夫环么？
大家都挺感兴趣啊，
& &版主要不要来个每日ACM一题啊· 呵呵，
看你回帖中提到过ACM几次（我对ACM不怎么了解）；
如果你感兴趣的话；
可以发到论坛一起讨论。（只要对学习有帮助就可以，会的交流更好的方法，不会的可以讨论弄懂嘛,不过最好一次一个，解决一个再一个，多了。。。。）
本帖最后由 月夜幻影 于
13:16 编辑用C语言写约瑟夫环-帮我改一下程序_百度知道实验三：用单循环链表实现约瑟夫环问题
实验三：用单循环链表实现约瑟夫环问题（2学时）
本次实验的主要目的在于帮助学生熟练掌握线性表的基本操作在链式存储结构上的实现。主要应用单循环链表来实现存储。
约瑟夫环问题描述：n个人围成一圈报数（每个人用编号1—n表示即可），从1号开始，每数到m出圈一个，然后再从下一个开始重新报数，直至所有人全部出圈为止。试设计一个程序求出圈顺序，要求n、m由键盘输入。
利用单向循环链表实现此过程，按照出圈的顺序输出各人的编号。
n=10,m=3,正确的顺序为3,6,9,2,7,1,8,5,10,4。
n=10,m=1,正确的顺序为1,2,3,4,5,6,7,8,9,10。
此题用的单循环链表中不需要“头结点”，注意空表和非空表的条件，出圈即删除结点，最后链表中无数据
#include&stdio.h&
#include&string.h&
#include&stdlib.h&
typedef int E
typedef struct LNode
&struct LNode *
typedef struct
void build(Link *l,int n,int *flag);
&int i,flag,n,m;
&Jiedian p,q,s;
& clrscr();
& puts("input the length");
& scanf("%d",&n);
build(&l,n,&flag);
& if(flag==0)
puts("please try again");
& puts("input the data of xunhuan");
& scanf("%d",&m);
& clrscr();
& printf("the length:%d\n",n);
& printf("the xunhuan data:%d\n",m);
& printf("the turn:");
& while(l.len&0)
for(i=1;i&=m;i++)
printf("%d ",p-&d);
while(s-&next!=p)
s-&next=q;
& l.h=NULL;
& gotoxy(25,20);
& puts("Try again---------y");
& b=getch();
& if(b!='y')
void build(Link *l,int n,int *flag)
&Jiedian p,q;
&l-&len=n;
&for(i=1;i&=n;i++)
p=(Jiedian)malloc(sizeof(struct LNode));
&& if(p==NULL)
&& p-&d=i;
&& if(i==1)
q-&next=p;
q-&next=l-&h;
& *flag=1;
#include &stdlib.h&
#include &stdio.h&
#include&conio.h&
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef char ElemT
typedef int S
typedef struct node
struct node *
LNode* Create(int,int);
LNode* GetNode(LNode *);
int Print(LNode *,int);
int n,k,m;
printf ("输入总人数");
scanf ("%d",&n);
while (n&=0);
printf ("输入开始人的序号(1~%d)",n);
scanf ("%d",&k);
while (k&=0 || k&n);
printf ("输入间隔数字");
scanf ("%d",&m);
while(m&=0);
p=Create(n,k);
Print(p,m);
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;
p-&next=L;
LNode* GetNode(LNode *p)
(q=p;q-&next!=p;q=q-&next);
q-&next=p-&
return (q);
Print(LNode *p,int m)
printf ("出队编号:\n");
while (p-&next!=p)
for (i=1;i&=m;i++)
printf ("%d ",p-&data);
p=GetNode(p);
printf("%d\n",p-&data);
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。求c语言用循环链表编写约瑟夫环代码（速度求解）！！！_百度知道用数据结构的单循环链表写的约瑟夫环（C语言），哪错了？_百度知道