当前位置: 代码迷 >> C语言 >> [求助] C程序的约瑟夫问题,编译成功,运行不成功
  详细解决方案

[求助] C程序的约瑟夫问题,编译成功,运行不成功

热度:246   发布时间:2007-03-15 15:21:27.0
[求助] C程序的约瑟夫问题,编译成功,运行不成功

问题:有一组人围成一个圈,分别编号(如1,2,3...),设定一个数K,从编号为K的人开始报数,报到M的出列,然后M的下一位从1开始重新报数,报到M的人出列,直到所有的人全出列,记录出列人的编号.
思路:先构建一个循环链表,再用删除的方法一个一个除去.
代码如下:
#include<malloc.h>
#define NULL 0
typedef struct Node /*定义一个结构体变量*/
{
int data;
struct Node *next;
}Lnode,*LinkList;

LinkList Creat_LinkList(int n) /*创建单循环链表的函数*/
{ /*10*/
int x;
LinkList L;
Lnode *s,*r;
L=r=NULL;
for(x=1;x<=n;x++)
{
s=(Lnode *)malloc(sizeof(Lnode));
s->data=x;
if(L==NULL)
L=s; /*20*/
else
r->next=s;
r=s;
}
if(r!=NULL)
r->next=L;
return L;
}

Lnode *Get_LinkList(LinkList L,Lnode *p)/*30*/ /*寻找指针函数*/
{
Lnode *p2;
p2=L;
while(p2->next!=p)
{
p2=p2->next;
}
return p2;
}
/*40*/
Lnode *Del_LinkList(Lnode *p,LinkList L) /*删除函数*/
{
Lnode *p1;
p1=Get_LinkList(L,p);
p1->next=p->next;
return p1+1;
}

main() /*主函数入口点*/
{ /*50*/
int k,n,m;
LinkList H;
Lnode *p,*w;
printf("Please insert n,k,m:");
scanf("%d%d%d",&n,&k,&m);
H=Creat_LinkList(n);
for(w=H+k;w+1!=w;)
{
printf("%d",w->data);
w=Del_LinkList(w,H);
w=w+m-1;
}
printf("%d",w->data);
getch();
}
编译成功,但运行后不是预期效果.
请高人帮忙看下.

搜索更多相关的解决方案: 约瑟夫  链表  编译  Node  

----------------解决方案--------------------------------------------------------
看了一下,觉得LS的有点复杂,自己写了个(从第M个开始,数到N的出列),依次输出出列人的编号,并输出最后留下的人的编号


#include "stdio.h"
#define N 3
#define M 0
main()
{int i,j,t,n,a[100],*p,k=1;
p=a;
printf("Enter n:");
scanf("%d",&n);
for(i=0;i<n;i++)
a[i]=i+1;
t=n-1;
do
{for(i=0;i<n;i++)
{if(*(p+i)==0)
for(j=0;j<n;j++)
if(*(p+j)) (*(p+j))--;
if(!(*(p+i)%N)&&*(p+i))
{ *(p+i)=0;
t--;
printf("%d: %d\n",k++,i+1);
}
}
for(i=0;i<n;i++)
if(*(p+i)) *(p+i)+=n;
}while(t);
for(i=0;i<n;i++)
if(*(p+i))
printf("the last number is %d\n",(i+1+M)>n?(i+1+M-n):(i+1+M));
}

[此贴子已经被作者于2007-3-15 16:39:10编辑过]


----------------解决方案--------------------------------------------------------
以下是引用PcrazyC在2007-3-15 16:38:36的发言:
看了一下,觉得LS的有点复杂,自己写了个(从第M个开始,数到N的出列),依次输出出列人的编号,并输出最后留下的人的编号


#include "stdio.h"
#define N 3
#define M 0
main()
{int i,j,t,n,a[100],*p,k=1;
p=a;
printf("Enter n:");
scanf("%d",&n);
for(i=0;i<n;i++)
a[i]=i+1;
t=n-1;
do
{for(i=0;i<n;i++)
{if(*(p+i)==0)
for(j=0;j<n;j++)
if(*(p+j)) (*(p+j))--;
if(!(*(p+i)%N)&&*(p+i))
{ *(p+i)=0;
t--;
printf("%d: %d\n",k++,i+1);
}
}
for(i=0;i<n;i++)
if(*(p+i)) *(p+i)+=n;
}while(t);
for(i=0;i<n;i++)
if(*(p+i))
printf("the last number is %d\n",(i+1+M)>n?(i+1+M-n):(i+1+M));
}

记得TC 100题中有很简洁

但用链表的话不能以此论之


----------------解决方案--------------------------------------------------------

没看过,发上来看看


----------------解决方案--------------------------------------------------------

是这样的吗?
#include "stdio.h"
main()
{
int i,k,n,m;
char *s,c;
struct str
{
char ch;
struct str *next;
}*pa,*pb,*pc;
printf("input some char:");
scanf("%s",s);
printf("input a nubmer k:");
scanf("%d",&k);
printf("input a number m:");
scanf("%d",&m);
n=strlen(s);
for(i=0;i<n;i++) /*把输入的一组字符放到链表里 */
{
pb=(struct str*)malloc(sizeof(struct str));
pb->ch=*(s+i);
if(i==0) pa=pc=pb;
else pc->next=pb;
pc=pb;
pc->next=0;
}
pc->next=pa;
for(i=1;i<k;i++) pa=pa->next; /*找到k的位置*/
while(pa->next!=pa)
{
if(m==1) /*删除1*/
{
c=pa->ch; /*自己的值给c*/
pa->ch=pa->next->ch; /*把下个的值给自己*/
}
else
{
for(i=1;i<m;i++) pa=pa->next; /*找到第m个的前一个*/
pb=pa->next; /*pb指向第m个*/
c=pb->ch; /*第m个的值给c*/
pa->next=pb->next; /*m的前一个的next指向m的下一个*/
pb->next=0;
free(pb);
}
pa=pa->next; /*pa指向m的下一个*/
printf("%c",c); /*输出c的值*/
}
printf("%c\n",pa->ch);
getch();
}


----------------解决方案--------------------------------------------------------
Lnode *Del_LinkList(Lnode *p,LinkList L) /*删除函数*/
{
Lnode *p1;
p1=Get_LinkList(L,p);
p1->next=p->next;
free(p);
return p1+1;
}

----------------解决方案--------------------------------------------------------
LinkList Creat_LinkList(int n) /*创建单循环链表的函数*/
{ /*10*/
int x;
LinkList L;
Lnode *s,*r;
...
return L;
}

你这是申明的 L 变量是auto 类型,
它的生命周期是 Creat_LinkList()这个函数的的开始到结束,
计算机会回收这段空间,
而返回L的时侯,L所指的空间可能被覆盖.
显然这样做是不可取的.

你可以这样做函数的头的处理:
LinkList Creat_LinkList(Lnode **Head)
{
....
}

调用时,Creat_LinkList(&H);
----------------解决方案--------------------------------------------------------

To lz:
关键是这段代码的思路有问题:
for(w=H+k;w+1!=w;)
{
printf("%d",w->data);
w=Del_LinkList(w,H);
w=w+m-1;
}
w=H+k,你大概是想令w指向从H开始的第k个结点吧,这样的表达不正确
在你的代码的基础上,我进行了如下修改(紫色粗体部分):

#include<malloc.h>
#define NULL 0
typedef struct Node /*定义一个结构体变量*/
{
int data;
struct Node *next;
}Lnode,*LinkList;

LinkList Creat_LinkList(int n) /*创建单循环链表的函数*/
{ /*10*/
int x;
LinkList L;
Lnode *s,*r;
L=r=NULL;
for(x=1;x<=n;x++)
{
s=(Lnode *)malloc(sizeof(Lnode));
s->data=x;
if(L==NULL)
L=s; /*20*/
else
r->next=s;
r=s;
}
if(r!=NULL)
r->next=L;
return L;
}

Lnode *Get_LinkList(LinkList L,int move)/*30*/ /*寻找指针函数*/
{
int i;
Lnode *p2;
p2=L;
for(i=1;i<=move;i++) p2=p2->next; /**/
return p2;
}

int Del_LinkList(LinkList *L,int m) /*40*/ /*删除函数*/
{
Lnode *p1,*p2;
int dt;
if ((*L)->next==(*L))
return 0;
p1=Get_LinkList(*L,m-1);
dt=p1->data;
p1->data=p1->next->data;
p2=p1->next;
p1->next=p2->next;
free(p2);
(*L)=p1;
return dt;
}


main() /*主函数入口点*/
{ /*50*/
int k,n,m,dt;
LinkList H;
Lnode *p;
printf("Please insert n,k,m:");
scanf("%d%d%d",&n,&k,&m);
H=Creat_LinkList(n);
p=Get_LinkList(H,k-1);
while(dt=Del_LinkList(&p,m))
printf("%d",dt);

printf("%d\n",p->data);
getch();
}

[此贴子已经被作者于2007-3-16 11:24:31编辑过]


----------------解决方案--------------------------------------------------------

PcrazyC的代码,m=1时进入死循环

iwfy的代码,(1)m=1时没有删除结点;(2)for(i=1;i<m;i++) pa=pa->next;这句恐怕多走了一步


----------------解决方案--------------------------------------------------------
题目:有n个人围成一圈,顺序排号。从第一个人开始报数(从1到3报数),凡报到3的人退出
   圈子,问最后留下的是原来第几号的那位。
1. 程序分析:
2.程序源代码:
#define nmax 50
main()
{
int i,k,m,n,num[nmax],*p;
printf("please input the total of numbers:");
scanf("%d",&n);
p=num;
for(i=0;i<n;i++)
  *(p+i)=i+1;
  i=0;
 k=0;
 m=0;
 while(m<n-1)
  {
  if(*(p+i)!=0) k++;
  if(k==3)
  {
*(p+i)=0;
  k=0;
 m++;
  }
i++;
if(i==n) i=0;
}
while(*p==0) p++;
printf("%d is left\n",*p);
}

----------------解决方案--------------------------------------------------------
  相关解决方案