约瑟夫环输出实际人名

一、实验目的1. 理解并掌握约瑟夫环问题的基本概念和解决方法。

2. 熟悉链表数据结构及其操作，提高编程能力。

3. 通过实验加深对数据结构和算法的理解，提高解决实际问题的能力。

二、实验原理约瑟夫环问题是一个经典的数学问题，描述了N个人围成一圈，从某个人开始报数，报到M的人出列，然后从下一个人开始重新报数，如此循环，直到所有人都出列为止。

本实验通过实现单向循环链表来模拟这个过程。

三、实验内容1. 单向循环链表实现：- 定义单向循环链表的节点结构体，包含数据域和指针域。

- 实现创建单向循环链表的函数，从键盘输入N和M，生成包含N个节点的单向循环链表。

- 实现遍历单向循环链表的函数，用于输出链表中的节点信息。

2. 约瑟夫环报数：- 实现报数函数，从链表的第一个人开始报数，报到M的人出列。

- 实现删除节点的函数，将出列的人从链表中删除。

- 实现重新开始报数的函数，从下一个人开始重新报数。

3. 输出结果：- 实现输出出列顺序的函数，将出列的人的编号按顺序输出。

四、实验步骤1. 定义单向循环链表的节点结构体：```ctypedef struct Node {int data; // 数据域struct Node next; // 指针域} Node;```2. 实现创建单向循环链表的函数：```cNode createList(int n) {Node head = NULL;Node tail = NULL;Node tmp = NULL;for (int i = 1; i <= n; i++) {tmp = (Node)malloc(sizeof(Node)); tmp->data = i;tmp->next = NULL;if (head == NULL) {head = tmp;tail = tmp;} else {tail->next = tmp;tail = tmp;}}tail->next = head; // 形成循环链表return tail; // 返回尾节点}```3. 实现遍历单向循环链表的函数：```cvoid printList(Node tail) {Node p = tail->next; // 从头节点开始遍历while (p != tail) {printf("%d ", p->data);p = p->next;}printf("\n");}```4. 实现报数函数：```cvoid josephus(int n, int m) {Node tail = createList(n); // 创建单向循环链表Node p = tail->next; // 从头节点开始报数Node q = NULL; // 记录出列节点的前一个节点 for (int i = 1; i <= n; i++) {for (int j = 1; j < m; j++) {q = p;p = p->next;}q->next = p->next; // 删除出列节点printf("%d ", p->data); // 输出出列节点编号free(p); // 释放出列节点内存p = q->next; // 从下一个人开始报数}printf("\n");}```5. 实现输出出列顺序的函数：```cvoid printOutSequence(int n, int m) {printf("出列顺序为：\n");josephus(n, m);}```五、实验结果与分析1. 实验结果：- 当N=7，M=3时，出列顺序为：6 1 4 7 2 3 5。

程序源代码：#include <stdio.h>#include <malloc.h>#include<conio.h>#include <stdlib.h>#include<ctime>#define NULL 0typedef struct Node{int m;//密码int n;//序号struct Node *next;}Node,*Linklist;Linklist create(int z) //生成循环单链表并返回,z为总人数{int i,mm;Linklist H,r,s;H=NULL;printf("请按顺序依次为每个人添加密码：");for(i=1;i<=z;i++){printf("\ninput cipher=");scanf("%d",&mm);s=(Linklist)malloc(sizeof(Node));s->n=i;s->m=mm;printf("%d号的密码%d",i,s->m);if(H==NULL)//从链表的第一个节点插入{H=s;r=H;}else//链表的其余节点插入{r->next=s;r=s;//r后移}//for结束r->next=H;/*生成循环单链表*/return H;}void search(Linklist H,int m0,int z)//用循环链表实现报数问题{int count=1;//count为累计报数人数计数器int num=0;//num为标记出列人数计数器Linklist pre,p;p=H;printf("出列的顺序为:");while(num<z){do{count++;pre=p;p=p->next;}while(count<m0);｛pre->next=p->next;printf("%d ",p->n);m0=p->m;free(p);p=pre->next;count=1;num++;}//while结束}void clean(){int system(const char *string);int inquiry;printf("请问需要清除上一次操作记录吗（1.清屏/2.不清屏）...?\n"); scanf("%d",&inquiry);if(inquiry ==1)system("cls");}void text(){int m0,z,i, choose,k=1; //k用来阻止第一次进入程序清屏操作Linklist H;bool chooseFlag=false;while(1){if(k!=1)clean();k++;while(!chooseFlag){printf(" ……………………欢迎进入约瑟夫环问题系统…………………… \n"); printf( "* 1.输入约瑟夫环数据 * \n"); printf(" * 2.什么是约瑟夫环 * \n"); printf(" * 3.退出系统 * \n"); printf("........................................................ \n"); printf("请输入相应的数字进行选择: ");scanf("%d",&choose);for(i=1;i<=4;i++){if(choose==i) { chooseFlag=true; break;}else chooseFlag=false;}if(!chooseFlag) printf("Error Input!\n");} //end while(!chooseFlag)if(choose==1) //if 开始{printf("Input how many people in it:");//z为总人数scanf("%d",&z);if(z<=30){H=create(z);//函数调用printf("\nInput the start code m0=");scanf("%d",&m0);search(H,m0,z);printf("\n\n\n");}else{printf("超过最大输入人数\n");break;}}else if(choose==2){printf("\n约瑟夫环问题：设有n个人，其编号分别为1，2，3，…，n，安装编号顺序顺时针围坐一圈。

#include"stdio.h" //预处理命令打开输入输出头文件#include"stdlib.h" //预处理命令打开标准库头文件#define MAXPASSWORDVALUE 20 //最大的密码的上线值#define MAXPERSONNUMBER 30 //最大人数#define MAXFIRSTCOUNTVALUE 20 //第一个M最大的上线值//#define MAXPASSWORD 10 //最大的密码上线typedef struct Node //定义人这个结构体{int data;//人的名字，即位置1.2.3...int password;//人的密码struct Node *next;//移动的指针}Node, *LinkList;//结构体指针变量，用于使用结构体中的属性//函数的声明void CreatLinkList(LinkList *);//声明建立单链表的函数void InitLinkList(LinkList *,int );//声明初始化单链表的函数int GetPassword();//获得每人的密码的函数int GetPersonNumber();//获得最大人数的函数//int GetPersonNumber();//int GetFirstCountValue();//获得初始的M值void GetOutputOrder(LinkList* , int, int, int* );//遍历单链表的函数void printResult(int * ,int );//输出遍历结果的函数//对以上各函数的定义//函数1构建链表void CreatLinkList(LinkList *L)//函数->>构建单链表{(*L) = (LinkList)malloc(sizeof(Node));if ((*L) == NULL){printf("memory allocation failed, goodbye");exit(1);}}//函数2初始化链表void InitLinkList(LinkList *L, int personNumber)//初始化单链表Node *p, *q;int i ;p = (*L);p->data = 1;p->password = GetPassword();for (i = 2; i <= personNumber; i++){q = (LinkList)malloc(sizeof(Node));if (q == NULL){printf("memory allocation failed, goodbye");exit(1);}q->password = GetPassword();q->data = i;p->next = q;p = q;}p->next = (*L);}//函数3为每个人输入一个密码int GetPassword()//给每个人赋密码{//定义变量int password;static int count = 1;//------------------------------------printf("\n请输入第%d的密码:",count);//可自加的提示文字scanf("%d",&password);//输入第1-n个人的密码while (password > MAXPASSWORDVALUE || password < 0)//当输入的密码大于最大密码的上限或是小于零的时候{printf("您输入的数字无效，请输入在0到%d的整数:",MAXPASSWORDVALUE);//提示请输入0-n的整数scanf("%d",&password);//重新输入密码}printf("第%d个人的密码为%d",count,password);//每输入后显示这个人的密count++;//计步器return password;//每循环一次返回一个密码值}//函数4获取玩游戏的人数int GetPersonNumber()//确定需要处理的人数{//定义变量int personNumber;//------------------------------------------------printf("请输入需要输入人的数目:");//提示语言scanf("%d",&personNumber);//输入参加游戏的人数while (personNumber > MAXPERSONNUMBER || personNumber < 0)//当人数大于最大人数或是小于0的时候{printf("\n你输入的数字无效,请输入在0到%d的整数",MAXPERSONNUMBER);//提示你要输入从0到最大人数个人数scanf("%d",&personNumber);//重新输入参加游戏的人数}printf("最终确定的人数为%d\n",personNumber);//输入完显示最终完游戏的人数return personNumber;//将人数返回到主函数}//函数5确定玩游戏开始时的M值int GetFirstCountValue()//确定开始的上限值{//定义变量int firstCountValue;//-----------------------------------------------printf("请输入初始的上限值");//提示语scanf("%d",&firstCountValue);//让你输入M最初始的值while (firstCountValue > MAXFIRSTCOUNTVALUE || firstCountValue < 2)//当输入的值大于M初始值上限或是小于2{printf("\n你输入的数字无效,请输入在2到%d的整数",MAXFIRSTCOUNTVALUE);//提示你输入2-M上限大小的数scanf("%d",&firstCountValue);//重新输入M的初始值printf("最终的上限值为%d",firstCountValue);//显示你输入的M的初始值return firstCountValue;//吧M的初始值返回到值函数}//函数6实现游戏过程void GetOutputOrder(LinkList *L, int personNumber, int reportValue, int array[MAXPERSONNUMBER])//遍历链表函数的定义{//变量的定义Node *p, *q;int count = 1, i = 0;p = (*L);//---------------------------------while (personNumber)//当人数值返回的为真时（没有用的，一定为真）{while (count != reportValue)//当M得初始值不为1时{//一个一个输出（游戏过程）q = p;p = p->next;count++;}array[i++] = p ->data;reportValue = p->password;q->next = p->next;free(p);p = q->next;count = 1;personNumber--;}}//函数7遍历单链表void printResult(int array[],int personNumer)//输出结果{//定义变量int i;//--------------------------------------printf("\n出队的顺序为:");//提示语for(i = 0; i < personNumer; i++)//循环输出链表内的值{printf("%-3d",array[i]);}printf("\n");}//函数8...主函数!!!!!!!int main(void)//主函数定义{//变量的定义LinkList L;int personNumber, reportValue;int array[MAXPERSONNUMBER];//------------------------------------------------personNumber = GetPersonNumber();//将函数4获取参加游戏的人数的函数的返回值赋到变量内reportValue = GetFirstCountValue();//将函数5获取M的初始值函数的返回值赋到变量内CreatLinkList(&L);//调用函数1建立一个单链表InitLinkList(&L, personNumber);//调用函数2初始化单链表GetOutputOrder(&L, personNumber, reportValue, array);//调用函数6实现游戏过程printResult(array, personNumber);//调用函数7遍历单链表system("pause");//结束return 0;}。

约瑟夫问题（循环链表）问题描述：约瑟夫是犹太军队的⼀个将军，在反抗罗马的起义中，他所率领的军队被击溃，只剩下残余的部队40余⼈，他们都是宁死不屈的⼈，所以不愿投降做叛徒。

⼀群⼈表决说要死，所以⽤⼀种策略来先后杀死所有⼈。

于是约瑟夫建议：每次由其他两⼈⼀起杀死⼀个⼈，⽽被杀的⼈的先后顺序是由抽签决定的，约瑟夫有预谋地抽到了最后⼀签，在杀了除了他和剩余那个⼈之外的最后⼀⼈，他劝服了另外⼀个没死的⼈投降了罗马。

1//利⽤循环链表模拟约瑟夫问题，把41个⼈⾃杀的顺序编号输出2 #include<iostream>3 #include<malloc.h>4 #include<string.h>5 #include<stdlib.h>6 #include<stdio.h>7using namespace std;89 typedef struct Node{10int data;11struct Node *next;12 }Node,*LinkList;1314void InitList(LinkList &L){15 L = (LinkList)malloc(sizeof(Node));16if(!L)17 exit(0);18 L->next = NULL;19 }2021 LinkList CreatList(LinkList &L, int n){//尾插法创建单链表22 LinkList r,p;23 r = L;24for(int i = 1; i <= n; i++){25 p = (LinkList)malloc(sizeof(Node));26 p->data = i;27 r->next = p;28 r = p;29 }30 r->next = NULL;31 p->next = L->next;//尾部指向头部，循环链表32return p->next;//返回头结点的头指针（构成循环）33 }3435int main(){36int n = 41;37int m = 3;38 LinkList L,p;39 InitList(L);40 p = CreatList(L,n);41 LinkList temp;42 m %= n;43while(p != p->next){44for(int i = 1;i < m-1; i++){45 p = p->next;46 }47 printf("%d->",p->next->data);48//删除结点49//p->next->next;50 temp = p->next;51 p->next = temp->next;52free(temp);53 p = p->next;54 }55 cout<<p->data;56return0;57 }运⾏结果：关于约瑟夫问题的题⽬：n个⼈围成⼀个圈，每个⼈分别标注为1、2、...、n，要求从1号从1开始报数，报到k的⼈出圈，接着下⼀个⼈⼜从1开始报数，如此循环，直到只剩最后⼀个⼈时，该⼈即为胜利者。

约瑟夫环问题的简单解法（数学公式法）关于约瑟夫环问题，无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。

我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。

因此如果要追求效率，就要打破常规，实施一点数学策略。

为了讨论方便，先把问题稍微改变一下，并不影响原意：问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。

求胜利者的编号。

我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:k k+1 k+2 … n-2, n-1, 0, 1, 2, … k-2并且从k开始报0。

现在我们把他们的编号做一下转换：k-2 – n-2k-1 – n-1解x’ —- 解为x注意x’就是最终的解变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x’=(x+k)%n如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。

(n-2)个人的解呢？当然是先求(n-3)的情况—- 这显然就是一个倒推问题！下面举例说明：假设现在是6个人（编号从0到5）报数，报到（2-1）的退出，即 m=2。

那么第一次编号为1的人退出圈子，从他之后的人开始算起，序列变为2,3,4,5,0，即问题变成了这5个人报数的问题，将序号做一下转换：现在假设x为0,1,2,3,4的解，x’设为那么原问题的解（这里注意，2,3,4,5,0的解就是0,1,2,3,4,5的解，因为1出去了，结果还是一个），根据观察发现，x与x’关系为x’=(x+m)%n，因此只要求出x，就可以求x’。

数据结构实验报告约瑟夫环约瑟夫环是一个古老而有趣的问题，也是数据结构中一个经典的应用。

它的故事发生在公元前1世纪，当时犹太人正面临罗马的入侵。

为了避免被俘虏，一群犹太士兵决定以一种特殊的方式自杀，而不是被罗马人俘虏。

他们围成一个圈，按照某个规则进行自杀，直到只剩下一个人为止。

这就是著名的约瑟夫环问题。

在这个问题中，我们有n个人，编号从1到n，围成一个圈。

按照一定的规则，从第一个人开始报数，每次报到m的人将被淘汰。

然后，从下一个人开始重新报数，如此循环，直到只剩下一个人为止。

这个问题的解决方法有很多，其中最常见的是使用链表数据结构。

我们可以将每个人表示为一个节点，节点之间通过指针连接，形成一个环形链表。

每次淘汰一个人后，只需要将指针跳过被淘汰的节点，重新连接链表。

为了更好地理解这个问题，我们可以通过一个简单的例子来演示。

假设有10个人，编号从1到10，每次报数到3的人将被淘汰。

首先，我们将这10个人表示为一个环形链表：1->2->3->4->5->6->7->8->9->10->1。

按照规则，第一次报数到3的人是3号，所以我们将3号节点从链表中删除：1->2->4->5->6->7->8->9->10->1。

接下来，从4号节点开始重新报数。

第二次报数到3的人是6号，所以我们再次将6号节点从链表中删除：1->2->4->5->7->8->9->10->1。

以此类推，直到只剩下一个人为止。

通过这个例子，我们可以看到约瑟夫环问题的解决方法非常简单直观。

使用链表数据结构，每次淘汰一个人后，只需要将指针跳过被淘汰的节点，重新连接链表。

这种方法的时间复杂度为O(n*m)，其中n为人数，m为报数的次数。

除了链表，还有其他数据结构可以用来解决约瑟夫环问题。

数据结构实验报告约瑟夫环约瑟夫环是一个经典的问题，涉及到数据结构中的循环链表。

在本次数据结构实验中，我们将学习如何使用循环链表来解决约瑟夫环问题。

约瑟夫环问题最早出现在古代，传说中的犹太历史学家约瑟夫斯·弗拉维奥（Josephus Flavius）在围攻耶路撒冷时，为了避免被罗马人俘虏，与其他39名犹太人躲进一个洞穴中。

他们决定宁愿自杀，也不愿被敌人俘虏。

于是，他们排成一个圆圈，从第一个人开始，每次数到第七个人，就将他杀死。

最后剩下的人将获得自由。

在这个问题中，我们需要实现一个循环链表，其中每个节点表示一个人。

我们可以使用一个整数来表示每个人的编号。

首先，我们需要创建一个循环链表，并将所有人的编号依次添加到链表中。

接下来，我们需要使用一个循环来模拟每次数到第七个人的过程。

我们可以使用一个指针来指向当前节点，然后将指针移动到下一个节点，直到数到第七个人为止。

一旦数到第七个人，我们就将该节点从链表中删除，并记录下该节点的编号。

然后，我们继续从下一个节点开始数数，直到只剩下一个节点为止。

在实现这个算法时，我们可以使用一个循环链表的数据结构来表示约瑟夫环。

循环链表是一种特殊的链表，其中最后一个节点的指针指向第一个节点。

这样，我们就可以实现循环遍历链表的功能。

在实验中，我们可以使用C语言来实现循环链表和约瑟夫环算法。

首先，我们需要定义一个节点结构体，其中包含一个整数字段用于存储编号，以及一个指针字段用于指向下一个节点。

然后，我们可以实现创建链表、添加节点、删除节点等基本操作。

接下来，我们可以编写一个函数来实现约瑟夫环算法。

该函数接受两个参数，分别是参与游戏的人数和每次数到第几个人。

在函数内部，我们可以创建一个循环链表，并将所有人的编号添加到链表中。

然后，我们可以使用一个循环来模拟每次数到第几个人的过程，直到只剩下一个节点为止。

在每次数到第几个人时，我们可以删除该节点，并记录下其编号。

最后，我们可以返回最后剩下的节点的编号。

约瑟夫问题简介约瑟夫问题是一个经典的数学问题，由弗拉维奥·约瑟夫斯(Josephus Flavius)所提出。

问题的背景是：在一个固定长度的圆桌周围围坐着n个人，从第一个人开始报数，报到m的人出圈，然后从下一个人开始重新报数，直到剩下最后一个人。

问题是，给定n和m，求最后剩下的人的编号。

解法暴力破解法最直观的解法是使用循环和数组来模拟这个过程。

首先，我们用一个数组来表示这些人的编号，例如[1, 2, 3, ..., n]。

然后我们在循环中模拟报数的过程，每次报到m的人就从数组中删除。

当数组中只剩下一个元素时，就找到了最后剩下的人。

def josephus(n, m):people = list(range(1, n +1))idx =0while len(people) >1:idx = (idx + m -1) % len(people)people.pop(idx)return people[0]这种解法的时间复杂度为O(n*m)，并且在n很大的情况下，性能会变得很差。

数学公式法约瑟夫问题其实存在一个更巧妙的解法，不需要模拟整个过程，而是通过数学公式来直接计算出最后剩下的人的编号。

如果我们将问题的规模缩小为n-1，即在一个长度为n-1的圆桌上进行同样的操作，求出的结果为f(n-1, m)。

然后我们将这个结果映射到原始问题的编号上，即将f(n-1, m)变为f(n, m)。

计算f(n, m)的过程如下： - 首先，我们将f(n, m)映射到f(n-1, m)上。

假设f(n, m) = x，那么f(n, m)在映射到f(n-1, m)上的过程中，每次都将整个序列向后移动m 位，即f(n, m)在映射到f(n-1, m)上的过程中，原来的第x个元素变成了第x+m个元素。

因此，f(n-1, m) = (x + m) % n。

- 其次，我们将f(n-1, m)映射回f(n, m)上。