C++循环链表之约瑟夫环的实现方法

本文实例形式展示了C++实现循环链表中约瑟夫环的方法,分享给大家供大家参考之用。具体方法如下:

主要功能代码如下:

#include <iostream>
using namespace std;

typedef struct student
{
 int data;
 struct student* next;
}node,*LinkList;
//约瑟夫环
void printfList(LinkList head){

 LinkList p=head;
 if (head!=NULL)
 {

 do{
  cout<<p->data<<" ";
  p=p->next;
 }while(p!=head);//这里出现过问题,用do-while
 cout<<endl;
 }
}
void Josephus(int n,int k,int m){
 int i=2;
 LinkList head=(LinkList)malloc(sizeof(node));
 head->next=head;
 head->data=1;
 LinkList pre=head;
 while(i<=n){
   LinkList p=(LinkList)malloc(sizeof(node));
 p->data=i;
 p->next=pre->next;
 pre->next=p;
 pre=p;
 i++;
 }
 printfList(head);

 LinkList mend=pre;
 int kk=0;
 while(kk!=k){
 mend=mend->next;
 ++kk;
 }//找到k个开始

 while(n--){//要全部输出
 int mm=1;
 pre=mend;//每次都要给pre从新复值否则程序错误
 while(mm!=m){//不是要求的数,指针每次往前推一步,mend指向报数的人,pre指向前一个
  pre=mend;
  mend=mend->next;
  mm++;
 }
 pre->next=mend->next;//前一个链到下一个准备报数的
 cout<<mend->data<<endl;
 LinkList deletem=mend;
 mend=pre->next;//mend指向报数的人;
 free(deletem); //最后删除
 }
}
int main(){
 Josephus(13,4,1);
 return 0;
}

希望本文所述对大家的C++程序设计有所帮助。

时间: 2014-08-31

C++ 中循环链表和约瑟夫环

循环链表和约瑟夫环 循环链表的实现 单链表只有向后结点,当单链表的尾链表不指向NULL,而是指向头结点时候,形成了一个环,成为单循环链表,简称循环链表.当它是空表,向后结点就只想了自己,这也是它与单链表的主要差异,判断node->next是否等于head. 代码实现分为四部分: 初始化 插入 删除 定位寻找 代码实现: void ListInit(Node *pNode){ int item; Node *temp,*target; cout<<"输入0完成初始化"&

C++ 中约瑟夫环替换计数器m(数组解决)

C++ 中约瑟夫环替换计数器m(数组解决) 题目描述: 输入一个由随机数组成的数列(数列中每个数均是大于0的整数,长度已知),和初始计数值m.从数列首位置开始计数,计数到m后,将数列该位置数值替换计数值m,并将数列该位置数值出列,然后从下一位置从新开始计数,直到数列所有数值出列为止.如果计数到达数列尾段,则返回数列首位置继续计数.请编程实现上述计数过程,同时输出数值出列的顺序 比如: 输入的随机数列为:3,1,2,4,初始计数值m=7,从数列首位置开始计数(数值3所在位置) 第一轮计数出列数字为

C++ 约瑟夫环的实例代码

C++ 约瑟夫环的实例代码 约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围.从编号为k的人开始报数,数到m的那个人出列:他的下一个人又从1开始报数,数到m的那个人又出列:依此规律重复下去,直到圆桌周围的人全部出列. 分析:有n个人,要想所有的人都退出去,只有每个人喊到m,才可以退完,所以可以算出,n*m为所有人总共报数的总次数. 代码: /* * 约瑟夫出圈 */ #include <stdio.h> int main() { char peo[

java 实现约瑟夫环的实例代码

复制代码 代码如下: import java.io.BufferedInputStream;import java.util.ArrayList;import java.util.List;import java.util.Scanner;public class Josephus {    private static class Node{        int No;        Node next;        public Node(int No){            this

php解决约瑟夫环算法实例分析

本文实例讲述了php解决约瑟夫环算法.分享给大家供大家参考,具体如下: 今天偶遇一道算法题 "约瑟夫环"是一个数学的应用问题:一群猴子排成一圈,按1,2,-,n依次编号.然后从第1只开始数,数到第m只,把它踢出圈,从它后面再开始数, 再数到第m只,在把它踢出去-,如此不停的进行下去, 直到最后只剩下一只猴子为止,那只猴子就叫做大王.要求编程模拟此过程,输入m.n, 输出最后那个大王的编号. 方法一:递归算法 function killMonkey($monkeys , $m , $cu

python判断链表是否有环的实例代码

先看下实例代码: class Node: def __init__(self,value=None): self.value = value self.next = None class LinkList: def __init__(self,head = None): self.head = head def get_head_node(self): """ 获取头部节点 """ return self.head def append(self

判断给定的图是不是有向无环图实例代码

复制代码 代码如下: #include<iostream>#include<list>#include<stack>using namespace std; class Graph { int vertexNum; list<int> *adjacents;public: Graph(int _vertexNum) {  vertexNum = _vertexNum;  adjacents = new list<int>[vertexNum]; 

利用简洁的C语言代码解决跳台阶问题与约瑟夫环问题

跳台阶问题 题目: 一个台阶总共有 n 级,如果一次可以跳 1 级,也可以跳 2 级. 求总共有多少总跳法,并分析算法的时间复杂度. 分析: 也是比较基础的题目,通过递归可以方便的求解 代码实现如下(GCC编译通过): #include "stdio.h" #include "stdlib.h" int function(int n); int main(void) { int tmp; tmp = function(5); printf("%3d\n&q

代码详解Java猴子选王问题(约瑟夫环)

关于约瑟夫环的基本知识: 罗马人攻占了乔塔帕特,41人藏在一个山洞中躲过了这场浩劫.这41个人中,包括历史学家josephus和他的一个朋友.剩余的39个人为了表示不向罗马人屈服,决定集体自杀.大家决定了一个自杀方案,所有这41人围城一个圆圈,由第一个人开始顺时针报数,没报数为3的人就立刻自杀,然后由下一个人重新开始报数仍然是每报数为3的人就立刻自杀,......,知道所有人都自杀死亡为止.约瑟夫和他的朋友并不想自杀,于是约瑟夫想到了一个计策,他们两个同样参数到自杀方案中,但是最后却躲过了自杀.

PHP实现的基于单向链表解决约瑟夫环问题示例

本文实例讲述了PHP实现的基于单向链表解决约瑟夫环问题.分享给大家供大家参考,具体如下: 约瑟夫环问题:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止.然而Josephus 和他的朋友并不想遵从.首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人.接着,再越

Java简单实现约瑟夫环算法示例

本文实例讲述了Java简单实现约瑟夫环算法.分享给大家供大家参考,具体如下: 1.算法背景: 罗马人攻占了乔塔帕特,41人藏在一个山洞中躲过了这场浩劫.这41个人中,包括历史学家josephus和他的一个朋友.剩余的39个人为了表示不向罗马人屈服,决定集体自杀.大家决定了一个自杀方案,所有这41人围城一个圆圈,由第一个人开始顺时针报数,没报数为3的人就立刻自杀,然后由下一个人重新开始报数 仍然是每报数为3的人就立刻自杀,......,知道所有人都自杀死亡为止. 约瑟夫和他的朋友并不想自杀,于是约

Python实现约瑟夫环问题的方法

本文实例讲述了Python实现约瑟夫环问题的方法.分享给大家供大家参考,具体如下: 题目:0,1,...,n-1这n个数字排成一个圆圈,从数字0开始每次从这个圆圈里删除第m个数字.求出这个圆圈里剩下的最后一个数字. 定义函数f(n,m),表示每次在n个数字(0,1,...,n-1)中每次删除第m个数字后最后剩下的数字. 在n个数字中,假设第一个被删除的数字为k,那么删除k之后剩下的n-1个数字为0~k-1,k 1~n-1,并且下一次删除从数字k 1开始计数.第二个序列最后剩下的数字也就是我们要求