約瑟夫環應用問題


/*
約瑟夫環是一個數學的應用問題:已知n個人(以編號1,2,3...n分別表示)
圍坐在一張圓桌周圍。從編號為k的人開始報數,從1數到m的那個人出列;他的下
一個人又從1開始報數,數到m的那個人又出列;依此規律重復下去,直到圓桌
周圍的人全部出列。寫程序實現上述過程。
*/

#include<iostream>
#include<cstdio>
#include<cstdlib>

using namespace std;

struct node
{
int ID;
struct node *next;
};
typedef struct node* JLink;

//第一步建立循環鏈表
void JOSEPHUS(int n, int k, int m)
{
//第一步創建循環鏈表
JLink head, ptr, newnode,temp;
temp = NULL;
head = (JLink)malloc(sizeof(node));
head->ID = 1;
ptr = head;
for (int i = 2; i <= n; ++i)
{
newnode=(JLink)malloc(sizeof(node));
newnode->ID = i;
ptr->next = newnode;
ptr = newnode;
}
ptr->next = head; //尾指向頭結點

//第二步,找到第K個結點
ptr = head;
for (int i = 1; i < k; ++i) //循環停止以後,ptr指向第K個結點,temp指向第K-1個結點
{
temp = ptr;
ptr = ptr->next;
}
//從1數m.刪除第m 個結點
while (n--)
{
for (int j = 1; j < m; ++j)
{
temp = ptr;
ptr = ptr->next; //ptr指向第m個結點
}
cout << "出列序號為:" << ptr->ID<<endl;
temp->next = ptr->next;
ptr = temp->next;
}
}

int main()
{
JOSEPHUS(9, 1, 5);
system("pause");
return 0;
}

運行結果如下:

0 個評論

要回覆文章請先登錄註冊