【数据结构与算法】七 █约瑟夫环█ 二动态规划

女爷i 2022-08-20 15:12 69阅读 0赞

# **【数据结构与算法】七 █约瑟夫环█ 二 动态规划** #

--------------------

上一章节我们提到约瑟夫环拥模拟现实来实现，这一节我们来用动态规划来解决这一问题。。。

# **背景** #

约瑟夫环

约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号0, 1，2，3…n-1分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从0开始报数，数到m-1的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

--------------------

# **思路** #

我们知道第一个人(编号一定是(m-1)%n) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）: 　　 k k+1 k+2 … n-2, n-1, 0, 1, 2, … k-2 　　并且从k开始报0。现在我们把他们的编号做一下转换

> k –> 0 　　k+1 –> 1 　　k+2 –> 2  
> n-1 –> n-1-k 0–> n-k  
> … … 　　
> 
> k-3 –> n-3 　　k-2 –> n-2
> 
> 序列1： 1, 2, 3, 4, …, n-2, n-1, n
> 
> 序列2： 1, 2, 3, 4, … k-1, k+1, …, n-2, n-1, n
> 
> 序列3： k+1, k+2, k+3, …, n-2, n-1, n, 1, 2, 3,…, k-2, k-1 　　
> 
> 序列4：1, 2, 3, 4, …, 5, 6, 7, 8, …, n-2, n-1

变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：

> ∵ k=m%n; 　　
> 
> ∴x’ = x+k = x+ m%n ; 而 x+ m%n 可能大于n
> 
> ∴x’= (x+ m%n)%n = (x+m)%n 　　得到 x‘=(x+m)%n

如何知道(n-1)个人报数的问题的解?对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 —- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：令f表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f\[n\].

> 递推公式: 　　f\[1\]=0;　　f\[i\]=(f\[i−1\]\+m)

--------------------

# **实现** #

C++

#include <iostream>
    
    using namespace std;
    
    int main(){
        int n=10, m=3,i, f[11]={0};
        for(i=1;i<=n;i++){
            f[i]=(f[i-1]+m)%i;
            printf("i=%d    f[i]=%d    i-1=%d    f[%d]=%d    %d+%d=%d%%%d=%d  \n", i, f[i], i-1, i-1, f[i-1], f[i-1] , m, f[i-1] + m , i , f[i]);
            for(int j=0;j<=n;j++)
                printf("index%d=%d     ", j ,f[j]);
            printf("\n\n");
        }
        printf("\n");
        printf("The winner is %d\n", f[n]);
    
        return 0;
    }

我们来看运行结果,我们在代码中加入了log日志有助于我们理解。  
现在在来理解这句话是不是就容易多了。  
**如何知道(n-1)个人报数的问题的解?对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 —- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：令f表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f\[n\].**  
![这里写图片描述][20160304010721608]

--------------------

# **简单优化** #

好的现在我们只计算最后的胜利者，我们也不用打印出Log , 我们可以优化之前的代码。

#include <iostream>
    using namespace std;
    
    int main(void){
        int n=10, m=3,i, s=0;
        for(i=1;i<=n;i++)
        {
            s=(s+m)%i;
        }
        printf("The winner is %d\n", s);
    }

--------------------

# **最后** #

通过上面一些简单的讲解，  
相信朋友们已经知道其原理及特性了。  
本人能力有限,  
如发现错误或不合理欢迎指正…

--------------------

[20160304010721608]: /images/20220731/e5f33764f0cf46c0a4aa27f7af7f8ce7.png