C++约瑟夫问题

题1. 统计字母的使用频率一、题目：统计字母的使用频率二、目的与要求1．目的：通过编写程序统计字母的使用频率，培养学生综合利用C语言进行程序设计的能力，熟悉字符串的操作方法，加强函数的运用，提高软件系统分析能力和程序文档建立、归纳总结的能力。

2．基本要求：1）要求用C语言编程，在Visual C++环境下调试完成；2）要求按照程序功能分成几个功能模块来实现，各个功能模块分别使用函数来完成；3）要求应用本课所讲授的程序设计语言知识来解决问题三、设计方法和基本原理1．课题功能描述本程序的功能，就是要统计英文字母的使用频率。

2．问题详细描述为统计英文字母的使用频率，输入一个不包括空格的由英文字母组成的字符串，长度不超过200个字符。

统计26个英文字母的使用频率，不区分大小写。

最后按使用频率从大到小输出字母（小写字母）和使用频率（出现的次数）。

3．问题的解决方案按照程序要求，本程序应采用模块化设计方法,设计几个功能模块。

例如（仅供参考）：l 将字符串中的大写字母转换为小写字母l 统计输入的字符串中字母的使用频率l 按使用频率从大到小进行排序主函数中控制输入、函数调用和输出。

四、主要技术问题的描述根据三的分析，主要问题在于：1) 为统计字母的使用频率，定义一个长度为26的int数组存放所统计的各个字母的使用频率。

2) 在统计字母的使用频率时，不要使用if语句或switch语句，利用字母的ASCII码与数组元素下标之间的关系来求得。

3) 按使用频率从大到小进行排序时，建议使用指针数组更为方便。

五、创新要求实现程序功能后，可进行创新设计：1) 使用多文件，即主函数和各个函数分别存放在不同的.c文件中，在头文件中进行函数原型声明。

2) 读入一篇英文文档，并对其进行字母频率分析。

题2.指示灯控制问题描述：N盏灯排成一排，从1到N按顺序依次编号。

有N个人也从1到N依次编号。

第一个人（1号）将灯全部关闭。

第二个人（2号）将凡是2和2的倍数的灯打开。

约瑟夫环问题问题描述：有n个⼈，编号分别从0到n-1排列，这n个⼈围成⼀圈，现在从编号为0的⼈开始报数，当报到数字m的⼈，离开圈⼦，然后接着下⼀个⼈从0开始报数，依次类推，问最后只剩下⼀个⼈时，编号是多少？分析：这就是著名的约瑟夫环问题，关于来历不再说明，这⾥直接分析解法。

解法⼀：蛮⼒法。

我曾将在⼤⼀学c语⾔的时候，⽤蛮⼒法实现过，就是采⽤标记变量的⽅法即可。

解法⼀：循环链表法。

从问题的本质⼊⼿，既然是围成⼀个圈，并且要删除节点，显然符合循环链表的数据结构，因此可以采⽤循环链表实现。

解法三：递推法。

这是⼀种创新的解法，采⽤数学建模的⽅法去做。

具体如下：⾸先定义⼀个关于n和m的⽅程f(n,m)，表⽰每次在n个编号0，1，...，n-1中每次删除的报数为m后剩下的数字，在这n个数字中，第⼀个被删除的数字是(m-1)%n，为了简单，把(m-1)%n记作k，那么删除k之后剩下的数字为0，1，2，...，k-1，k+1，...，n-1并且下⼀次删除的数字从k+1开始计数，这就相当于剩下的序列中k+1排在最前⾯，进⽽形成k+1,..,n-1,0,1,2,...,k-1这样的序列，这个序列最后剩下的数字应该和原序列相同，由于我们改变了次序，不能简单的记作f(n-1,m),我们可以记作g(n-1,m),那么就会有f(n,m)=g(n-1,m).下⼀步，我们把这n-2个数字的序列k+1,..,n-1,0,1,2,...,k-1做⼀个映射，映射的结果是形成⼀个从0到n-2的序列。

k+1对0，k+2对1，......，n-1对n-k-2，0对n-k-1，1对n-k，....，k-1对n-2这样我们可以把这个映射定义为p,则p(x)=(x-k-1)%n,它表⽰如果映射前的数字是x，映射后为(x-k-1)%n,从⽽这个映射的反映射问为p-1(x)=(x+k+1)%n由于映射之后的序列和原始序列具有相同的形式，都是从0开始的序列，所以可以⽤函数f来表⽰，即为f(n-1,m)，根据映射规则有：g(n-1,m)=p-1[f(n-n,m)]=[f(n-1,m)+k+1]%n,最后把之前的k=(m-1)%n带⼊式⼦就会有f(n,m)=g(n-1,m)=[f(n-1,m)+m]%n.这样我们就可以得出⼀个递推公式，当n=1时，f(n,m)=0;当n>1时，f(n,m)=[f(n-1,m)+m]%n;有了这个公式，问题就变得多了。

约瑟夫环问题如下：已知n个人(n>=1)围桌一园桌周围，从1开始顺序编号。

从序号为1的人开始报数，顺时针数到m的那个人出列。

他的下一个人又从1开始报数，数到m的那个人又出列。

依此规则重复下去，直到所有人全部出列。

求解最后一个出列的人的编号。

本次实验是以顺序表求解约瑟夫环问题，程序流程图及程序运行结果如下：输入人数、所报数、第一个报数人编号存储并建立一个约瑟夫环通过循环结构依次查找每次出列的人的编号并输出输出最后一个出列的人的编号程序代码如下：#include<iostream>#include<process.h>#include<stdlib.h>using namespace std;struct Node //循环节点的定义{int number; //编号Node *next;};Node *CreateList(Node *L,int &n,int &m); //建立约瑟夫环函数void Joseph(Node *L,int n,int m); //输出每次出列号数函数Node *DeleteList(Node **L,int i,Node *q); //寻找每次出列人的号数int LengthList(Node *L); //计算环上所有人数函数void main() //主函数{system("color 75"); //设置颜色以美观Node *L;L=NULL; //初始化尾指针int n, m;cout<<"请输入人数N：";cin>>n; //环的长度if(n<1){cout<<"请输入正整数!";} //人数异常处理else{cout<<"请输入所报数M：";cin>>m;if(m<1){cout<<"请输入正整数!";} //号数异常处理else{L=CreateList(L,n,m); //重新给尾指针赋值Joseph(L,n,m);}}system("pause");}Node *CreateList(Node *L,int &n,int &m) //建立一个约瑟夫环（尾插法）{Node *q;for(int i=1;i<=n;i++){Node *p;p=new Node;p->number=i;p->next=NULL;if(i==1) L=q=p; //工作指针的初始化 else{q->next=p;q=q->next;}}q->next=L;if(L!=NULL){return(L);} //返回尾指针else cout<<"尾指针异常!"<<endl; //尾指针异常处理}void Joseph(Node *L,int n,int m) //输出每次出列的人{int k;cout<<"请输入第一个报数人：";cin>>k;if(k<1||k>n){cout<<"请输入1-"<<n<<"之间的数"<<endl;}else{cout<<"\n出列顺序:\n";for(int i=1;i<n;i++){Node *q = new Node;if(i==1) q=DeleteList(&L,k+m-1,q); //第一个出列人的号数else q=DeleteList(&L,m,q);cout<<"号数："<<q->number<<endl;delete q; //释放出列人的存储空间}cout<<"最后一个出列号数是："<<L->number<<endl; //输出最后出列人的号数}}Node *DeleteList(Node **L,int i,Node *q) //寻找每次出列的人{if(i==1) i+=LengthList(*L); //顺序依次出列情况的处理方式Node *p;p=*L;int j=0;while(j<i-2) {p=p->next;j++;}q = p->next;p->next=p->next->next;*L = p->next;return(q);}int LengthList(Node *L) //计算环上的人数{if(L){cout<<"尾指针错误!"<<endl;} //异常处理else{int i=1;Node *p=L->next;while(p!=L){i++;p=p->next;}return(i);}}实验体会：通过对本问题的分析，我进一步熟悉了对各种逻辑表达式的判断和指针的使用。

约瑟夫问题（有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。

在计算机编程的算法中，类似问题又称为约瑟夫环。

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

然而Josephus 和他的朋友并不想遵从。

首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。

接着，再越过k-1个人，并杀掉第k个人。

这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。

问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

//详情请见百度百科。

[题目描述]Josephus问题是建立在历史学家Josephus的一个报告的基础之上，该报告讲述了他和40个士兵在公元67年被罗马军队包围期间签定的一个自杀协定，Josephus建议每个人杀死他的邻居，他很聪明的使自己成为这些人中的最后一个，因此获得生还。

21世纪的今天，我们将Josephus问题稍作扩展：设N个人围成一圈，依次从1到N编号，从第S号开始报数，报到K的人出列，求第T个出列的人的编号。

显然，Josephus面对的是N = 40, K = 2, S= 1, T = 40的退化情况。

[数据范围]30%的数据，K = 2100%的数据，1 <= N <= 1000000, 1<= K <= 2147483647, 1 <= S <= N, 1 <= T <= N最简单的推导方法应该是模拟。

#include<iostream>using namespace std;struct Node//定义节点的结构类型{int data;Node* next;};class CircularLinkedList//循环链表类{public:CircularLinkedList(){first=new Node;first->next=NULL;}CircularLinkedList(int n);//构建一个附有值的循环链表~CircularLinkedList();int Josephus(int num);//约瑟夫函数private:Node* first;};CircularLinkedList::CircularLinkedList(int n){first=new Node;Node * r=first;for(int i=1;i<=n;i++){Node* s=new Node;s->data=i;s->next=NULL;r->next=s;r=s;} //头插法初始化链表r->next=first; //最后一个元素的next志指向头结点}CircularLinkedList::~CircularLinkedList(){Node* p=first,*q;while(p->next!=first)//p指向最后一个结点时结束循环{q=p;p=p->next;delete q;}delete p;//删除头结点}int CircularLinkedList::Josephus(int num){Node* p=first,*q;if(num<=0)throw "输入错误！";while(first->next->next!=first){for(int i=1;i<num;i++) //p向后移动num位，指向要删除的元素的前一个结点{p=p->next;if(p==first) //若循环过程中出现p指向头结点，则跳过头结点{p=p->next;}}if(p->next==first) //若循环结束后p指向最后一个元素，则要跳过头结点，并让头结点的next指向要删除元素的下一个{p=first;q=p->next;p->next=q->next;//first->next=q->next;cout<<q->data<<" ";delete q;}else{q=p->next;p->next=q->next;cout<<q->data<<" ";delete q;}}cout<<endl;cout<<"最后一个数为：";return first->next->data;}void main(){int n,m;cout<<"请输入约瑟夫问题的人数和间隔人数：";cin>>n>>m;cout<<"依次删除："<<endl;CircularLinkedList Josephus1(n);//创建的对象调用第二个构造函数cout<<Josephus1.Josephus(m)<<endl;}。

C++约瑟夫环的实例代码C++ 约瑟夫环的实例代码约瑟夫环是⼀个数学的应⽤问题：已知n个⼈（以编号1，2，3...n分别表⽰）围坐在⼀张圆桌周围。

从编号为k的⼈开始报数，数到m的那个⼈出列；他的下⼀个⼈⼜从1开始报数，数到m的那个⼈⼜出列；依此规律重复下去，直到圆桌周围的⼈全部出列。

分析：有n个⼈，要想所有的⼈都退出去，只有每个⼈喊到m，才可以退完，所以可以算出，n*m为所有⼈总共报数的总次数。

代码：/** 约瑟夫出圈*/#include <stdio.h>int main(){char peo[100] ;char *p_peo = peo;int i , n , skip , flag[100] = {0} , cnt;int *p_flag = NULL;printf("请输⼊⼈数：");scanf("%d", &n);printf("所有⼈如下：\n");for(p_peo , i = 0 ; p_peo < peo + n ; ++p_peo , ++i){*p_peo = 'a' + i;printf("%c ", *p_peo);}printf("\n");printf("请输⼊报数值：");scanf("%d", &skip);cnt = 0;while(cnt <= n * skip){for(p_peo = peo , p_flag = flag ; p_peo < peo + n ; ++p_peo , ++p_flag){if(*p_flag)continue;cnt++;if(!(cnt % skip)){*p_flag = 1;printf("%c ", *p_peo);}}}printf("\n");return 0;}如有疑问请留⾔或者到本站社区交流讨论，感谢阅读，希望能帮助到⼤家，谢谢⼤家对本站的⽀持！。

c课程设计约瑟夫问题一、教学目标本章节的教学目标分为三个维度：知识目标、技能目标和情感态度价值观目标。

1.知识目标：通过学习约瑟夫问题，学生能够理解并掌握约瑟夫问题的基本概念、原理和解决方法。

2.技能目标：学生能够运用所学的约瑟夫问题的解决方法，解决实际问题，并能够进行简单的数学推理和分析。

3.情感态度价值观目标：通过学习约瑟夫问题，学生能够培养对数学的兴趣和好奇心，提高解决问题的能力和团队合作的精神。

二、教学内容本章节的教学内容以约瑟夫问题为核心，包括以下几个方面：1.约瑟夫问题的定义和背景介绍。

2.约瑟夫问题的解决方法，包括递归法、循环队列法和迭代法。

3.约瑟夫问题的应用场景，结合实际问题进行讲解。

4.约瑟夫问题的扩展，如约瑟夫环的生成和约瑟夫问题的变种。

三、教学方法为了激发学生的学习兴趣和主动性，本章节将采用多种教学方法：1.讲授法：通过讲解约瑟夫问题的定义、原理和解决方法，使学生掌握基本概念和知识点。

2.案例分析法：通过分析实际问题，引导学生运用所学的约瑟夫问题的解决方法，培养学生的解决问题的能力。

3.实验法：通过进行约瑟夫问题的编程实验，让学生亲手实践，加深对解决方法的理解和记忆。

四、教学资源为了支持教学内容和教学方法的实施，丰富学生的学习体验，将选择和准备以下教学资源：1.教材：选用权威、系统的教材，如《计算机科学导论》等，作为学生学习的基本依据。

2.参考书：推荐一些相关的参考书，如《算法导论》等，供学生进一步拓展学习。

3.多媒体资料：制作PPT、教学视频等多媒体资料，以图文并茂的形式呈现教学内容，提高学生的学习兴趣。

4.实验设备：准备计算机实验室，让学生能够进行约瑟夫问题的编程实验，提高实践能力。

五、教学评估本章节的评估方式包括平时表现、作业和考试三个部分，以全面、客观、公正地评估学生的学习成果。

1.平时表现：通过观察学生在课堂上的参与度、提问和回答问题的表现，了解学生的学习态度和理解程度。

C语言的循环链表和约瑟夫环C语言的循环链表和约瑟夫环约瑟夫问题）是一个数学的应用问题，对于学习C语言四非常挺有帮助的，下面是店铺为大家搜集整理出来的有关于C语言的循环链表和约瑟夫环，一起了解下吧!循环链表的实现单链表只有向后结点，当单链表的尾链表不指向NULL，而是指向头结点时候，形成了一个环，成为单循环链表，简称循环链表。

当它是空表，向后结点就只想了自己，这也是它与单链表的主要差异，判断node->next是否等于head。

代码实现分为四部分：1. 初始化2. 插入3. 删除4. 定位寻找代码实现：1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1void ListInit(Node *pNode){int item;Node *temp,*target;cout<<"输入0完成初始化"<<endl; cin="">>item;if(!item)return ;if(!(pNode)){ //当空表的时候，head==NULLpNode = new Node ;if(!(pNode))exit(0);//未成功申请pNode->data = item;pNode->next = pNode;}else{//for(target = pNode;target->next!=pNode;target = target->next);4 15 16 17 18 19 2 0 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 3 0 3 1 3 2 3 3 3 4 3 5 3temp = new Node;if(!(temp))exit(0);temp->data = item;temp->next = pNode;target->next = temp;}}}void ListInsert(Node *pNode,int i){ //参数是首节点和插入位置Node *temp;Node *target;int item;cout<<"输入您要插入的值:"<<endl; cin="">>item;if(i==1){temp = new Node;if(!temp)exit(0);temp->data = item;for(target=pNode;target->next != pNode;target = target->next);temp->next = pNode;target->next = temp;pNode = temp;}else{target = pNode;for (int j=1;j<i-1;++j) target="target-">next;temp = new Node;if(!temp)exit(0);temp->data = item;temp->next = target->next;target->next = temp;}}void ListDelete(Node *pNode,int i){Node *target,*temp;if(i==1){for(target=pNode;target->next!=pNode;target=target ->next);temp = pNode;//保存一下要删除的首节点 ,一会便于释放6 37 38 39 4 0 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 5 0 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5pNode = pNode->next;target->next = pNode;temp;}else{target = pNode;for(int j=1;j<i-1;++j) target="target-">next;temp = target->next;//要释放的nodetarget->next = target->next->next;temp;}}int ListSearch(Node *pNode,int elem){ //查询并返回结点所在的位置Node *target;int i=1;for(target = pNode;target->data!=elem && target->next!= pNode;++i)target = target->next;if(target->next == pNode && target->data!=elem)return 0;else return i;}</i-1;++j)></i-1;++j)></endl;></endl;>5 96 0 6 1 6 2 6 3 6 4 6 5 6 6 67 68 69 7 0 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 8约瑟夫问题约瑟夫环(约瑟夫问题)是一个数学的'应用问题：已知n个人(以编号1，2，3…n分别表示)围坐在一张圆桌周围。