標籤: 暫無標籤

是一個數學的應用問題。已知n個人(以編號1,2,3...n分別表示)圍坐在一張圓桌周圍。從編號為k的人開始報數,數到m的那個人出列;他的下一個人又從1開始報數,數到m的那個人又出列;依此規律重複下去,直到圓桌周圍的人全部出列。這個就是約瑟夫環問題的實際場景,有一種是要通過輸入n,m,k三個正整數,來求出列的序列。

1 約瑟夫環 -概述

    是一個數學的應用問題:

    已知n個人(以編號1,2,3...n分別表示)圍坐在一張圓桌周圍。從編號為k的人開始報數,數到m的那個人出列;他的下一個人又從1開始報數,數到m的那個人又出列;依此規律重複下去,直到圓桌周圍的人全部出列。

   這個就是約瑟夫環問題的實際場景,有一種是要通過輸入n,m,k三個正整數,來求出列的序列。這個問題採用的是典型的循環鏈表的數據結構,就是將一個鏈表的尾元素指針指向隊首元素。 p->link=head

2 約瑟夫環 -解決


   解決問題的核心步驟:
       1.建立一個具有n個鏈結點,無頭結點的循環鏈表
       2.確定第1個報數人的位置
       3.不斷地從鏈表中刪除鏈結點,直到鏈表為空

void JOSEPHUS(int n,int k,int m) //n為總人數,k為第一個開始報數的人,m為出列者喊到的數
{
    "
    LinkList p,r,list;

    "
    for(int i=0,i<n,i++)
    {
        p=(LinkList)malloc(sizeof(LNode));
        p->data=i;
        if(list==NULL)
            list=p;
        else
            r->link=p;
        r=p;
    }
    p>link=list; "
    p=list; "

    "
    for(i=0;i<k;i++)
    {
        r=p;
        p=p->link;
    }

    "
    while(p->link!=p)
    {
        for(i=0;i<m;i++)
        {
            r=p;
            p=p->link;
        }
        r->link=p->link;
        printf("被刪除的元素:%4d ",p->data);
        free(p);
        p=r->link;
    }
    printf("\n最後被刪除的元素是:%4d",P->data);
}
上一篇[冒泡排序]    下一篇 [top]

相關評論

同義詞:暫無同義詞