主题：请各位大侠帮我看一下这个程序
ndcjhba
[专家分：0] 发布于 2010-05-13 23:34:00
题目是:用数组求解约瑟夫问题，有N个小孩围在一起按顺时钟报数，报到M的小孩从圈子中离开，然后从下一个小孩开始报数，每报到M相应的小孩从圈子中离开，最后一个离开圈子的人为胜者，问胜者是哪一个小孩？
#include<iostream>
using namespace std;
const int N=20,M=5;
int main()
{int children[N],count=1,children_remaind=M,i=0;
for(i=0;i<N;i++)
children[i]=i+1;
while(children_remaind>1)
{for(i=0;children_remaind>1;i++,count++)
{if(count==M)
{for(int m=i;m<children_remaind-1;m++)
children[m]=children[m+1];
children_remaind--;
}
count=1;
if(i>=children_remaind-1)
i=0;
}
}
cout<<" the winner is No."<<children[0]<<endl;
}
回复列表 （共4个回复）
沙发
zlongxielinhua [专家分：0] 发布于 2010-05-15 15:07:00
//用java写的
//我的思路是这样的：
//1、初始化小孩编号
//2、初始化小孩是否离队标志,这个数组大小为2倍元素数组大小，这样做是为了不再需要每次重建新的数组
//3、生成一个数组用于存放离开小孩的编号。最后进数组的那个小孩是赢家。
//4、每次检验从startId开始到start+20为止的小孩
//5、找出第key个没离队小孩(标记不为-1)
//6、将这个小孩所在位置的标记置为编号
//7、修改startId
//8、直到remainChild比key小 退出循环
板凳
zlongxielinhua [专家分：0] 发布于 2010-05-15 15:08:00
class Game
{
static int lastChildren(int total, int key)
{
if (total <= 0 || key <= 0 || key > total)
{
return 0;
}
//初始化数据
int[] child = new int[total];
for (int i = 0; i < child.length; i++)
{
child[i] = i+1;
}
int[] childFlag = new int[2 * total];
for (int i = 0; i < childFlag.length; i++)
{
childFlag[i] = -1;
}
int[] leaveChildID = new int[total];
int leaveNum = -1;
int remainChildNum = total;
int startId = 0;
//进行离队检验
while(remainChildNum >= key)
{
int startKey = 0;
int j = startId;
//找到第key离队小孩
for(; j < startId + total; j++)
{
if (childFlag[j] == -1)
{
startKey++;
if(startKey == key)
{
break;
}
}
}
if(startKey == key)
{
int findID;
if (j >= total)
{
findID = j - total;
}
else
{
findID = j;
}
//重置标记
childFlag[findID] = child[findID];
childFlag[findID + total] = child[findID];
leaveNum++;
leaveChildID[leaveNum] = child[findID];
remainChildNum--;
//System.out.println("---------leaveChildID[leaveNum]---------" + leaveChildID[leaveNum]);
//新一轮开始
int nextStart = findID + 1;
int m = nextStart;
for(; m < nextStart + total; m++)
{
if (childFlag[m] == -1)
{
break;
}
}
if (m >= total)
{
startId = m - total;
}
else
{
startId = m;
}
}
}
return leaveChildID[leaveNum];
}
3 楼
zlongxielinhua [专家分：0] 发布于 2010-05-15 15:08:00
public static void main(String[] args)
{
System.out.println(lastChildren(20, 5));
//结果 ：
//---------leaveChildID[leaveNum]--------- 5
//---------leaveChildID[leaveNum]--------- 10
//---------leaveChildID[leaveNum]--------- 15
//---------leaveChildID[leaveNum]--------- 20
//---------leaveChildID[leaveNum]--------- 6
//---------leaveChildID[leaveNum]--------- 12
//---------leaveChildID[leaveNum]--------- 18
//---------leaveChildID[leaveNum]--------- 4
//---------leaveChildID[leaveNum]--------- 13
//---------leaveChildID[leaveNum]--------- 1
//---------leaveChildID[leaveNum]--------- 9
//---------leaveChildID[leaveNum]--------- 19
//---------leaveChildID[leaveNum]--------- 11
//---------leaveChildID[leaveNum]--------- 3
//---------leaveChildID[leaveNum]--------- 17
//---------leaveChildID[leaveNum]--------- 16
}
}
4 楼
拖拉基斯基 [专家分：0] 发布于 2010-05-22 09:43:00
赶紧站位，此时不抢更待何时
我来回复
您所在位置：