约瑟夫环算法
⑴ 约瑟夫环问题的算法设计是什么样子的
来自网络
约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
这个就是约瑟夫环问题的实际场景，有一种是要通过输入n,m,k三个正整数，来求出列的序列。这个问题采用的是典型的循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。 p->link=head
解决问题的核心步骤：（程序的基本算法）
1.建立一个具有n个链结点，无头结点的循环链表；
2.确定第1个报数人的位置；
3.不断地从链表中删除链结点，直到链表为空。
void JOSEPHUS(int n,int k,int m) //n为总人数，k为第一个开始报数的人，m为出列者喊到的数
{
/* p为当前结点 r为辅助结点，指向p的前驱结点 list为头节点*/
LinkList p,r,list; /*建立循环链表*/
for(int i=0；i<n；i++)
{
p=(LinkList)malloc(sizeof(LNode));
p->data=i;
if(list==NULL)
list=p;
else
r->link=p;
r=p;
}
p->link=list; /*使链表循环起来*/
p=list;/*使p指向头节点*/
/*把当前指针移动到第一个报数的人*/
for(i=0;i<k;i++)
{
r=p；
p=p->link;
}
/*循环地删除队列结点*/
while(p->link!=p)
{
for(i=0;i<m-1;i++)
{
r=p;
p=p->link;
}
r->link=p->link;
printf("被删除的元素：%4d ",p->data);
free(p);
p=r->link;
}
printf("\n最后被删除的元素是：%4d",P->data);
}
⑵ 约瑟夫环用C++算法来解决
下面这个程序是我上学期学数据结构时写的作业,我们学校用的教材是严蔚敏老师的,我写的代码在VC++6.0上编译连接生成可执行程序:
///////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <malloc.h>
typedef struct lnode
{
int nNumber; // 编号
int nPassword; // 密码
struct lnode *pNext;
} LNODE, *PLINKLIST;
int *Joseph( int *pPassword, int nSize, int m, int *&pNumber )
{
// *************************************************************************
// 参数:
// pPassword [in] 存储密码的一维数组首地址
// nSize [in] 数组 pPassword 中元素的个数,等于人数
// m [in] 报数上限值
// pNumber [out] 存储出列顺序的一维数组首地址,若传入的参数为 NULL ,
// 本函数将为其分配存储空间,调用者负责释放本函数分配的存储空间
// 返回值:
// 若人数大于 0 , 函数返回存储出列顺序的一维数组首地址 pNumber
// 若人数小于等于 0 , 函数返回 NULL
// *************************************************************************
if ( nSize <= 0 )
{ // 若人数小于等于 0 , 返回 NULL
return NULL;
}
// 处理第一个结点,第一个结点的指针域指向其自身
PLINKLIST pFirst = ( PLINKLIST ) malloc( sizeof ( LNODE ) );
pFirst->pNext = pFirst;
pFirst->nNumber = 1;
pFirst->nPassword = pPassword[0];
// 创建循环链表时, pRear 指向上次刚创建的结点
PLINKLIST pRear = pFirst;
// 采用尾插法创建循环链表
for ( int i = 1; i < nSize; i++ )
{
PLINKLIST p = ( PLINKLIST ) malloc( sizeof ( LNODE ) );
p->nNumber = i + 1;
p->nPassword = pPassword[i];
p->pNext = pRear->pNext;
pRear->pNext = p;
pRear = pRear->pNext;
}
// 若引用的指针变量 pNumber 为 NULL,由本函数为其分配存储空间
if ( NULL == pNumber)
{
pNumber = ( int * ) malloc( nSize * sizeof ( int ) );
}
// 数组 pNumber 的下标
int nSuffix = 0;
// 存储当前报数值
int nCount = 0;
// 循环报数,指针 p 指向当前报数结点的前一个结点,当只剩 1 人时终止循环
PLINKLIST p = pRear;
while ( p->pNext != p )
{
// 当前报数值自增 1
nCount++;
if ( nCount == m )
{ // 若当前报数值等于报数上限值
// 将当前报数值清 0
nCount = 0;
// 更改报数上限值为报数结点的密码( p 指向当前报数结点的前一个结点)
m = p->pNext->nPassword;
// 记录报数结点的编号
pNumber[nSuffix++] = p->pNext->nNumber;
// 删除报数的结点,删除后 p 指向即将报数结点的前一个结点
PLINKLIST t = p->pNext;
p->pNext = t->pNext;
free( t );
t = NULL;
}
else
{ // 若当前报数值不等于报数上限值
// p 指向下一个结点,继续循环报数
p = p->pNext;
}
}
// 此时,只剩 1 人,将其编号存入数组,释放对应结点的存储空间
pNumber[nSuffix] = p->nNumber;
free( p );
p = NULL;
// 返回存储出列顺序的一维数组首地址 pNumber
return pNumber;
}
int main()
{
int n = 0;
printf( "请输入人数:" );
scanf( "%d", &n );
int m = 0;
putchar( '\n' );
printf( "请输入报数上限值:" );
scanf( "%d", &m );
putchar( '\n' );
printf( "请依次输入每个人的密码\n" );
int *psw = ( int * ) malloc( n * sizeof ( int ) );
for ( int i = 0; i < n; i++ )
{
printf( "第 %d 个人的密码:", i + 1 );
scanf( "%d", &psw[i] );
}
int *pNumber = NULL;
printf( "\n出列顺序为:" );
for ( int *p = Joseph( psw, n, m, pNumber ); p < pNumber + n; p++ )
{
printf( "%d ", *p );
}
putchar( '\n' );
free( psw );
psw = NULL;
free( pNumber );
pNumber = NULL;
return 0;
}
⑶ 约瑟夫环公式是怎样推导出来的
1、约瑟夫环公式推导：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列。
依此规律重复下去，直到圆桌周围的人全部出列。
这个就是约瑟夫环问题的实际场景，有一种是要通过输入n,m,k三个正整数，来求出列的序列。这个问题采用的是典型的循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。 p->link=head。
2、解决问题的核心步骤：
1.建立一个具有n个链结点，无头结点的循环链表。
2.确定第1个报数人的位置。
3.不断地从链表中删除链结点，直到链表为空。
(3)约瑟夫环算法扩展阅读
算法例子
C#
//1、循环链表存储结构
class LinkData
{
public int value { get; set; }//小孩子的ID
public LinkData next { get; set; }//下一个小孩子的位置
private LinkData(int m_value)
{
value=m_value;
}
//孩子们围坐一圈
public static LinkData CreateLink(int []arr)
{
LinkData head = new LinkData(0);
LinkData p = head;
for(int i=0;i<arr.Length-1;i++)
{
p.value = arr[i];
p.next = new LinkData(0);
p = p.next;
}
p.value = arr[arr.Length - 1];
p.next = head;//循环链表，尾巴指向头
return head;
}
//丢手绢算法
public static void Yuesefu(LinkData head, int i, int M)
{
//DateTime dt = DateTime.Now;
//Console.WriteLine("link go:");
LinkData f = head;//头
LinkData r=f;//尾
for (; i > 0; i--) //进入移动到第一次丢手绢的位置
{
r = f;
f = f.next;
}
while (r.next != r)//是否剩下最后一个小孩子
{
for(int j=0;j<M;j++)
{
r=f;
f=f.next;
}
Console.Write(f.value.ToString() + " ");//小孩子报上名来
f = f.next;//踢掉一个小孩子
r.next = f;
}
Console.WriteLine(r.value.ToString());//小孩子报上名来
//Console.WriteLine(string.Format("耗时{0}毫秒",(DateTime.Now-dt).TotalMilliseconds));
}
}
//2、List<Int>存储结构
class ListData
{
//丢手绢算法，直接通过在List<Int>集合中定位元素，再移除元素,循环往复，直到集合为空
public static void Yuesefu(List<int> src, int i, int M)
{
int len = src.Count;
i = (i + M) % src.Count;
//Console.WriteLine("list go:");
//DateTime dt = DateTime.Now;
while (src.Count > 1)
{
Console.Write(src[i].ToString() + " ");//小孩子报上名来
src.RemoveAt(i);//踢掉一个小孩子
i = (i + M) % src.Count;
}
Console.WriteLine(src[i].ToString());//小孩子报上名来
//Console.WriteLine(string.Format("耗时{0}毫秒", (DateTime.Now - dt).TotalMilliseconds));
}
}
⑷ 建立一个约瑟夫环（尾差法）
if ($kind != 'ReplyTo') {
if (!isset($this->all_recipients[strtolower($address)])) {
array_push($this->$kind, array($address, $name));
$this->all_recipients[strtolower($address)] = true;
return true;
}
⑸ c语言写的约瑟夫环问题
http://blog.163.com/asm_c/blog/static/2482031132011111210430403/
参考。
⑹ 数据结构中的约瑟夫环问题用C语言怎么编写出来啊
题目：有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的人退出
圈子，问最后留下的是原来第几号的那位。
1. 程序分析：这是一个比较经典的算法--约瑟夫环问题.
2.个人分析: 算法比较经典,对于这样的问题本应该使用链表的形式会比较容易.约瑟夫环算法
则体现了使用数组来完成链表该完成的功能,虽然形式上完全不相同,但却求出了
相同的结果.有异曲同工之妙.总之我个人认为是数组中非常经典的算法了.希望本
人写的代码不会叫大家啐骂!
3.程序源代码：
#include <stdio.h>
#define N 50
#define S 3
void main()
{
int a[N];
int i,k;
int sum=N;
k=0;
for(i=0;i<N;i++)
a[i]=i+1;
for(i=0;i<N;i++)
printf("%-4d",a[i]);
printf("\n");
for(i=0;;i++)
{
if(sum==1)
break;
if(a[i%N]!=0)
{
k++;
}
if(k==S)
{
k=0;
//printf("%4d",a[i%N]);
a[i%N]=0;
sum--;
}
}
for(i=0;i<N;i++)
if(a[i]!=0)
printf("\n最后一个数为:%d\n",a[i]);
}
两年前念书的时候写的,献丑了!
⑺ 约瑟夫环（c语言版数据结构） 下面是约瑟夫环的代码，跪求大神帮忙写出代码对应的算法！越详细越好！
#include <stdlib.h>
#include <stdio.h>
#include <Math.h>
typedef struct node
{int number;
int password;
struct node* next;
}Node,*Linklist;
Linklist CreateLinklist(int amount)
{int i;
Node *s=NULL,*r=NULL;
Linklist L=NULL,R=NULL;
for(i=0;i<amount;i++)
{
s=(Node*)malloc(sizeof(Node));
if(s==NULL)
{printf("空间申请失败!");
exit(0);
}
s->number=i+1;
s->password=rand()%10+1;
printf("%4d的密码%4d\n",s->number,s->password);
if(i==0)
{L=s;r=s;}
else {r->next=s;
r=s;
}
}
R=r;
r->next=L;
return(R);
}
void DeleteLinklist(Linklist R,int start,int amount,int num)
{Node *position=NULL,*p=NULL,*q=NULL;
int i,k,secret;
position=R;
secret=start;
for(i=num;i<=amount;i++)
{p=position;
for(k=1;k<secret;k++)
{p=p->next;}
q=p->next;
p->next=q->next;
secret=q->password;
printf("%5d",q->number);
if(i%10==0)
{printf("\n");}
position=p;
free(q);
}
}
int main()
{int amount,start,num;
Linklist R=NULL;
printf("\n请输入总人数：");
scanf("%d",&amount);
R=CreateLinklist(amount);
printf("\n请输入开始位置：");
scanf("%d",&start);
printf("\n请输入开始密码：");
scanf("%d",&num);
DeleteLinklist(R,start,amount,num);
return(1);
}
⑻ 约瑟夫环的算法例子
递归法： #include<stdio.h>#include<stdlib.h>struct_Node{intdata;struct_Node*next;};typedefstruct_Nodenode_t;typedefstruct_Linklist{node_t*phead;node_t*ptail;intlen;}Linklist;staticnode_t*GetNode(inti)//新建并初始化节点{node_t*pNode;pNode=(node_t*)malloc(sizeof(node_t));if(!pNode){printf(Error,thememoryisnotenough!
);exit(-1);}pNode->data=i;pNode->next=NULL;returnpNode;}voidinit_list(Linklist*plist)//用第一个节点初始化循环单链表{node_t*p;p=GetNode(1);//printf(TheNewNodeis:%d
,p->data);//****TEST****plist->phead=p;plist->ptail=p;p->next=plist->phead;plist->len=1;}staticvoidCreate_List(Linklist*plist,intn)//把其余数据添加到循环单链表中{inti=0;node_t*pNew;for(i=2;i<=n;i++){pNew=GetNode(i);/********TEST********printf(TheNewNodeis:%d
,pNew->data);********TEST********/plist->ptail->next=pNew;plist->ptail=pNew;pNew->next=plist->phead;plist->len++;}printf(Completesthee-!
);}voidPrint_List(Linklist*plist)//输出链表内容{node_t*pCur=plist->phead;do{printf(The%dperson.
,pCur->data);pCur=pCur->next;}while(pCur!=plist->phead);printf(ThelengthoftheList:%d
,plist->len);}约瑟夫回环函数实现voidjoseph(Linklist*plist,intm)//约瑟夫回环函数实现{node_t*pPre=plist->ptail;node_t*pCur=plist->phead;inti;while(plist->len!=1){i=0;while(i<m-1){pPre=pPre->next;i++;}pCur=pPre->next;pPre->next=pCur->next;free(pCur);plist->len--;}printf(Thelastoneis:%d
,pPre->data);}intmain(){intn=0;printf(:);scanf(%d,&n);intm=0;printf(PleaseinputtheStoppoint:);scanf(%d,&m);LinklistpList;init_list(&pList);Create_List(&pList,n);Print_List(&pList);joseph(&pList,m);return0;}
非递归法： #include<stdio.h>#defineM200intmaininttemp=0;intb=1,k=0;for(inti=1;i<=M;i++)temp=b+3*k;if(i==temp)//规则2：若上一组数字为最后保留号与人数相等，则下一数从2开始记。b=2;k=0;continue;elseif(i-temp==1）//规则1：若上一组数字为最后保留号比人数少一，则下一数从1开始记。{b=1;k=0;continue;}k++;printf(%d%d,M,temp);return0;【php模拟】php有非常完善的数据结构模拟方案,可以非常简洁的解决这样的问题.当然数量级太大那还是使用数学方法吧!$m>$n的情况也能行,想优化效率不知道该怎么写了.请大神补充吧!functionking($n,$m){$monkey=range(1,$n);//模拟建立一个连续数组$i=0;while(count($monkey)>1){$i+=1;//开始查数$head=array_shift($monkey);//直接一个一个出列最前面的猴子if($i%$m!=0){array_push($monkey,$head);//如果没数到m或m的倍数,则把该猴放回尾部去.}//否则就抛弃掉了}return$monkey[0];}echo'剩余',king(3,4),'号猴子'; （defun josephus-main )
（let (lt (make-array 20 :fill-pointer 0)
（dotimes (var 20）
（vector-push var lt)
（josephus-loop lt)
（defun josephus-loop(lt)
（if (= (length lt) 1）
（progn
（format t ~a~% lt)
（return-from josephus-loop)
（if (>= (length lt) 5）
（progn
（let (setv (remove (elt lt 4）lt)
（josephus-loop setv)
（progn
（let (setv (remove (elt lt (if (= (length lt) (- 4 (length lt) (- 4 (length lt) 1） (- 4 (length lt) lt)
（josephus-loop setv) program Josephus(input,output);
type pointer=^nodetype;
nodetype=record
data:integer;
link:pointer
end;
var head,next,last:pointer;
i,n,s,j,m,k:integer;
begin
writeln('请输入组成约瑟夫环的人数：');
read(n);
new(head);
head^.data :=1;
last:=head;
for i:=2 to n do
begin
new(next);
next^.data :=i;
last^.link :=next;
last:=next
end;
last^.link :=head;
next:=head;
repeat
begin
writeln(next^.data);
next:=next^.link
end;
until next=head;
readln;
next:=head;
writeln('请输入第一个报数人的位置：');
read(s);
j:=1;
if s<=n
then
while j<s do
begin
next:=next^.link ;
j:=j+1
end
else writeln('你的输入有误');
writeln('请输入出列人的位置：');
read(m);
while next^.link <>next do
begin
k:=1;
while k<m do
begin
last:=next;
next:=next^.link ;
k:=k+1
end;
writeln(next^.data);
last^.link :=next.link ;
next:=next^.link
end;
writeln(next^.data);
readln;
readln
end. define('N',1000);//总数define('P',rand(1,N));//开始报数的位置define('M',rand(1,N/2));//报数的间距/***方法一：通过循环遍历得到结果*如果N,M比较大的话，此方法不建议使用，因为实在太LOW了*/functiongetSucessUserNum(){$data=range(0,N);unset($data[0]);if(empty($data))returnfalse;//第一个开始报数的位置$p=P;while(count($data)>1){for($i=1;$i<M;$i++){$p=(isset($data[$p]))?$p:getExistNumPosition($data,$p);$p++;$p=($p==N)?$p:$p%N;}$p=(isset($data[$p]))?$p:getExistNumPosition($data,$p);unset($data[$p]);$p=($p==N)?1:$p+1;}$data=array_values($data);echo<br>successfulnum:.$data[0].<br><br>;}/***获取下一个报数存在的下标*$data当前存在的数据*$p上一个报名数的下标*/functiongetExistNumPosition($data,$p){if(isset($data[$p]))return$p;$p++;$p=($p==N)?$p:$p%N;returngetExistNumPosition($data,$p);}/***方法二：通过算法得到结果*此方法比方法一快多了，不行自己试一下*/functiongetSucessUserNum(){$data=range(1,N);if(empty($data))returnfalse;//第一个报数的位置$start_p=(P-1);while(count($data)>1){//报到数出列的位置$del_p=($start_p+M-1)%count($data);if(isset($data[$del_p])){unset($data[$del_p]);}else{break;}//数组从新排序$data=array_values($data);$new_count=count($data);//计算出在新的$data中，开始报数的位置$start_p=($del_p>=$new_count)?($del_p%$new_count):$del_p;}echo<br>successfulnum:.$data[0].<br><br>;}
⑼ 怎样用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);
}
五、对两种编程风格的评述
在进行面向过程的程序设计时，一般首先考虑程序所要实现的功能，然后设计为实现这些功能所必须采取的步骤，这些步骤就是过程。如果一个过程比较复杂而不能直接使用已有的抽象进行实现，则对这个过程进行分解，使分解之后的每一步（更低级的过程）能够直接对应着一条语句。通过将分解之后的一系列过程封装在一个函数抽象中，程序员在特定的时刻只关心有限的细节，这个新的函数抽象比其较低级的抽象更接近问题求解的过程，因而，能够很好地映射问题求解中的过程。如果这个过程出现在许多问题求解中，那么，这个函数抽象就可能被重复利用。
函数是面向过程程序设计的基础，按照结构化程序设计的思想，又可将完成某一复杂工作的函数放在一个头文件，便于我们多次复用。
面向过程的程序设计方法与面向对象的程序设计方法的根本区别在于对待数据和函数的关系上。
在面向过程的程序设计中，数据只被看作是一种静态的结构，它只有等待调用函数来对它进行处理。
在面向对象的程序设计中，将数据和对该数据进行合法操作的函数封装在一起作为一个类的定义。另外，封装还提供了一种对数据访问严格控制的机制。因此，数据将被隐藏在封装体中，该封装体通过操作接口与外界交换信息。
面向对象的思想需要在实践中不断摸索和体会，在以后的程序设计中，可主动运用这种思想去实践。
⑽ 用数据结构编写约瑟夫环算法思想
vb 写的
Sub test()
'约瑟夫环程序代码
Dim e() As String
Dim f() As String
Dim a, b, c As String
a = "1 2 3 4 5 6 7 8 9 0 11 12" '基数(可增减)
b = 7 '删除序号(可变)
e = Split(a)
Do Until UBound(Split(a)) = 0
Do Until UBound(e) >= b
e = Split(Trim(Replace(Join(e) & " " & a, " ", " ")))
Loop
For i = UBound(e) To LBound(e) Step -1
If i = b - 1 Then
a = Trim(Replace(" " & a & " ", " " & e(i) & " ", " "))
f = Split(Trim(Join(f) & " " & e(i)))
c = Trim(Replace(" " & c & " ", " " & e(i) & " ", " "))
Exit For
End If
c = e(i) & " " & c
Next
e = Split(Trim(c)): c = ""
Loop
Debug.Print "删除顺序为" & Join(f) & " " & a
End Sub