需找新的美猴王——约瑟夫环 猴王问题

猴王问题:
某森林中有n只猴子在商量猴王选举问题,所有的猴子都想当猴王,
因此大家商量了一个选举办法如下:
所有的猴子围成一圈,先从第一个猴子开始报数,报数到13的猴子就出列。
紧接着的下一个猴子,又从1开始进行新的一轮报数,报数到12的猴子再出列;
依此重复下去,每一轮报数都比上一轮的报数少1,直到报数减为1之后,又从13开始报数。
直到原列中只剩下一个猴子为止,这个猴子就是猴王。

 

试设计一个程序求出猴王。

约瑟夫环……
很自然地能想到,用链表——环形链表 比较合适。
创建一个环形的链表,每次报数报到的猴子的节点被删除,C程序实现如下:

#include "stdafx.h"
#include 
#include 

/*定义结构类型*/
typedef struct Monkey{
    int id ;
    struct Monkey *next;
} Monkey;

/**
 * 创建一个有n个节点的环形链表
 */
Monkey *creatList(int n){
    Monkey *r= (Monkey *)malloc(sizeof(Monkey));
    r->id = n;//头节点存储链表长度
    r->next = NULL;
    Monkey *head = r;//记住头
    for(int i = 1; i <= n ; i  ){
        Monkey *temp = (Monkey *)malloc(sizeof(Monkey));
        temp->id = i;
        temp->next = NULL;
        r->next = temp;
        r = r->next;
    }
    r->next = head->next;
    return head;//带头的链表
}

/**
 * 谁是众猴之王?
 */
int lookForTheKing(Monkey *list){
    int remainedNum = list->id;
    Monkey *p = list;//指向头    
    
    /*每次都删除p->next节点,直至链表中除头只剩一个节点,此时p->next也指向p*/
    for(int password = 13; remainedNum > 1; password--, remainedNum--){
        //password = (password > 0 ? password : password  13); //此句可以置换下面的if语句
        if(!password){
            password = 13;
        }
        for(int i = 0; i < password -1; i  ){
            //因为后面是要删除p->next,所以p往后移动password-1次
             p = p->next;
        }
        /*删除p->next节点*/
        Monkey *temp = p->next;
        p->next = temp->next;
        free(temp);
    }    
    return p->id;
}


int main(int argc, char* argv[])
{
    int n;
    printf("请输入猴子的个数n:");
    scanf("%d",&n);
    Monkey *list = creatList(n);
    int king = lookForTheKing(list);
    printf("/n美猴王是:%d号猴子!//nn",king);
    return 0;
}

 

示例结果:
imageimage
约瑟夫环是一个很经典的问题,最初为——
已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。

 

而变形很多,又比如如下“狐狸抓兔子”问题:

围绕着山顶有10个洞。一只兔子和一只狐狸各住一个洞。 狐狸要吃兔子。
兔子对狐狸说:“你想吃掉我可以,但必须找到我。我就藏身于这十个洞中,
你从10号洞出发,先到1号洞找我,第二次隔一个洞找我,第三次隔两个洞找我,……,
以后依次类推,若能找到我,可饱餐一顿。”。
狐狸答应了,但是狐狸从早到晚进进出出了1000次,仍没找到兔子。
请编程求兔子究竟躲在哪个洞里。 

这个问题可以在泛化一点,使山洞的个数和进进出出的次数可变, 同样用环形链表求解,这次不必删除节点,只需在每个节点(山洞)中加一个标志变量,标志其是否被进出过,则C代码实现:

#include "stdafx.h"
#include 
#include 
using namespace std;

/*为了方便,设为全局变量*/
int numOfHole;
int times;

/*表示山洞的节点*/
typedef struct Hole{
    int id ;
    int isFound;
    struct Hole *next;
}Hole;

/**
 *创建一个含有numOfHole个节点的链表
 *id值为 1 - numOfHole 
 */
Hole *creatList(){
    Hole *r= (Hole *)malloc(sizeof(Hole));
    r->id = 0;
    r->next = NULL;
    Hole *head = r;//记住头
    for(int i = 1; i <= numOfHole ; i  ){
        Hole *temp = (Hole *)malloc(sizeof(Hole));
        temp->id = i;
        temp->isFound = 0;
        temp->next = NULL;
        r->next = temp;
        r = r->next;
    }
    r->next = head->next;
    return head->next;
}

/**
 *显示所有还存在的节点id
 */
void showList(Hole *list){
    if(!list->isFound){
        printf("%d/t",list->id);
    }
    Hole *p = list->next;
    while(p != list ){
        if(!p->isFound){
            printf("%d/t",p->id);
        }
        p = p->next;
    }
}

/**
 *找兔子~即执行“进进出出”的动作
 */
Hole *lookForRabbit(Hole *list){
    Hole *p = list;
    p->isFound = 1;
    for(int i = 2; i <= times; i  ){
        for(int j =  0; j < i; j  ){
            p =p->next;
        }
        p->isFound = 1;
    }
    return p;
}

int main(int argc, char* argv[]){
    printf("请输入洞穴的数量和寻找的次数,用空格隔开: ");
    scanf("%d%d",&numOfHole,×);
    Hole *list = creatList();//创建
    list = lookForRabbit(list);//寻找兔子过程
    puts("/n兔子可能在的洞穴序号为:");
    showList(list);//打印所有没被找过的山洞序号
    puts("");
    return 0;
}

示例结果:
image

 

 

有关约瑟夫环,具体见 http://baike.baidu.com/view/717633.htm

 

 

 

Leave a Reply

Your email address will not be published.