约瑟夫问题 1128

2023-10-14 16:59

文章标签 问题约瑟夫 1128

本文主要是介绍约瑟夫问题 1128，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述:

已知n个人（编号分别为1、2、3，……、n）围坐在一张圆桌周围，从编号为1的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列，依次规律重复下去，直到圆桌周围的人全部出列

输入描述：

一行：人数n和间隔数m

输出描述：

出列顺序，每个编号之间用一个空格分开

样例输入:

9 5

样例输出:

5 1 7 4 3 6 9 2 8

自己做过类似的课程设计

  1 //4、约瑟夫环 
  2 //问题描述：
  3 //编号为1，2… n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。
  4 //一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数，
  5 //报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1报数，
  6 //如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序。 
  7 //基本要求：
  8 //（1）利用单循环链表作为存储结构模拟此过程；
  9 //（2）键盘输入总人数、初始报数上限值m及各人密码；
 10 //（3）按照出列顺序输出各人的编号
 11  
 12 #include<stdio.h>
 13 #include<stdlib.h>
 14 #define N 100
 15 typedef struct LNode
 16 {
 17     int data;
 18     struct LNode *next;
 19 
 20 }LNode,*LinkList;
 21 
 22 LinkList CreateNode(int n)
 23 {
 24     LinkList LNode;
 25     LNode=(LinkList)malloc(sizeof(LNode));
 26     LNode->data=n;
 27     LNode->next=NULL;
 28     return LNode;
 29 }
 30 
 31 void CreateList(LinkList &pH, int n)
 32 {
 33     int k;
 34     LinkList p, t;
 35     p=CreateNode(1);
 36     t=p; 
 37     pH=p; 
 38     t->next=pH; 
 39     for(k=2;k<=n;k++)
 40     {    
 41         p=CreateNode(k);
 42         p->next=t->next;
 43         t->next=p;
 44         t=p;
 45     }
 46 }
 47 
 48 void PrintList(LinkList pH, int Ld,int Lcode[])
 49 {
 50     LinkList p, temp,c;
 51     p=pH;
 52     int i,count=1;
 53     while(p->next!=p)
 54     {
 55         for(i=1;i<Ld;i++)
 56         {
 57             temp=p;
 58             p=p->next;
 59         }
 60         temp->next=p->next;
 61         Ld=Lcode[p->data];
 62         c=p;
 63         printf("第%d个出列的小孩的编号为：%d\n",count,p->data);
 64         free(c);
 65         count++;
 66         p=temp->next;
 67         
 68     }
 69     printf("第%d个出列的小孩的编号为：%d\n",count,p->data);
 70     free(p);
 71     pH=NULL;
 72 }
 73 
 74 int main()
 75 {
 76     int n,m,i;
 77     int code[N];
 78     LinkList h=NULL;
 79     printf("请输入小孩的个数n(不超过100)：\n");
 80     scanf("%d",&n);
 81     while(n>N||n<=0){
 82         printf("输入的数据有误，请重新输入\n");
 83         printf("请输入小孩的个数n(不超过100)：\n");
 84         scanf("%d",&n);
 85     }
 86     printf("---------------------------------\n");
 87     printf("请输入每个小孩的密码:\n");
 88     for(i=1;i<=n;i++)
 89     {
 90         printf("编号为%d的小孩: ",i); 
 91         scanf("%d",&code[i]);
 92     }
 93     printf("---------------------------------\n");
 94     printf("请输入第一次报数数目m：\n");
 95     scanf("%d",&m);
 96     CreateList(h,n);
 97     printf("\n");
 98     printf("---------------------------------\n");
 99     printf("运行结果为：\n");
100     PrintList(h,m,code);
101     return 0;
102 }

约瑟夫环

 1 #include<iostream>
 2 #include<stdlib.h>
 3 using namespace std;
 4 typedef struct LNode
 5 {
 6     int data;
 7     struct LNode *next;
 8 
 9 }LNode,*LinkList;
10 
11 LinkList CreateNode(int n)
12 {
13     LinkList LNode;
14     LNode=(LinkList)malloc(sizeof(LNode));
15     LNode->data=n;
16     LNode->next=NULL;
17     return LNode;
18 }
19 
20 void CreateList(LinkList &pH, int n)
21 {
22     int k;
23     LinkList p, t;
24     p=CreateNode(1);
25     t=p; 
26     pH=p; 
27     t->next=pH; 
28     for(k=2;k<=n;k++)
29     {    
30         p=CreateNode(k);
31         p->next=t->next;
32         t->next=p;
33         t=p;
34     }
35 }
36 
37 void PrintList(LinkList pH, int Ld)
38 {
39     LinkList p, temp,c;
40     p=pH;
41     int i;
42     while(p->next!=p)
43     {
44         for(i=1;i<Ld;i++)
45         {
46             temp=p;
47             p=p->next;
48         }
49         temp->next=p->next;
50         c=p;
51         //cout<<p->data<<' ';
52         free(c);
53         p=temp->next;
54         
55     }
56     cout<<p->data<<endl;
57     free(p);
58     pH=NULL;
59 }
60 
61 int main(){
62     int n,m;
63     while(cin>>n>>m){
64         LinkList h=NULL;
65         CreateList(h,n);
66         PrintList(h,m);
67     }
68     return 0;
69 }