欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C++ 新约瑟夫问题

程序员文章站 2023-04-08 09:13:55
又是一道递推 代码如上; 试题描述: 你一定听说过经典“约瑟夫”问题吧?现在来组织一个皆大欢喜的新游戏:假设 n 个人站成一圈,从第 1 人开始交替的去掉游戏者,但只是暂时去掉(例如,首先去掉 2),直到最后剩下唯一的幸存者为止。幸存者选出后,所有比幸存者号码高的人每人将得到 1 块钱,并且永久性地 ......
#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)).

所以就是这样了!!!