回 帖 发 新 帖 刷新版面

主题:[讨论]编写一算法解决约瑟夫问题

设有N个人为坐在圆桌周围,现从第S个人开始报数,数到第M个人出列,然后从出列的下一个人重新开始报数,数到第M个人又出列……如此重复直到所有的人全不出列为止,例如当N=8,M=4,S=1,得到的新序列为:4,8,5,2,1,3,7,6

回复列表 (共25个回复)

沙发

哪位仁兄写的现在不记得了,只记得这是本论坛的一位牛人的作品

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");    
}

板凳


这个程序不对吧,用到的知识是数据结构与算法,应该是个循环链表啊

3 楼


#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 楼

1楼的程序十分十分的精彩!!!!!!!!!!!!
顶!!!!
很巧妙

5 楼

#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 楼

有个小错误,应该把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 楼

一楼的式子需要一些步骤的证明

8 楼

一楼的这个程序是错误的,如果输入N=8,M=4的话,算出来的结果应该是4,8,5,2,1,3,7,6

9 楼


但是我去调试后得出来的结果是4,8,4,-2,-9,-16,-22,-29

10 楼


3楼,不好意思我没说清楚,用C语言编写,你用的是C++吧

我来回复

您尚未登录,请登录后再回复。点此登录或注册