谁能笑到最后，约瑟夫环-Josephus问题求解-白红宇

谁能笑到最后，约瑟夫环-Josephus问题求解

阅读量：6689 次

发布时间：2019-06-25

本文共 2991 字，大约阅读时间需要 9 分钟。

一、简述Josephus问题

　　N个人站成一环，从1号开始，用刀将环中后面一个人“消灭“”掉，之后再将刀递给下一个人，这样依次处理，最后留下一个幸存者。

二、求解方法

1. 约瑟夫问题如果使用链表来求解比较麻烦，这里采用循环队列的处理。

约瑟夫问题可以等价为l连续地DeQueue()两次，然后再将第一次DeQueue()的值EnQueue()入队列尾，直到队列中只剩下一个元素。

# 循环队列代码如下：

#include 
     
      #include 
      
       #define MAX 100   /* Maximum size of Queue */typedef struct _Queue *Queue; struct _Queue {    int A[MAX];    int Head, Tail;    int Num_of_Items;};               /* Queue struct and pointer define */void EnQueue( Queue Q, int x ){    if ( Q->Num_of_Items < MAX ) {        /*  Cycle Queue not full */        if ( Q->Num_of_Items == 0 ) {            Q->Head = Q->Tail = 0;            Q->A[0] = x;        } else {            Q->Tail = (Q->Tail + 1) % MAX; /* Tail insert */            Q->A[Q->Tail] = x;        }        Q->Num_of_Items++;    } else {        printf("Warning: Full Queue!\n");        return;    }}int DeQueue( Queue Q ){    if ( Q->Num_of_Items < 1 ) {        /* empty queue */        printf("Warning: Empty Queue!\n");    } else {        int ret = Q->A[Q->Head];        Q->Num_of_Items--;        Q->Head = (Q->Head + 1) % MAX;        return ret;    }}

# 循环队列解约瑟夫问题：

void JosephusByQueue(){    _Queue Que;    Queue Q = &Que; /* initial */    //Queue Q = (Queue)malloc( sizeof(struct _Queue) );      Q->Num_of_Items = 0;            int i, j, n, answer;    printf("Enter an integer (1--99):");    scanf("%d", &n);        /* Solve Josephus Problem */    /* Step 1: Put all the number between 1 to n to the Queue */    for ( i = 1; i <= n; i++ ) {        EnQueue( Q, i);    }        /* Step 2: Start killing for n-1 rounds */    for ( i = 1; i < n; i++ ) {        j = DeQueue( Q ); /* first dequeue item */        DeQueue( Q );        EnQueue( Q, j );    }        answer = Q->A[Q->Head]; /* the last item */    printf("The value of J(%d) is: %d\n", n, answer);}

2. 每次隔一个人就消灭掉一人，经过一圈，消灭一半，就等于累次除二。等价于二的幂相关问题。

对于Josephus( N )：

　　 [1] 若N为二次幂(N = 2^M)，M为幂次。从开始一圈消除偶数，再消除奇数，每次跳过起始的1，最终留下1。

　　 EX 1: J( 8 ): Green : start ， Red: delete

　　 1 2 3 4 5 6 7 8 --> 1 2 3 4 5 6 7 8 --> 1 3 5 7

　　 --> 1 3 5 7 --> 1 5 --> 1 5 --> 1

　　 [2] 若N为奇数，可化为(N = 2^M + K)，先消除K个人，即经历过2K个人后。又为偶数问题，留下的[ Last=2K+1 ]。

　　 EX 2: J( 10 ) : N = 10, M = 3, K = 2 --> J( 10 ) = 2*k + 1 = 5

公式： N = 2^M + K ， K= N - 2^M。 J( N ) = 2 *( N - 2^M ) + 1

求解代码：

/* 数学解法：N = 2^M + K | Last = 2 *( N - 2^M ) + 1  */void Josephus(){    int i, n, m_prime, k;    printf("Enter an integer:");    scanf("%d", &n);            i = 1;    while ( i < n ) {        /* find the largest power of 2 that less than n */        i *= 2;     }    m_power = i / 2;    k = n - m_power;    printf("The remain one is %d!\n", (2 * k + 1));}

主函数：

int main(int argc, char *argv[]){    printf("Method 1: Math solving\n");    Josephus();         printf("\nMethod 2: Queue solving\n"); return 0;}

参考资料：

[1] 中国大学MOOC-数据结构-台湾清华大学-04BasicDataStructure

[2] 2的幂在约瑟夫环问题的应用https://www.cnblogs.com/sirlipeng/p/5387830.html#undefined

图片来自网络

转载于:https://www.cnblogs.com/justLittleStar/p/10432614.html

你可能感兴趣的文章