C++ 新约瑟夫问题

2018-07-27 06:10:25来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

#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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:洛谷P1251 餐巾计划问题(最小费用最大流)

下一篇:类对象加括号与不加括号