养花网什么叫约瑟问题？
约瑟夫问题（有时也称为约瑟夫斯置换，是一个计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。又称“丢手绢问题”.）
约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3。
分析：（1）由于对于每个人只有死和活两种状态，因此可以用布尔型数组标记每个人的状态，可用true表示死，false表示活。（2）开始时每个人都是活的，所以数组初值全部赋为false。（3）模拟杀人过程，直到所有人都被杀死为止。
延伸阅读
数据结构编程：求解报数问题。设有n个人占成一排，从左向右的编号分别为1到n，现在从左往右报数“1，2？
这个问题就是『约瑟夫环』问题嘛。
1 问题描述
约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知 n 个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为 k 的人开始报数，数到 m 的那个人出圈；他的下一个人又从 1 开始报数，数到 m 的那个人又出圈；依此规律重复下去，直到剩余最后一个胜利者。
例如：有10个人围成一圈进行此游戏，每个人编号为 1-10,。若规定数到 3 的人出圈。则游戏过程如下。
（1）开始报数，第一个数到 3 的人为 3 号，3 号出圈。 ??1， 2， 【3】， 4， 5， 6， 7， 8， 9， 10。 （2）从4号重新从1开始计数，则接下来数到3的人为6号，6号出圈。 ??1， 2， 【3】， 4， 5， 【6】， 7， 8， 9， 10。 （3）从7号重新从1开始计数，则接下来数到3的人为9号，9号出圈。 ??1， 2， 【3】， 4， 5， 【6】， 7， 8， 【9】， 10。 （4）从10号重新从1开始计数，由于10个人称环形结构，则接下来数到3的人为2号，2号出圈。 ??1， 【2】， 【3】， 4， 5， 【6】， 7， 8， 【9】， 10。 （5）从4号重新从1开始计数，则接下来数到3的人为7号，7号出圈。 ??1， 【2】， 【3】， 4， 5， 【6】， 【7】， 8， 【9】， 10。 （6）从8号重新从1开始计数，则接下来数到3的人为1号，1号出圈。 ??【1】， 【2】， 【3】， 4， 5， 【6】， 【7】， 8， 【9】， 10。 （7）从4号重新从1开始计数，则接下来数到3的人为8号，8号出圈。 ??【1】， 【2】， 【3】， 4， 5， 【6】， 【7】， 【8】， 【9】， 10。 （8）从10号重新从1开始计数，则接下来数到3的人为5号，5号出圈。 ??【1】， 【2】， 【3】， 4， 【5】， 【6】， 【7】， 【8】， 【9】， 10。 （9）从10号重新从1开始计数，则接下来数到3的人为10号，10号出圈。 ??【1】， 【2】， 【3】， 4， 【5】， 【6】， 【7】， 【8】， 【9】， 【10】。 （10）最终剩余 4 号，4 号为胜利者。
2 数组求解
2.1 解题思想
用数组求解的基本思想就是用一个一维数组去标识这 n 个人的状态，默认全为 1 ，也就是都在圈子内，当数到 m的人出圈之后，标识置为 0（就是出圈了），同时报数器清 0，下一个人要从 1 开始。在每次报数之前要判断他是否在圈子内（也就是他的标识是否为 1 ），如果在圈子里面才会继续报数。定义一个变量记录出圈的人数， 出圈的人数等于 n-1 时，则游戏结束。
2.2 代码实现
3 循环链表求解3.1 解题思想
约瑟夫环问题可以转化为循环链表的数据结构来求解。可以将每个人看做链表的单个节点，每个节点之间通过链表的 next 指针连接起来，并且将链表末尾节点指向头节点就形成的环，由链表构成的环形结构在数据结构中称为循环链表。
3.2 代码实现
4 递推公式求解4.1 解题思想
约瑟夫环中，每当有一个人出圈，出圈的人的下一个人成为新的环的头，相当于把数组向前移动 m 位。若已知 n-1 个人时，胜利者的下标位置位 f(n?1,m) ，则 n 个人的时候，就是往后移动 m 位，(因为有可能数组越界，超过的部分会被接到头上，所以还要模 n )，根据此推导过程得到的计算公式为： ??f(n,m) = (f(n?1,m) + m) % n。 其中，f(n,m) 表示 n 个人进行报数时，每报到 m 时杀掉那个人，最终的编号，f(n?1,m) 表示，n-1 个人报数，每报到 m 时杀掉那个人，最终胜利者的编号。有了递推公式后即可使用递归的方式实现。
4.2 递归代码实现
4.3 迭代代码实现
实际应用
比如你们公司需要团建，你可以设计这个游戏，根据游戏人数的多少，将你和你心仪的妹子安排在合适的座位上，一同进最后的决赛圈~
怎样用vb实现约瑟夫环算法？
用面向过程的编程方式（C），对某个给定的n=8与m=3，给出被淘汰出列的旅客编号，以及最终的幸存者。
用面向对象的编程风格（C++），重新处理该约瑟夫问题。
谈谈这两种编程风格的优点。
二、用C语言解约瑟夫问题
1、单链表的创建与输出
#include<stdio.h>
#include<malloc.h>
#define NULL 0
struct node{ /*定义结构体*/
int data;
struct node *next;
};
typedef struct node NODE;/*将该结构体设置成自定义类型*/
NODE *head;/*定义一个指向该结构体的头指针*/
NODE *create(int n)/*创建具有n个结点的单链表*/
{
NODE *p;
int i=1;
head=(NODE *)malloc(sizeof(NODE));
head->next=NULL;
while(i<=n)
{
p=(NODE *)malloc(sizeof(NODE));
p->data=n+1-i;
p->next=head->next;
head->next=p;
i++;
}
return(head);
}
void output(NODE *point)/*输出该链表数据域内的值*/
{
NODE *p;
p=point->next;
while(p!=NULL)
{
printf(“%d “,p->data);
p=p->next;
}
printf(“n”);
}
如果我们写一段main()函数
void main()
{
head=create(8);
output(head);
}
便可以完成创建和输出单链表的工作。
如果将上述创建单链表与输出单链表的工作保存为头文件link1.h,那么在今后需要创建输出类似的单链表时，只需写以下主函数即可。
#inlucde “link1.h”
void main()
{
head=create(8);
output(head);
}
2、循环单向链表的创建与输出
明白了带头指针的单向链表的创建与输出，只需作简单修改便可处理循环单向链表的相关问题。这里我们建立一个新的头文件link2.h，它包含以下几段代码。
#include<stdio.h>
#include<malloc.h>
struct node{
int data;
struct node *next;
};
typedef struct node NODE;
NODE *head;
NODE *create(int n)
{
NODE *p;
int i=1;
p=head=(NODE *)malloc(sizeof(NODE));
head->next=head;/*造循环链表时头指针的指针域设置*/
while(i<=n)
{
p->data=n+1-i;
p->next=head->next;
head->next=p;
i++;
p=(NODE *)malloc(sizeof(NODE));
}
return(head);
}
void output(NODE *point,int n) /*n表示欲输出多少个结点，由于该链表是循环的，可输出无穷项*/
{
NODE *p;
int i=1;
p=point->next;
while(i<=n)
{
printf(“%d “,p->data);
p=p->next;
i++;
}
printf(“n”);
}
3、在循环链表中删除结点并输出被删结点的相关信息
在头文件link2.h中增添新函数del(int n,int m),这里的形参n代表起始结点，m代表报数值。
void del(int n,int m)
{
int i;
NODE *p,*q;
p=head;
/*将指针移到起始结点，即第n个结点*/
i=0;
while(i<n)
{
p=p->next;
i++;
}
/*删除满足报数值的结点*/
while(p->next!=p)
{
i=1;
while(i<m)/*找到符合报数值结点的前一个结点,即第m-1个结点*/
{
p=p->next;
i++;
}
/*先输出，后删除*/
q=p->next;
printf(“%d “,q->data);
p->next=q->next;
free(q);
}
printf(“nonly one %d”,p->data);/*输出仅剩的结点*/
}
4、解决约瑟夫问题的主函数
#include <link2.h>
void main()
{
/*number结点个数,item输出结点的个数,location报数的起始位置,callnum报数值*/
int number,item,location,callnum;
printf(“ninput nose number=”);
scanf(“%d”,&number);
printf(“noutput item=”);
scanf(“%d”,&item);
head=create(number);
output(head,item);
printf(“ninput location=”);
scanf(“%d”,&location);
printf(“ninput callnum=”);
scanf(“%d”,&callnum);
del(location,callnum);
}
三、以类作为结点来处理约瑟夫问题（准C++编程风格）
1、以类作结点的链表建立
#include <iostream.h>
class Node
{
private:
int data;
Node *next;
public:
Node(){data=0;next=NULL;}
void SetData(int new_data){data=new_data;}
void SetNext(Node *new_next){next=new_next;}
int GetData(){return data;}
Node *GetNext(){return next;}
};
void main()
{
Node *head=NULL,*p,*q;
for(int i=1;i<9;i++)
{
p=new Node;
p->SetData(i);
if(head==NULL)
head=p;
else
q->SetNext(p);
q=p;
}
q=head;
do
{
cout<<“该游客编号为:”<<q->GetData()<<endl;
q=q->GetNext();
}while(q!=NULL);
q=head;
do
{
q=q->GetNext();
delete head;
head=q;
}while(q!=NULL);
}
2、以类作结点的循环链表的建立
#include <iostream.h>
class Node
{
private:
int data;
Node *next;
public:
Node(){data=0;next=NULL;}
void SetData(int new_data){data=new_data;}
void SetNext(Node *new_next){next=new_next;}
int GetData(){return data;}
Node *GetNext(){return next;}
};
void main()
{
Node *head,*p,*q;
head=new Node;
q=p=head;
for(int i=1;i<=8;i++)
{
p->SetData(i);
p->SetNext(head);
q->SetNext(p);
q=p;
p=new Node;
}
q=head;
i=1;
do
{
cout<<“该游客编号为:”<<q->GetData()<<endl;
q=q->GetNext();
i++;
}while(i<=10);
}
3、解决约瑟夫问题
#include <iostream.h>
class Node
{
private:
int data;
Node *next;
public:
Node(){data=0;next=NULL;}
void SetData(int new_data){data=new_data;}
void SetNext(Node *new_next){next=new_next;}
int GetData(){return data;}
Node *GetNext(){return next;}
};
void main()
{
Node *head,*p,*q;
head=new Node;
q=p=head;
for(int i=1;i<=8;i++)
{
p->SetData(i);
p->SetNext(head);
q->SetNext(p);
q=p;
p=new Node;
}//
p=head;
i=1;
while(i<=8)
{
cout<<p->GetData()<<” “<<endl;
p=p->GetNext();
i++;
}//输出
cout<<endl;
p=head;
while(p->GetNext()!=p)
{
i=1;
while(i<2)
{
p=p->GetNext();//将欲删除点的前一个结点
i++;
}
q=p->GetNext();
cout<<q->GetData()<<endl;//删除循环链表上的结点
p->SetNext(q->GetNext());//将q指针域所指结点的地址赋给p的指针域
p=p->GetNext();
delete q;
}//做循环数数出局游戏
cout<<“nLast One “<<p->GetData()<<endl;
}
四、用标准的面向对象编程风格处理约瑟夫问题（C++编程风格）
//#include “stdafx.h”
#include “iostream.h”
//#define NULL 0
class Node
{
private:
int data;
Node *next;
public:
Node(){data=0;next=NULL;}
Node *Create(int n);//创建含n个结点的循环链表
void Output(Node *p,int n);//输出循环链表头结点为p的后n个结点的信息
Node *Move(Node *p,int n);//将头结点指针前移到n
//从头结点为p的循环链开始，所用的计数为n进行约瑟夫实验
void Josephus(Node *p,int n);
};
Node *Node::Create(int n)
{
Node *head,*p,*q;
head=new Node;
q=p=head;
for(int i=1;i<=n;i++)
{
p->data=i;
p->next=head;
q->next=p;
q=p;
p=new Node;
}
return head;
};
void Node::Output(Node *p,int n)
{
int i=1;
while(i<=n)
{
cout<<p->data<<” “;
p=p->next;
i++;
}
};
Node *Node::Move(Node *p,int n)
{
if(n>1)
{
int i=1;
while(i<n)
{
p=p->next;
i++;
}
}
return p;
};
void Node::Josephus(Node *p,int n)
{
Node *q;
while(p->next!=p)
{
p=Move(p,n-1);
q=p->next;
cout<<q->data<<” “;
p->next=q->next;
p=p->next;
delete q;
}
cout<<“nLast One “<<p->data<<endl;
};
void main()
{ Node A,*head;
head=A.Create(8);
cout<<“nCirclist is “;
A.Output(head,10);
head=A.Move(head,1);
cout<<“nJosephus result is “<<endl;
A.Josephus(head,3);
}
五、对两种编程风格的评述
在进行面向过程的程序设计时，一般首先考虑程序所要实现的功能，然后设计为实现这些功能所必须采取的步骤，这些步骤就是过程。如果一个过程比较复杂而不能直接使用已有的抽象进行实现，则对这个过程进行分解，使分解之后的每一步（更低级的过程）能够直接对应着一条语句。通过将分解之后的一系列过程封装在一个函数抽象中，程序员在特定的时刻只关心有限的细节，这个新的函数抽象比其较低级的抽象更接近问题求解的过程，因而，能够很好地映射问题求解中的过程。如果这个过程出现在许多问题求解中，那么，这个函数抽象就可能被重复利用。
函数是面向过程程序设计的基础，按照结构化程序设计的思想，又可将完成某一复杂工作的函数放在一个头文件，便于我们多次复用。
面向过程的程序设计方法与面向对象的程序设计方法的根本区别在于对待数据和函数的关系上。
在面向过程的程序设计中，数据只被看作是一种静态的结构，它只有等待调用函数来对它进行处理。
在面向对象的程序设计中，将数据和对该数据进行合法操作的函数封装在一起作为一个类的定义。另外，封装还提供了一种对数据访问严格控制的机制。因此，数据将被隐藏在封装体中，该封装体通过操作接口与外界交换信息。
面向对象的思想需要在实践中不断摸索和体会，在以后的程序设计中，可主动运用这种思想去实践。
