循环队列的应用——约瑟夫问题

淩亂°似流年 2022-05-18 01:28 130阅读 0赞

# 约瑟夫问题 #

**[约瑟夫][Link 1]问题（有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。又称“丢手绢问题”.）**

## 问题来历 ##

据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第*k*个人。接着，再越过k-1个人，并杀掉第*k*个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。

## 正题 ##

闲扯了这么多，来下来看这个算法怎么实现。

主要是用到循环队列来解决这个问题。具体的代码说明已注释。

循环队列的**头文件\#include "yuesefu.h"**

#ifndef YUESEFU_H_INCLUDED
    #define YUESEFU_H_INCLUDED
    
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    typedef struct LNode
    {
        int data;
        struct LNode *next;
    }LNode;
    typedef struct LinkList
    {
       LNode *head;
       int size;
    }LinkList;
    
    LinkList *CreateList_L(int n)      //创建
    {
        int i;
        LNode *p;
        LinkList *L = (LinkList *)malloc(sizeof(LinkList));
        L -> size = 0;
        L->head = (LNode *)malloc(sizeof(LNode));
        L->head->data = 0;
        L->head->next = L->head;
    
        for( i = 0;i < n;i++)
        {
            p = (LNode *)malloc(sizeof(LNode));
            scanf("%d",&p -> data);
            p -> next = L -> head-> next;
            L -> head -> next = p;
        }
        L->size = n;
        printf("链表创建成功！\n");
        return L;
    }
    void DestoryList_L(LinkList *L)     //销毁
    {
        if(L == NULL)
            return;
        LNode *current = L->head;
        LNode *Next;
        while( current != NULL)
        {
            Next = current ->next;
            free(current);
            current = Next;
        }
        L ->size = 0;
        free(L);
        printf("链表销毁成功！\n");
    }
    void InsertList_L(LinkList *L, int pos, int e)  //插入元素
    {
        if( L == NULL )
            return;
        if( pos < 0 || pos > L->size)
        {
            pos = L->size;
        }
    
        LNode *newnode = (LNode *)malloc(sizeof(LNode));
        newnode->data = e;
        newnode->next = NULL;
        LNode *current = L->head;
        int i;
        for( i = 0; i < pos; i++ )
        {
           current = current ->next;
        }
        newnode ->next = current ->next;
        current ->next = newnode;
        L ->size++;
    }
    void DeleteListByPos_L(LinkList *L, int pos)   //按位置进行删除元素
    {
    
        if( L == NULL)
            return;
        if( pos < 0 || pos > L->size )
        {
            printf("你输入的位置不合法，请重新输入！\n");
            return;
        }
        int i;
        LNode *Next;
        LNode *current = L->head;
        for( i = 0;  i < pos; i++ )
        {
            current = current ->next;
        }
        Next = current ->next;
        current ->next = current ->next->next;
        free(Next);                           //后释放结点
        L->size--;
    }
    
    void DeleteListByValue_L(LinkList *L, char e)
    {
        if( L == NULL)
            return;
        LNode *current = L->head;
        while(current ->next->data != e)
        {
            current = current ->next;
    
        }
        LNode *Next = current ->next;
        current->next = current ->next->next;
        free(Next);
        L->size--;
    }
    
    void PrintList_L(LinkList *L)           //打印
    {
    
        if(L == NULL)
        {
           printf("链表为空！");
           return;
        }
        LNode *current = L->head->next;
        while( current != NULL)
        {
            if(current == L->head)
            {
                break;
                //current = current ->next;
            }
            printf("%d\t",current -> data);
            current = current -> next;
        }
        printf("\n");
    }
    int SizeList_L(LinkList *L)
    {
       return L->size;
    }
    #endif // YUESEFU_H_INCLUDED

**主函数main**

#include <stdio.h>
    #include <stdlib.h>
    
    #define N 3
    #include "yuesefu.h"
    void testysf()
    {
        LinkList *L = CreateList_L(8);      //创建循环队列
        PrintList_L(L);
        int index = 1;
        LNode *current = L->head->next;       //辅助指针
        LNode *Next;                
        while(SizeList_L(L) > 1)
        {
            if(index == N)                  //判断
            {
    
                printf("%d\t",current ->data);  
                Next = current ->next;        //要进行删除当前结点，需要缓存下一个结点的位置
                DeleteListByValue_L(L,current ->data); //删除结点
                current = Next;                
                if(current == L->head)        //如果指向头结点 需要跳过去
                    current = current ->next;
                index = 1;                    //重置index
    
            }
            else
            {
                current = current ->next;
                index ++;
                if(current == L->head)
                    current = current ->next;
            }
    
        }
        if(SizeList_L(L) == 1)                //最后循环队列里只剩一个元素，将其进行一个输出
        {
            printf("%d\t",L->head->next->data);
        }
    
    }
    int main()
    {
    
        testysf();
        printf("\n");
        system("pause");
        return 0;
    }

编译环境：Code::Blocks 16.01

**注：再进行输入时由于队列采用的头插法要采用倒叙输入（例：12345678，输入时87654321）。**

[Link 1]: https://baike.baidu.com/item/%E7%BA%A6%E7%91%9F%E5%A4%AB/1368843