双向列表实现约瑟夫问题

1．约瑟夫问题：n个人围成一圈，从第s（s<n）个人开始报数，数到m的人出圈；再由下一个人开始报数，数到m的人出圈；……。

输出依次出圈的人的编号。

m的值预先选定，n由键盘输入。

分析：我们将这n个人组成一个链表，表中每一个元素为一记录类型，第一个域变量lvalue为人的编号，第二个域变量next指向下一个人，这样链接下去构成一个环形链。

然后由lvalue值为s的记录开始，对链中的元素逐一记数，数到第m个记录时，将它删去，即把第（m-1）个记录的指针改成指向第（m+1）个记录，然后从第（m+1）个向下记数，这样重复进行下去，直到剩下一个记录。

出列的人也组成一条链，r是其首指针，只要打印这条链就得到结果。

源程序如下：#include <iostream.h>#include <stdio.h>#include <stdlib.h> // 使用malloc()函数的库函数#include <malloc.h>typedef struct linknode{int lvalue;struct linknode *next;} point;int main(){int n,m,s,node,i;point *p,*q,*r;cout<<"Input total number, initial number and distance: ";cin>>n>>s>>m;p=(point *)malloc(sizeof(point));q=p;for(i=1; i<=n-1; i++){ // 生成链表q->lvalue=s;s=s%n+1;q->next=(point *)malloc(sizeof(point));q=q->next;}q->lvalue=s;q->next=p; // 生成循环链表node=n;r=(point *)malloc(sizeof(point));q=r;while(node>1){if(m==1){r->next=p;node=1;}else{for(i=1; i<=m-2; i++)p=p->next;q->next=p->next; // 将数到m的人出圈，链到出列人的链表中q=q->next;p->next=p->next->next;p=p->next;node--;}}for(i=1; i<=n-1; i++){ // 依次打印出列人的序号r=r->next;cout<<"The"<<i<<"th person is number:"<<r->lvalue<<endl;}if(m==1)cout<<"The last one is number:"<<r->next->lvalue<<endl;elsecout<<"The last one is number:"<<p->lvalue<<endl;return 1;}2．设单链表中存放着n个字符，试设计算法判断字符串是否中心对称。

约瑟夫问题实验报告背景约瑟夫问题（Josephus Problem）据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。

然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

原题：用户输入M,N值，N个人围成一个环，从0号人开始数,数到M,那个人就退出游戏，直到最后一个人求最后一个剩下的人是几号？问题描述设编号为1-n的n(n>0)个人按顺时针方向围成一圈．首先第1个人从1开始顺时针报数．报m的人(m 为正整数)．令其出列。

然后再从他的下一个人开始，重新从1顺时针报数，报m的人，再令其出列。

如此下去，直到圈中所有人出列为止。

求出列编号序列。

一.需求分析：(1)基本要求需要基于线性表的基本操作来实现约瑟夫问题需要利用循环链表来实现线性表（2）输入输出格式输入格式：n，m(n,m均为正整数，)输出格式1：在字符界面上输出这n个数的输出序列(3)测试用例（举例）输入：8，4输出：4 8 5 2 1 3 7 6二．概要设计（1）抽象数据类型：数据对象：n个整数数据关系：除第一个和最后一个n外，其余每个整数都有两个元素与该元素相邻。

基本操作：查找，初始化，删除，创建链表循环链表的存储结构:（2）.算法的基本思想循环链表基本思想：先把n个整数存入循环链表中，设置第m个数出列，从第一个开始查找，找到第m个时，输出第m个数，并删掉第m个节点，再从下一个数开始查找,重复上一步骤，直到链表为空，结束。

（3）.程序的流程程序由三个模块组成：1.输入模块：完成两个正整数的输入，存入变量n和m中2.处理模块：找到第m个数3.输出模块：按找到的顺序把n个数输出到屏幕上三．详细设计首先，设计实现约瑟夫环问题的存储结构。

信息学竞赛复习1.斐波拉契数列（1000000以内的数字）#include “stdio.h”#include “stdlib.h”void main(){long fib1=1,fib2=1,fib=0;printf("1000000以内的数字:\n\n");printf("%d\n%d\n",fib1,fib2);while (fib<1000000){fib=fib1+fib2;fib1=fib2;fib2=fib;printf( "%d \n", fib);}system("pause");}2.约瑟夫问题（1）约瑟夫问题_数组#include "stdio.h"#include "stdlib.h"#define Length 100void main(){int i,j;int len; //输入的总节点数int n,m; //输入的每次数几个int remain; //剩下的节点数int current; //当前数到那个数字int a[Length];for(i=0;i<Length;i++){a[i]=1;}printf("请输入约瑟夫问题节点总数：");len=41; //scanf("%d",&len);printf("请输入每次数的节点数字：");n=3; //scanf("%d",&n);remain=len; //剩下的节点数current=0; //当前数到那个数字m=0; //计数到n，m=n时清零//从1开始数//循环到剩下的节点数为0printf("出列的节点的编号依次为：");while(remain>0){current++;while(current>len){current-=len;}if(a[current]==1){m++;if(m==n){a[current]=0;remain--;printf("%d, ",current);m=0;}}}system("pause");}（2）约瑟夫问题_数组环#include "stdio.h"#include "stdlib.h"void main(){int a[100];int i,len,n; //i循环 len总数 n每次数几个int cur,m,remain; //cur当前是哪个 m 计数 remain 剩下几个//int t1,t2;for(i=0;i<100;i++){a[i]=i+1;}printf("请输入约瑟夫问题节点总数：");len=41; //scanf("%d",&len);printf("请输入每次数的节点数字：");n=3; //scanf("%d",&n);a[len]=1; //首尾相连remain=len; //开始前，剩余数为总数cur=1; //当前从第1个开始m=1; //计数从1开始while(remain>0){cur=a[cur];m++;if(m==n-1){printf("%d, ",a[cur]);//t1=a[cur];//t2=a[a[cur]];a[cur]=a[a[cur]];remain--;m=0;}}system("pause");}（3）约瑟夫问题_链表#include "stdio.h"#include "stdlib.h"struct people{int num;struct people *next;};typedef struct people node;node *create(int m){int i;node *h,*p1,*p2;h=p1=p2=(node *)malloc(sizeof(node));h->num=1;for(i=1;i<m;i++){p1=(node *)malloc(sizeof(node));p2->next=p1;p1->num=i+1;p2=p1;}p1->next=h;return h;}node *findout(node *tp,int n){int i;node *p;p=tp;for(i=1;i<n-1;i++){p=p->next;}return p;}node *moveaway(node *tp){node *c,*p1,*p2;c=tp;p1=c->next;p2=p1->next;c->next=p2;printf("%d, ",p1->num);free(p1);return p2;}void main(){node *p;int len,i,n;printf("请输入约瑟夫问题节点总数：");len=41; //scanf("%d",&len);printf("请输入每次数的节点数字：");n=3; //scanf("%d",&n);p=create(len);for(i=1;i<=len;i++){p=moveaway(findout(p,n));}system("pause");}（4）约瑟夫问题_双向链表#include "stdio.h"#include "stdlib.h"struct people{int num;struct people *next;struct people *prior;};typedef struct people node;node *create(int m){int i;node *h,*p1,*p2;h=p1=p2=(node *)malloc(sizeof(node));h->num=1;for(i=1;i<m;i++){p1=(node *)malloc(sizeof(node));p2->next=p1;p1->prior=p2;p1->num=i+1;p2=p1;}p1->next=h;h->prior=p1;return h;}node *findout(node *tp,int n){int i;node *p;p=tp;for(i=1;i<n;i++){p=p->next;}return p;}node *moveaway(node *tp){node *c,*p1,*p2;c=tp;p1=c->prior;p2=c->next;p1->next=p2;p2->prior=p1;printf("%d, ",c->num);free(c);return p2;}void main(){node *p;int len,i,n;printf("请输入约瑟夫问题节点总数：");len=41;//scanf("%d",&len);printf("请输入每次数的节点数字：");n=3;//scanf("%d",&n);p=create(len);for(i=1;i<=len;i++){p=moveaway(findout(p,n));}system("pause");}3.数字7 和5（1）统计含有数字7，但不能被7整除的5位整数的个数#include <stdio.h>#include <stdlib.h>void main(){int sum=0;//统计个数int b;//起数int a[6];int have7;int j;int tempb;for(b=10000;b<100000;b++){//分离数字到数组tempb=b;for(j=0;j<5;j++){a[5-j]=tempb-(tempb/10)*10;tempb=tempb/10;}//判断是否含7have7=0;for(j=1;j<=5;j++){if(a[j]==7){have7++;}}if(have7>0 && b%7!=0){//printf("%d\n",b);sum++;}}printf("sum=%d\n",sum);system("pause");}（2）统计含有2个数字7，但不能被7整除的5位整数的个数#include <stdio.h>#include <stdlib.h>void main(){int sum=0;//统计个数int b;//起数int a[6];int have7;int j;int tempb;for(b=10000;b<100000;b++){//分离数字到数组tempb=b;for(j=0;j<5;j++){a[5-j]=tempb-(tempb/10)*10;tempb=tempb/10;}//判断是否含7have7=0;for(j=1;j<=5;j++){if(a[j]==7){have7++;}}if(have7==2 && b%7!=0){printf("%d\n",b);sum++;}}printf("sum=%d\n",sum);system("pause");}4.百钱买百鸡：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？（1）#include <stdio.h>#include <stdlib.h>void main(){int i,j,k;for(i=1;i<20;i++){for(j=1;j<33;j++){k=100-i-j;if(i*15+j*9+k==300){printf("鸡翁%d,鸡母%d,鸡雏%d\n",i,j,k);}}}system("pause");}（2）#include <stdio.h>#include <stdlib.h>void main(){int i,j,k;for(i=1;i<20;i++){for(j=1;j<33;j++){k=(100-i*5-j*3)*3;if(i+j+k==100){printf("鸡翁%d,鸡母%d,鸡雏%d\n",i,j,k);}}}system("pause");}5.逆序乘积式（1）两位数逆序乘积式#include <stdio.h>void main(){int sum=0;int a,b,c,d;int i,j,ir,jr,m,n;int arr[5];int flag;for(i=10;i<98;i++){arr[1]=a=i/10;arr[2]=b=i-a*10;for(j=i+1;j<98;j++){arr[3]=c=j/10;arr[4]=d=j-c*10;//检查有没有相同数字flag=0;for(m=1;m<4;m++){for(n=m+1;n<5;n++){if(arr[m]==arr[n]){flag=1;break;}}}//检查完//右侧的逆序ir=b*10+a;jr=d*10+c;if(flag==0&&i*j==ir*jr&&i<j&&i<ir&&i<jr){sum++;printf("%d:\ti=%d\t,j=%d\t,ir=%d\t,jr=%d\n",sum,i,j,ir,jr);}}}}（2）三位数逆序乘积式#include <stdio.h>void main(){int sum=0;int a,b,c,d,e,f;int i,j,ir,jr,m,n;int arr[7];int flag;for(i=100;i<987;i++){arr[1]=a=i/100;arr[2]=b=i/10-a*10;arr[3]=c=i-a*100-b*10;for(j=i+1;j<987;j++){arr[4]=d=j/100;arr[5]=e=j/10-d*10;arr[6]=f=j-d*100-e*10;//检查有没有相同数字flag=0;for(m=1;m<6;m++){for(n=m+1;n<7;n++){if(arr[m]==arr[n]){flag=1;break;}}}//检查完//右侧的逆序ir=c*100+b*10+a;jr=f*100+e*10+d;if(flag==0&&i*j==ir*jr&&i<j&&i<jr){sum++;printf("%d:\ti=%d\t,j=%d\t,ir=%d\t,jr=%d\n",sum,i,j,ir,jr);}}}}6.双和数组（1）普通解法#include <stdio.h>void main(){int s;int a,b,c,d,e,f;int arr[7];int flag,i,j;int sum=0;for (s=11;s<=100;s++){printf("s=%d:\n",s);for(a=1;a<=s-2;a++){for(b=a+1;b<=s-1;b++){for(d=a+1;d<=s-2;d++){for(e=d+1;e<=s-1;e++){c=s-a-b;f=s-d-e;//检查是否有重复数字arr[1]=a;arr[2]=b;arr[3]=c;arr[4]=d;arr[5]=e;arr[6]=f;if(a<b&&b<c&&d<e&&e<f){flag=0;for(i=1;i<7;i++){for(j=i+1;j<7;j++){if(arr[i]==arr[j]){flag=1;}}if(arr[i]<0){//避免负数flag=1;}}//没有重复的数字进入且符合倒数条件if(flag==0&&(a*b*c*(e*f+f*d+d*e)==d*e*f*(b*c+c*a+a*b))){sum++;printf("s=%d;a=%d,b=%d,c=%d,d=%d,e=%d,f=%d\n",s,a,b,c,d,e,f);}}}}}}}printf("sum=%d",sum);}（2）优化后解法#include <stdio.h>void main(){int s;int a,b,c,d,e,f;int arr[7];int flag,i,j;int sum=0;for (s=11;s<=100;s++){printf("s=%d:\n",s);for(a=1;a<=s-2;a++){for(b=a+1;b<=s-1;b++){for(d=a+1;d<=s-2;d++){for(e=d+1;e<=s-1;e++){c=s-a-b;f=s-d-e;//检查是否有重复数字arr[1]=a;arr[2]=b;arr[3]=c;arr[4]=d;arr[5]=e;arr[6]=f;flag=0;for(i=1;i<7;i++){for(j=i+1;j<7;j++){if(arr[i]==arr[j]){flag=1;}}if(arr[i]<0){//避免负数flag=1;}}if(a>b||a>c||b>c){flag=1;}if(d>e||d>f||e>f){flag=1;}//没有重复的数字进入且符合倒数条件if(flag==0&&(a*b*c*(e*f+f*d+d*e)==d*e*f*(b*c+c*a+a*b))){sum++;printf("s=%d;a=%d,b=%d,c=%d,d=%d,e=%d,f=%d\n",s,a,b,c,d,e,f);}}}}}}}7.八皇后问题（1）穷举法#include <stdio.h>#include <stdlib.h>#include <math.h>#define N 8 //定义棋盘大小void main(void){int numoftimes = 0;int count = 0;int a[N + 1];int flag;int i1, i2, i3, i4, i5, i6, i7, i8, x, y, p;printf("%d皇后问题的穷举法解决",N);for (i1 = 1; i1 <= N; i1++){a[1] = i1;for (i2 = 1; i2 <= N; i2++){a[2] = i2;for (i3 = 1; i3 <= N; i3++){a[3] = i3;for (i4 = 1; i4 <= N; i4++){a[4] = i4;for (i5 = 1; i5 <= N; i5++){a[5] = i5;for (i6 = 1; i6 <= N; i6++){a[6] = i6;for (i7 = 1; i7 <= N; i7++){a[7] = i7;for (i8 = 1; i8 <= N; i8++){a[8] = i8;//检测是否冲突flag = 0;for (x = 1; x < N; x++){for (y = x + 1; y <= N; y++){if (a[x] == a[y] || abs(a[x] - a[y]) == y - x){flag = 1;break;}numoftimes++;}if(flag==1){continue;}}if (flag==0){count++;printf("第%d种解法：", count); for (p = 1; p <= N; p++){printf("%d", a[p]);}printf("\n");}}}}}}}}}printf("共运行计算%d次\n", numoftimes);printf("共找到%d种方案\n", count);system("pause");}（2）递归法#include "stdio.h"#define N 8 //定义棋盘大小static int count,a[N];// count记录当前已找到解的个数// a[N]记录皇后的位置,表示第i行的皇后放在棋盘的第a[i]列int numoftimes = 0;void recursive(int t){//尝试第t行的放置方案int i;int j;int sign = 1;if (t == N + 1){//t == N + 1//表示放下最后一个皇后，找到解法count++;/* 第1种显示方法 */// t == N + 1// 已经得到一个解决方案printf("第%d种解法:", count);//Literal1.Text += string.Format("第{0}种解法:", count); for (i = 1; i <= N; i++){printf("%d",a[i]);//Literal1.Text += string.Format("{0}", a[i]);}printf("\n");//Literal1.Text += "<br/>";/* 第2种显示方法printf("第%d种解法:\n", count);for (i = 0; i < N; i ++){for (j = 0; j < N; j ++){if (j == a[i]){printf("@ ");}else{printf("* ");}}printf("\n");}printf("\n");*/}else{//还没有放下所有的皇后for (i = 1; i <= N; i++){//依次尝试在第t行的第1列到第N列放置a[t] = i;sign = 1;for (j = 1; j <= t - 1; j++){//测试皇后在第t行第a[t]列时是否与前面已放置好的皇后相攻击。

循环双链表特点循环双链表是一种特殊的数据结构，它具有循环和双向链表的特点。

循环双链表中的每个节点都包含两个指针，一个指向前一个节点，一个指向后一个节点。

最后一个节点的后指针指向头节点，头节点的前指针指向最后一个节点，从而形成了一个闭环。

循环双链表的特点如下：1. 双向性：每个节点都有两个指针，分别指向前一个节点和后一个节点。

这样可以方便地在任意位置插入或删除节点，而不需要像单链表那样需要遍历找到前驱节点。

2. 循环性：循环双链表是一个闭环，即最后一个节点的后指针指向头节点，头节点的前指针指向最后一个节点。

这样可以方便地进行循环遍历，不需要判断是否到达了链表的末尾。

3. 动态性：循环双链表可以动态地增加或删除节点，而不需要预先指定链表的长度。

4. 灵活性：循环双链表可以在任意位置插入或删除节点，不受限于只能在链表的头部或尾部进行操作。

这样可以方便地实现栈、队列等数据结构。

5. 代码实现简单：相比于其他数据结构，循环双链表的代码实现相对简单，只需要处理好节点之间的指针关系即可。

循环双链表的应用领域非常广泛，特别是在需要频繁插入和删除节点的场景中，循环双链表能够提供高效的插入和删除操作。

下面以几个具体的应用场景来展开对循环双链表的解释和扩展。

1. 缓存替换算法：循环双链表可以用于实现LRU（Least Recently Used）缓存替换算法。

LRU算法中，当缓存满时，需要替换掉最近最少使用的数据。

循环双链表可以维护数据的访问顺序，每次访问一个数据时，将其移到链表的头部；当缓存满时，删除链表尾部的数据即可。

这样就可以保证链表头部的数据是最近访问的数据，尾部的数据是最久未访问的数据。

2. 轮播图：循环双链表可以用于实现轮播图功能。

轮播图需要循环展示多张图片，循环双链表正好可以满足这个需求。

每个节点表示一张图片，节点之间通过指针连接起来形成一个循环链表。

通过不断地遍历链表，可以实现图片的自动切换。

3. 约瑟夫环问题：循环双链表可以用于解决约瑟夫环问题。

算法练习题一、基础算法1. 编写一个程序，实现一个冒泡排序算法。

2. 实现一个选择排序算法。

3. 实现一个插入排序算法。

4. 编写一个函数，计算一个整数数组中的最大值和最小值。

5. 编写一个函数，实现二分查找算法。

6. 编写一个函数，实现快速排序算法。

7. 编写一个函数，判断一个整数是否为素数。

8. 编写一个函数，实现反转一个整数数组。

9. 编写一个函数，计算两个整数数组的交集。

10. 编写一个函数，判断一个字符串是否为回文。

二、数据结构11. 实现一个单链表的基本操作，包括插入、删除、查找。

12. 实现一个双向链表的基本操作，包括插入、删除、查找。

13. 实现一个栈的基本操作，包括压栈、出栈、查看栈顶元素。

14. 实现一个队列的基本操作，包括入队、出队、查看队首元素。

15. 实现一个二叉树的基本操作，包括插入、删除、查找。

16. 实现一个二叉搜索树的基本操作，包括插入、删除、查找。

17. 实现一个哈希表的基本操作，包括插入、删除、查找。

三、搜索与图论18. 编写一个程序，实现深度优先搜索（DFS）算法。

19. 编写一个程序，实现广度优先搜索（BFS）算法。

20. 编写一个程序，求解迷宫问题。

21. 编写一个程序，计算一个有向图的拓扑排序。

22. 编写一个程序，计算一个无向图的欧拉回路。

23. 编写一个程序，计算一个加权无向图的最小树（Prim算法）。

24. 编写一个程序，计算一个加权有向图的最短路径（Dijkstra算法）。

25. 编写一个程序，计算一个加权有向图的所有顶点对的最短路径（Floyd算法）。

四、动态规划26. 编写一个程序，实现背包问题。

27. 编写一个程序，计算最长公共子序列（LCS）。

28. 编写一个程序，计算最长递增子序列（LIS）。

29. 编写一个程序，实现编辑距离（Levenshtein距离）。

30. 编写一个程序，实现硬币找零问题。

31. 编写一个程序，实现矩阵链乘问题。

“约瑟夫”问题及若干变种林厚从例1、约瑟夫问题(Josephus)[问题描述]M只猴子要选大王，选举办法如下：所有猴子按1…M编号围坐一圈，从第1号开始按顺序1，2，…，N报数，凡报到N的猴子退出到圈外，再从下一个猴子开始继续1~ N报数，如此循环，直到圈内只剩下一只猴子时，这只猴子就是大王。

M和N由键盘输入，1≤N,M≤10000，打印出最后剩下的那只猴子的编号。

例如，输入8 3，输出：7。

[问题分析1]这个例题是由古罗马著名史学家Josephus提出的问题演变而来的，所以通常称为Josephus(约瑟夫)问题。

在确定程序设计方法之前首先来考虑如何组织数据，由于要记录m只猴子的状态，可利用含m 个元素的数组monkey来实现。

利用元素下标代表猴子的编号，元素的值表示猴子的状态，用monkey[k]=1表示第k只猴子仍在圈中，monkey[k]=0则表示第k只猴子已经出圈。

程序采用模拟选举过程的方法，设变量count表示计数器，开始报数前将count置为0，设变量current表示当前报数的猴子编号，初始时也置为0，设变量out记录出圈猴子数，初始时也置为0。

每次报数都把monkey[current]的值加到count上，这样做的好处是直接避开了已出圈的猴子（因为它们对应的monkey[current]值为0），当count=n时，就对当前报数的猴子作出圈处理，即：monkey[current]：=0，count：=0，out：=out+1。

然后继续往下报数，直到圈中只剩一只猴子为止（即out=m-1）。

参考程序如下：program josephus1a {模拟法，用数组下标表示猴子的编号}const maxm=10000;var m,n,count,current,out,i:integer;monkey:array [1..maxm] of integer;beginwrite('Input m,n:');readln(m,n);for i:=1 to m do monkey[i]:=1;out:=0; count:=0; current:=0;while out<m-1 dobeginwhile count<n dobeginif current<m then current:=current+1 else current:=1;count:=count+monkey[current];end;monkey[current]:=0; out:=out+1; count:=0end;for i:=1 to m doif monkey[i]=1 then writeln('The monkey king is no.',i);readlnend.[运行结果]下划线表示输入Input m，n:8 3The monkey king is no.7 {时间：0秒}Input m，n:10000 1987The monkey king is no.8544 {时间：3秒}[反思]时间复杂度很大O(M*N)，对于极限数据会超时。

数据结构与算法（Python版）：⽤队列（Queue）处理约瑟夫问题在古罗马时期，犹太⼈背叛了罗马⼈，落到困境，约瑟夫和同⾏的⼀共39个犹太⼈只能够⾃杀殉国，但是犹太教义规定不能⾃杀，因此只能够让别⼈将⾃⼰杀害。

他们所有39个⼈坐成⼀圈，报数1—7，报到7则由⾝旁的⼈将⾃⼰杀死。

结果约瑟夫灵机⼀动，给⾃⼰安排了⼀个位置，最后活了下来，那么约瑟夫给⾃⼰安排的是哪⼀个位置呢？在这个题⽬当中，我们如果使⽤队列，不仅可以处理任意⼈数坐成⼀圈，还可以将报数的值任意修改，最后都可以找到那⼀个不被杀死的⼈的位置。

我们可以将所有⼈都放进⼀个⼤的队列⾥，每报⼀次数字，那么就把队列头部的⼈放到队列的尾部，直到报数报到⼀组数字的最后⼀个，⽐如1——7当中的7。

这个时候就将队列头的这个⼈删除（也就是杀死），不断执⾏这个过程，直到整个队列当中的⼈数只有⼀个，则跳出循环返回最后活着的那个⼈的名字。

⾸先定义队列（Queue）类的结构：class Queue():def__init__(self):# 初始化⼀个空的列表self.__list=[]# 往队列⾥插⼊元素def enqueue(self,item):self.__list.append(item)# 弹出队列⾥的元素def dequeue(self):return self.__list.pop(0)# 弹出队列⾥最先进⼊的元素# 判断队列是否为空def is_empty(self):return self.__list == []# 计算队列的⼤⼩def size(self):return len(self.__list)使⽤队列类来初始化⼀个对象，sim_queue,然后编写刚才我们分析之后的程序：def hot_potato(namelist,num):sim_queue = Queue()for name in namelist:sim_queue.enqueue(name) # 把拿到的名字全部都放到队列⾥while sim_queue.size() > 1:for i in range(num):sim_queue.enqueue(sim_queue.dequeue())# 每执⾏完⼀次，就将队列的头拿出来弹出，相当于⼟⾖传递给这个⼈，然后这个⼈就死了last_person=sim_queue.dequeue()return last_personprint("开始执⾏约瑟夫问题")print(hot_potato(["bob","NAni","Ao li Gei!","HeHe","Mike","Suvennia"],4))输出：开始执⾏约瑟夫问题Ao li Gei!得解，因此Ao li Gei!这个⼈不会被杀死。