免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 3597 | 回复: 9

[算法] 约瑟夫问题 [复制链接]

论坛徽章:
0
发表于 2010-12-13 21:57 |显示全部楼层
20可用积分
如题:设编号为1,2,3,……,n 的n(n>0)个人按顺时针方向围坐一圈,每个人持有一个正整数密
码。开始时任选一个正整数做为报数上限m,从第一个人开始顺时针方向自1 起顺序报数,报到m
是停止报数,报m 的人出列,将他的密码作为新的m 值,从他的下一个人开始重新从1 报数。如
此下去,直到所有人全部出列为止。令n 最大值取30。要求设计一个程序模拟此过程,求出出列编
号序列。


下面是我找的算法程序,只不过不能实现n的最大值取30,请帮忙改下程序,最好写下怎么改。而且我需要知道这段代码运用了什么算法,
牵扯到哪些知识,因为要答辩的,最好还能在每段代码旁边写上备注。 谢谢了~~

#include<stdio.h>
#include<stdlib.h>
#define FALSE 0
#define TRUE 1
struct node
{
int number;
int pass_m;
struct node *next;
}*head,*p1,*p2,*temp;
int main()
{
int m,i,n;
loop:printf("Input the number of students:");
scanf("%d",&n);
if(n<1)
{
printf("The \"n\" is wrong number:!Please input again!\n");
goto loop;
}
head=(struct node *)malloc(sizeof(struct node));
if(head==NULL)
return(FALSE);
loop1:printf("Input the 1th student's password: ");
scanf("%d",&head->pass_m);
if(head->pass_m<1)
{
printf("The \"password\" is wrong number:!Please input again!\n");
goto loop1;
}
head->number=1;
head->next=NULL;
p1=head;
for(i=1;i<n;i++)
{
p2=(struct node *)malloc(sizeof(struct node));
if(head==NULL)
return(FALSE);
loop2:printf("Input the %dth student's password: ",i+1);
scanf("%d",&p2->pass_m);
if(p2->pass_m<1)
{
printf("The \"password\" is wrong number:!Please input again!\n");
goto loop2;
}
p2->number=i+1;
p1->next=p2;
p2->next=NULL;
p1=p2;
}
p1->next=head;
p2=head;
p1=p2->next;
printf("Input the \"m\":");
scanf("%d",&m);
printf("The score is: ");
while(n>0)
{
if(m==2)
{
m=p1->pass_m;
printf("%d,",p1->number);
temp=p1;
p2->next=p1->next;
p2=p1->next;
p1=p2->next;
free(temp);
n--;
}
else if(m==1)
{
m=p2->pass_m;
printf("%d,",p2->number);
temp=p2;
p2=p1;
p1=p2->next;
free(temp);
n--;
}
else
{
while(m>2)
{
p2=p1;
p1=p1->next;
m--;
}
m=p1->pass_m;
p2->next=p1->next;
printf("%d,",p1->number);
temp=p1;
p2=p1->next;
p1=p2->next;
free(temp);
n--;
}
}
printf("\b.");
getchar();
return(TRUE);
}

论坛徽章:
0
发表于 2010-12-14 09:53 |显示全部楼层
这个和约瑟夫问题好像有点差别, 报m的值不是固定的,
下面的是约瑟夫问题的,你看着调整一下for中m的值就可以了。
#include<stdio.h>
#include<malloc.h>
struct node
{
int data;
struct node * link;
};
struct node * Create(int N)
{
int i=1,j;
struct node *List;
struct node *p,*q;
List=(struct node *)malloc(N*sizeof(struct node *));
List->data=i;
q=List;
for(j=1;j<N;j++)
{
  p=(struct node*)malloc(sizeof(struct node*));
  p->data=++i;
  q->link=p;
  q=p;
}
q->link=List;
//printf("%d\n",List->data);
return List;
}
int Run(struct node * List,int m)
{
int j;
struct node *p,*q;
p=List;
while(p->link!=p)
{
q=p;
for(j=1;j<m;j++)
{
  q=p;
  p=p->link;
}
//printf("%d\n",p->data);
p=p->link;

q->link=p;
}
return p->data;
}
int main()
{
int N,m;
int number;
scanf("%d %d",&N,&m);
struct node *List;
List=Create(N);
number=Run(List,m);
printf("%d\n",number);
    return 0;
}

论坛徽章:
0
发表于 2010-12-14 09:54 |显示全部楼层
这个和约瑟夫问题好像有点差别, 报m的值不是固定的,
下面的是约瑟夫问题的,你看着调整一下for中m的值就可以了。
#include<stdio.h>
#include<malloc.h>
struct node
{
int data;
struct node * link;
};
struct node * Create(int N)
{
int i=1,j;
struct node *List;
struct node *p,*q;
List=(struct node *)malloc(N*sizeof(struct node *));
List->data=i;
q=List;
for(j=1;j<N;j++)
{
  p=(struct node*)malloc(sizeof(struct node*));
  p->data=++i;
  q->link=p;
  q=p;
}
q->link=List;
//printf("%d\n",List->data);
return List;
}
int Run(struct node * List,int m)
{
int j;
struct node *p,*q;
p=List;
while(p->link!=p)
{
q=p;
for(j=1;j<m;j++)
{
  q=p;
  p=p->link;
}
//printf("%d\n",p->data);
p=p->link;

q->link=p;
}
return p->data;
}
int main()
{
int N,m;
int number;
scanf("%d %d",&N,&m);
struct node *List;
List=Create(N);
number=Run(List,m);
printf("%d\n",number);
    return 0;
}

论坛徽章:
0
发表于 2010-12-14 10:25 |显示全部楼层
#define N 100
int yuesefu1(int data[],int sum,int k)
{
   int i=0,j=0,count=0;
   while(count
   {
     if(data[i]!=0)/*当前人在圈子里*/
         j++;
     if(j==k)/*若该人应该退出圈子*/
     {
         data[i]=0;/*0表示不在圈子里*/
         count++;/*退出的人数加1*/
         j=0;/*重新数数*/
     }
     i++;/*判断下一个人*/
     if(i==sum)/*围成一圈*/
         i=0;
   }
   for(i=0;i
      if(data[i]!=0)
          return data[i];/*返回最后一个人的编号*/
}

void main()
{
   int data[N];
   int i,j,total,k;
   printf("\nPlease input the number of every people.\n");
   for(i=0;i
   {
      int input;
      scanf("%d",&input);
      if(input==0)
           break;/*0表示输入结束*/
      for(j=0;j
          if(data[j]==input)
              break;
      if(j>=i&&input>0)/*无重复,记录编号,继续输入*/
      {
          data[i]=input;
          i++;
      }
      else
           printf("\nData error.Re-input:");
   }
   total=i;
   printf("\nYou have input:\n");
   for(i=0;i
   {
     if(i%10==0)
            printf("\n");
     printf("%4d",data[i]);
   }
   printf("\nPlease input a number to count:");
   scanf("%d",&k);
   printf("\nThe last one's number is %d",yuesefu1(data,total,k));
}

论坛徽章:
0
发表于 2010-12-14 10:27 |显示全部楼层
4楼程序有错啊

论坛徽章:
0
发表于 2010-12-14 10:49 |显示全部楼层
回复 3# yikaikai


    您给的程序 运行结果不是我想要的啊~  麻烦您能再帮下忙么  谢谢了

论坛徽章:
0
发表于 2010-12-14 11:14 |显示全部楼层
  1. 我给你送饭,你不张口,那我只好强灌, 拿分来!
  2. #include<stdio.h>
  3. #include<malloc.h>
  4. struct node
  5. {
  6. int data;
  7. struct node * link;
  8. };
  9. struct node * Create(int N)
  10. {
  11. int i=1,j;
  12. struct node *List;
  13. struct node *p,*q;
  14. List=(struct node *)malloc(N*sizeof(struct node *));
  15. List->data=i;
  16. q=List;
  17. for(j=1;j<N;j++)
  18. {
  19.   p=(struct node*)malloc(sizeof(struct node*));
  20.   p->data=++i;
  21.   q->link=p;
  22.   q=p;
  23. }
  24. q->link=List;
  25. //printf("%d\n",List->data);
  26. return List;
  27. }
  28. int Run(struct node * List,int m)
  29. {
  30. int j;
  31. struct node *p,*q;
  32. p=List;
  33. while(p->link!=p)
  34. {
  35. q=p;
  36. for(j=1;j<m;j++)
  37. {
  38.   q=p;
  39.   p=p->link;
  40. }
  41. printf("%d\n",p->data);
  42. m = p->data; //这里修改m的值
  43. p=p->link;

  44. q->link=p;
  45. }
  46. return p->data;
  47. }
  48. int main()
  49. {
  50. int N,m;
  51. int number;
  52. scanf("%d %d",&N,&m);
  53. struct node *List;
  54. List=Create(N);
  55. number=Run(List,m);
  56. printf("%d\n",number);
  57.     return 0;
  58. }
复制代码

论坛徽章:
0
发表于 2010-12-14 11:19 |显示全部楼层
回复 7# yikaikai


    谢谢您帮我  不过这个题目是  每人手里都有一个密码  比如4号的密码是3    第一轮4下去了,下一轮从5开始查,查4的密码个人,也就是3个,8下去,然后从9开始查8的密码个

论坛徽章:
0
发表于 2010-12-14 11:32 |显示全部楼层
每个人的编号, 可以看成是手中的密码, 如果需要别的,修改结构体,再给赋值

论坛徽章:
0
发表于 2010-12-14 11:37 |显示全部楼层
回复 9# yikaikai


    谢谢~

   我对C不怎么懂  我的那段也是网上找的。学校需要答辩,所以必须要讲出来
  而且时间很紧,明天下午,我想请您帮我分析下这个程序的思路和备注
  而且 你刚才说该值什么的 我不知道从哪改~   这个我真不会
  我想请您把按照题目要求帮我改下和备注下  麻烦您了
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP