C++的编写约瑟夫(josephus)环函数

来源:本站
导读:目前正在解读《C++的编写约瑟夫(josephus)环函数》的相关信息,《C++的编写约瑟夫(josephus)环函数》是由用户自行发布的知识型内容!下面请观看由(电工技术网 - www.9ddd.net)用户发布《C++的编写约瑟夫(josephus)环函数》的详细说明。
简介:本文给大家分享了C++的编写约瑟夫(josephus)环函数。

约瑟夫(josephus)环是这样的:假设有n个小孩坐成一个环,假如从第一个小孩开始数,如果数到m个小孩,则该小该离开,问最后留下的小孩是第几个小孩?例如:总共有6个小孩,围成一圈,从第一个小孩开始,每次数2个小孩,则游戏情况如下:

小孩序号:1,2,3,4,5,6

离开小孩序号:2,4,6,3,1

最后获胜小孩序号:5

这样的问题,我可以先考虑输入的内容有哪些?输出内容有哪些?

要求用户输入的内容有:

1、是小孩的个数,也就是n的值;

2、是离开小孩的间隔是多少?也就是m的值。

3、所有小孩的序号要求存在数组或者链表中,所以需要定义一个指针,这里我们用数组来存放小孩的序号。

而要求输出的内容是:

1、离开小孩的序号;

2、最后留下小孩的序号;

所以,根据上面分析输入输出参数,我们考虑离开小孩的序号可以直接输出,这样可以使函数的复杂性。那么函数定义如下:

//输入参数:

//Childs为指向一个整形指针,指向保存小孩数组的首地址;

//n为小孩的个数;

//m为数小孩的个数;

int Josephus(int *Child,int n,int m)

{

int i=-1,j=0,k=1;

//开始数小孩,只到留下一个小孩

while(1)

{

//数m个小孩

for(j=0;j<m;)

{

i=(i+1)%n;//取下标加1的模,当i的值在0到n-1之间循环

if(Child[i]!=-1) //小孩在环中则数数有效;

j++;

}

if(k==n)//如果k==n则表示,此时数组中只留下一个小孩,

break;//序号为Child[i]中的值,跳出循环;

cout<<Child[i]<<",";//输出离开小孩的序号;

Child[i]=-1;//离开的小孩用-1作标记

k=k+1;

}

cout<<endl;

return(Child[i]);//返回最获胜小孩的序号

}

完整的程序,在VC6中调试通过。

//-----------------------------------------------------------

#include<iostream.h>

int Josephus(int *Child,int n,int m);

void main()

{

int *allChild,j,k,l;

cin>>j>>k;

if((allChild= new int[j])!=NULL)

{

for(l=0;l<j;l++)

{

cout<<l+1<<",";

allChild[l]=l+1;

}

cout<<endl;

cout<<Josephus(allChild,j,k);

}

}

int Josephus(int *Child,int n,int m)

{

int i=-1,j=0,k=1;

while(1)

{

for(j=0;j<m;)

{

i=(i+1)%n;

if(Child[i]!=-1)

j++;

}

if(k==n)

break;

cout<<Child[i]<<",";

Child[i]=-1;

k=k+1;

}

cout<<endl;

return(Child[i]);

}

提醒:《C++的编写约瑟夫(josephus)环函数》最后刷新时间 2024-03-14 00:58:43,本站为公益型个人网站,仅供个人学习和记录信息,不进行任何商业性质的盈利。如果内容、图片资源失效或内容涉及侵权,请反馈至,我们会及时处理。本站只保证内容的可读性,无法保证真实性,《C++的编写约瑟夫(josephus)环函数》该内容的真实性请自行鉴别。