主题:[讨论]编写一算法解决约瑟夫问题
人魚◎泡泡
[专家分:0] 发布于 2007-03-14 15:07:00
设有N个人为坐在圆桌周围,现从第S个人开始报数,数到第M个人出列,然后从出列的下一个人重新开始报数,数到第M个人又出列……如此重复直到所有的人全不出列为止,例如当N=8,M=4,S=1,得到的新序列为:4,8,5,2,1,3,7,6
回复列表 (共25个回复)
沙发
天边蓝 [专家分:1810] 发布于 2007-03-15 11:16:00
哪位仁兄写的现在不记得了,只记得这是本论坛的一位牛人的作品
S为1的情况
#include <stdio.h>
#include <stdlib.h>
int main( void )
{
int n, i=0, m, p;
scanf("%d%d", &n, &m);
while (++i <= n ){
p=i*m;
while( p>n )
p = p - n + (p-n-1)/(m-1);
printf("%d\n", p);
}
system("PAUSE");
}
板凳
人魚◎泡泡 [专家分:0] 发布于 2007-03-15 14:32:00
这个程序不对吧,用到的知识是数据结构与算法,应该是个循环链表啊
3 楼
qingchun1011 [专家分:90] 发布于 2007-03-16 12:17:00
#include<iostream>
#include<list>
#include<string>
using namespace std;
string f(int n,int m)
{
list<string> slist;
string sval;
while (cin >> sval)
slist.push_back(sval);
list<string>::iterator iter = slist.begin();
while(slist.size() != 1)
{
for (int i = 0; i < m-1; ++i)
{
++iter;
if (iter == slist.end())
iter = slist.begin();
}
//cout << *iter << endl;
iter = slist.erase(iter);
if (iter == slist.end())
iter = slist.begin();
}
return slist.front();
}
int main()
{
int n,m;
cin >> n >> m;
cout << f(n,m) << endl;
return 0;
4 楼
雨中飞燕 [专家分:18980] 发布于 2007-03-16 12:37:00
1楼的程序十分十分的精彩!!!!!!!!!!!!
顶!!!!
很巧妙
5 楼
wangfangbob [专家分:380] 发布于 2007-03-18 12:59:00
#include <stdio.h>
#include <stdlib.h>
int main( void )
{
int i,j,result, N, M, S;
scanf("%d%d%d", &N, &M, &S);
for ( i = 1; i <= 8; ++i )
{
for ( j = 1, result = 0; j <= i; ++j )
{
result = ( M + result ) % ( N + j - i );
result = ( 0 == result ) ? ( N + j - i ) : result;
}
result = ( result + S - 1 ) % N;
result = ( result == 0 ) ? N : result;
printf("%d\n", result );
}
system("pause");
}
6 楼
wangfangbob [专家分:380] 发布于 2007-03-18 13:03:00
有个小错误,应该把8改成N,重贴
#include <stdio.h>
#include <stdlib.h>
int main( void )
{
int i,j,result, N, M, S;
scanf("%d%d%d", &N, &M, &S);
for ( i = 1; i <= N; ++i )
{
for ( j = 1, result = 0; j <= i; ++j )
{
result = ( M + result ) % ( N + j - i );
result = ( 0 == result ) ? ( N + j - i ) : result;
}
result = ( result + S - 1 ) % N;
result = ( result == 0 ) ? N : result;
printf("%d\n", result );
}
system("pause");
}
7 楼
wangfangbob [专家分:380] 发布于 2007-03-18 20:00:00
一楼的式子需要一些步骤的证明
8 楼
人魚◎泡泡 [专家分:0] 发布于 2007-03-20 11:19:00
一楼的这个程序是错误的,如果输入N=8,M=4的话,算出来的结果应该是4,8,5,2,1,3,7,6
9 楼
人魚◎泡泡 [专家分:0] 发布于 2007-03-20 11:21:00
但是我去调试后得出来的结果是4,8,4,-2,-9,-16,-22,-29
10 楼
人魚◎泡泡 [专家分:0] 发布于 2007-03-20 11:27:00
3楼,不好意思我没说清楚,用C语言编写,你用的是C++吧
我来回复