最進遇到的問題

遇到的問題文題目

思路简介：

　　　　约瑟夫问题是学链表结构时的老问题，一般用循环链表做，但由于链表解法复杂度为m*n，当m、n较大时，这种模拟运算较为浪费时间，但观察一下，可以发现其中有一些规律。

比如说m为3，n我们从2开始，如果要使某位被选中最后获胜，则其位置必定为1，即第2个人（按0、1、2数）；而当n为3时，只有位置是第2个的人才会最后获胜。

举例：下图（盗的）绿框为当n为11，m为3时，各轮元素所在位置；黄框为各轮被淘汰的元素；红框为最后一个留下的元素。

　　　　　　　　　　　　最進遇到的問題

据上表，可以这样理解，当最后一轮淘汰开始的时候各元素的位置相当于最后第二轮各元素的位置向前移动了m（即3格），而前面3格的元素除了已被淘汰的，剩下的补充的队伍后面。由此反过来可以理解：

递推公式：

f (N, M) = (f (N - 1, M) + M) % N

#include<stdio.h>
int main()
{
    int n,d;
    while(scanf("%d%d",&n,&d),n|d)
    {
        int s=0;
        for(int i=2;i<=n;i++)
        {
            s=(s+d)%i;
        }
        printf("%d %d %d\n",n,d,s+1);
    }
    return 0;
}

Input

第一行输入小孩的人数N（N<=64）
接下来每行输入一个小孩的名字(人名不超过15个字符)
最后一行输入W,S (W < N)，用逗号","间隔
Output

按人名输出小孩按顺序出列的顺序，每行输出一个人名
Sample Input

5
Xiaoming
Xiaohua
Xiaowang
Zhangsan
Lisi
2,3

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
using namespace std;
string na[65];
    int p[65];
int main()
{
    int w,s,n,i;
    char c;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>na[i];
        p[i]=i;
    }
    cin>>w>>c>>s;
    w=(w+n-1)%n;
    do
    {
        w=(w+s-1)%n;
        cout<<na[p[w]]<<endl;
        for(i=w;i<n-1;i++)
        p[i]=p[i+1];
    }while(--n);//此处一定是--n，注意do-while的区别，否则re
    return 0;
}

秒客网

最進遇到的問題

相关文章