C++ 新约瑟夫问题

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int n,sum=0,j,i,k,lpl,a[100000],b[100000];
    cin>>n;
    a[1]=1,b[1]=1;        
    for(int i=2;i<=n;i++)
    {
            a[i]=(a[i-1]+1)%i+1;
    if(a[i]==i)b[i]=i;
    else b[i]=b[a[i]];
    }
    cout<<b[n]+n; 
}

又是一道递推  代码如上；

试题描述：

你一定听说过经典“约瑟夫”问题吧？现在来组织一个皆大欢喜的新游戏：假设 n 个人站成一圈，从第 1 人开始交替的去掉游戏者，但只是暂时去掉（例如，首先去掉 2），直到最后剩下唯一的幸存者为止。幸存者选出后，所有比幸存者号码高的人每人将得到 1 块钱，并且永久性地离开，其余剩下的人将重复以上过程，比幸存者号码高的人每人将得到 1 块钱后离开。一旦经过这样的过程后，人数不再减少，最后剩下的那些人将得到 2 块钱。请计算一下组织者一共要付出多少钱？

例如，第一轮有 5 人，幸存者是 3，所以 4、5 得到 1 块钱后离开，下一轮幸存者仍然是 3，因此没有人离开，所以每人得到 2 块钱，总共要付出 2+2*3=8 块钱。

输入：

一行一个整数 n。

输出：

一行一个整数，不超过65535，表示总共要付出多少钱。

输入实例:

10

输出实例：

13

首先，每个人都会得到1块钱，只有最后的那些幸存者多得到了1块钱。所以只要求出最后会幸存的人即可。

假设经过m次出圈操作后还剩final(m)个人，此时的人数已经不可以再减少了，则问题的解应该为final(m)+n.可是如何求final(m)呢？

当第i次的final(i)=i时，人数就不会再减少了，此时的i即为m，否则，就需要对剩下的final(i)个人再进行报数出圈操作；

会有两种情况：1 设jose(i)为幸存者的编号，设报道K的人出去，则jose(i-1)可以理解为第一轮第一次报数，k出去后的状态，k出去后会从k+1继续报数，此时圈中有i-1个人，从k+1开始报数，编号jose(i)为：k+1，K+2......i，1,2.....,k-1;

                          2 可以人为地把这个圈逆时针转k个单位，此时报数的编号jose（i-1）：1,2.....,i-k,i-k+1,i-k+2....,i-1;

从上面两种情况可以发现除了i和i-k以外，其他所有数据都满足规律：jose(i)=(jose(i-1)+k)mod i。对这个式子稍微调整一下，变成的公式都满足了：jose(i)=(jose(i-1)+1）mod i+1;

至此这个问题的递推公式就出来了，边界条件为jose(1)=1.然后，顺推求出每个jose(i),直到某一次jose(i)=i,则final(i)=i,否则final(i)=final(jose(i)).

所以就是这样了！！！

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有