约瑟夫问题的解法及引发的整数进制问题思考
【摘  要】：约瑟夫(Josephus)问题（也称约瑟夫斯置换，约瑟夫环问题），是一个出现在计算机科学和数学中的经典问题. 本文将就约瑟夫问题的算法复杂度优化、纯数学解法和引申出的数论进制问题进行讨论和创新，后两部分为本文研讨的重点，即离散数学中数论方面的进制问题.
【关键词】：约瑟夫(Josephus)问题，算法优化与纯数学，整数p进制及其应用.
首先让我们来回顾一下经典约瑟夫问题的表述：著名犹太历史学家约瑟夫有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人宁死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止. 约瑟夫将朋友与自己安排在第16个与第31个位置，逃过了这场死亡游戏.
将其抽象为一般数学问题（抽杀问题）则为：N(n)个人围成一圈，从第一个开始报数，第M(m)个将被杀掉，直至留下最后一个，求剩下的最后一个在原排列中的数码.
由其派生的一系列抽杀问题、猴子选王问题在本文不做讨论，重点在于引申的进制问题.
1. 算法模拟及其复杂度优化
1.1正常模拟——复杂度
题目中N个人围成一圈，因而启发我们用一个循环的链来表示. 可以使用结构数组来构成一个循环链. 结构中有两个成员，一个为指向下一个人的指针，以构成环形的链；另一个为该人是否自杀的标记，1表示未被杀. 从第一个人开始对未自杀的人进行计数，每数到9时，将结构中的标记改为0，表示该人已自杀. 这样循环计数直到剩下最后一个.
基于程序设计课试写了一段源代码，这次对其无用部分做了缩减和修改（复杂度o(nm)）：
#include<iostream>
using namespace std;
void main()
{
    int n, m, a[10001], k, i, j, num;
    cout << "n = ";
    cin >> n;
    if (n>10000)
    {
        cout << "Beyond!" << endl;
        return;
    }
    cout << "m = ";
    cin >> m;
    for (i = 1; i <= n; i++)
    {
        a[i] = 1;
    }
    j = 0;
    k = 0;
    for (i = 1; i <= n + 1; i++)
    {
        if (a[i] == 1)
        {
            j = j + a[i];
            if (j == m)
            {
                j = 0;
                a[i] = 0;
                k++;
            }
            if (k == n)
            {
                num = i;
                break;
            }
        }
        if (i == n + 1)
            i = 0;
    }
    cout << "number " << num << " wins " << endl;
}
1.2一级优化——复杂度
对于链表或是数组的模拟形态，在数据较大的N中我们发现程序的运行大大受制于其复杂度，又考虑到实际上不需要对原题所述的情况进行赋值，故而可以打破常规，先对于原题进行以下的数学分析，再编写一个运行相对快捷的代码.
运用数学归纳法的思想，在第一个人出列之后，剩下的个人组成了一个新的约瑟夫环（从编号开始），继而我们对新组的编号做一下平移：
 
对新组的如此一来，我们得到了前后关系的连接媒介，可以根据初值写出如下的关键式：
 
有了这个公式，我们只需要从顺序递推出值，得出. 由于题目中编号总是从1开始，输出即可. 代码如下（C语言）：
#include <stdio.h>
int main()
{
    int n, m, i, s = 0;
    printf("n m = "); scanf("%d%d", &n, &m);
    for (i = 2; i <= n; i++) s = (s + m) % i;
    printf("number %d wins\n", s + 1);
}
1.3二级优化（来自网络文献）——复杂度
进一步，如果我们观察删去和最终留下的号码，我们会发现它常常处在一种等差的状态
n（m=3）
剩余号s
16
2进制转十进制在线计算器8
32
4
1
1
17
11
33
7
2
2
18
14
34
10
3
2
19
17
35
13
4
1
20
20
36
16
5
4
21
2
37
19
6
1
22
5
38
22
7
4
23
8
39
25
8
7
24
11
40
28
9
1
25
14
41
31
10
4
26
17
42
34
11
7
27
20
43
37
12
10
28
23
44
40
13
13
29
26
45
43
14
2
30
29
46
46
15
5
31
1
47
2
观察1.2中的变量：，可以看出，当i比较大而比较小的时候，就处于一种等差递增的状态，这个等差递增的过程可以跳过.
我们设一中间变量，列出如下等式：
解出，令，将直接赋值给，这样就跳过了中间共重的循环，从而节省了等差递增的时间开销. 当求出来的超过时，我们便可以结束循环了. 这个方法跳脱出了的束缚，复杂度进一步缩减到了. 以下的代码来自于一篇博文，由于该部分不是本文讨论的重点，没有进行实践：
long Josephus(long n,long m,long k) //分别为：人数，出圈步长，起使报数位置,
{
    if (m == 1)k = k == 1 ? n : (k + n - 1) % n;
    else
    {
        for (long i = 1; i <= n; i++)
        {
            if ((k + m) < i)
            {
                x = (i - k + 1) / (m - 1) - 1;
                if (i + x < n)
                {
                    i = i + x;
                    k = (k + m * x);
                }
                else
                {
                    k = k + m * (n - i) ;
                    i = n;
                }
            }
            k = (k + m - 1) % i + 1;
        }
    }
    return k; //返回最后一人的位置
}
2. 纯数学解答中的归纳与发现
2.1对情况的解答
想要从纯数学的角度来解答这样一个复杂问题，首先需要从的特殊情况来探讨一些规律和特殊情况.
n（m=2）
剩余号s
17
3
27
23
8
1
18
5
28
25
9
3
19
7
29
27
10
5
20
9
30
29
11
7
21
11
31
31
12
9
22
13
32
1
13
11
23
15
33
3
14
13
24
17
34
5
15
15
25
19
35
7
16
1
26
21
36
9
从上表中我们可以发现对于，始终有，故而易想到将其作为归纳之基，可以得出如下的一种归纳证法：
1 时，易得每一次删减处理的数分别为， ，，， 第圈删去个数，最终剩下的是，，均为1的第一号数码.
2 时，先抽杀个数码，接下来剩下的个数码是以开头（相当于数码1）的新环列，运用①中的相关结论可得，最终剩下存活的恰是号数码的人.
由①②可以归总得的一般数学解：满足的约瑟夫环列，最终剩下的数码是
这道题的解答是否就这样完成了呢？在进行测算的过程中，我们其实能发现，出使得最接近的数字是一大关键点. 而恰好在进制转化的过程中，这一问题被交代成了对应二进制数的第一位数问题，故而我将分别进行了二进制转化，并发现了一定规律：
8
1
1000
0001
111
9
3
1001
0011
110
10
5
1010
0101
101
11
7
1011
0111
100
12
9
1100
1001
11
13
11
1101
1011
10
14
13
1110
1101
1
15
15
1111
1111
0
16
1
10000
00001
1111
注：表示的二进制数码，其余类比.
就如上述表格中所显示的一样，在二进制数码中，出现了惊人的对称与平移现象，在每一个与中最“外部”的1保持轴对称，其余数码直接平移就可以完成. 基于其形状可将其命名为“进制平移外称塔”. 仔细想来，二进制数码的第一位即象征十进制解法中的，对二进制而言既是末尾加1，整体动作看起来就像将第一位数字移到了末位.
有这样的解法的启发，我们是不是能够对任意来探讨进制下的数码变换而得到更加有新意且简便的解法呢？

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。