問題描述：設有n個人圍坐在一個圓桌周圍，現從第s個人開始報數，數到第m的人出列，然后從出列的下一個人重新開始報數，數到m的人又出列，如此重復，直到所有的人全部出列為止，Josephus問題是：對于任意給定的n，m，s，求出按出列次序得到的n個人員的順序表，
輸入：（第一行為圓桌上人數s，第二行為出列數m，即報數報到幾出列，第三行輸入人數代表的數字）
5
4
1 2 3 4 5
輸出：（第一行列印回圈鏈表，第二行列印出列序號）
1 2 3 4 5
4 3 5 2 1
存盤結構：單項回圈鏈表
演算法思想：按照游戲規則一個個報數，報到m的人出局，使用回圈鏈表，依次回圈可得到出列順序
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>//在c++中如果用到system("pause")需要使用這個頭檔案，后面程式同理
#define NULL 0
/*
1.首先要進行回圈鏈表的創建，createCircularList（）
2.進行單項鏈表輸出，注意結束條件，printCircularList（）
3.進行約瑟夫環的實作，并列印出列序號，josephRing（）
*/
typedef struct LNode{
int data;//資料元素
int sequence;//順序號
LNode *next;
}LNode,*LinkList;
void createCircularList(LinkList &L, int s);//創建一個不帶頭節點的回圈單向鏈表
void printCircularList(LinkList L);//列印輸出單項回圈鏈表
void josephRing(LinkList L, int m, int s);//約瑟夫環的實作,L對應題中n,m、s各代表m、s
int s,m;
int main(){
printf("請輸入圓桌上的人數:");
scanf("%d",&s);
printf("\n請輸入出列數:");
scanf("%d",&m);
LinkList L;
createCircularList(L, s);
printCircularList(L);
josephRing(L, m, s);
system("pause");
return 0;
}
void createCircularList(LinkList &L, int n){
printf("\n請輸入資料元素(%d個)：\n",s);
//輸入第一個元素，即頭節點
LinkList head = (LinkList)malloc(sizeof(LNode));
head->sequence = 1;
head->next = NULL;
scanf("%d", &head->data);
L = head;
LinkList p = head;
int i = 2;
while(i <= n){
LinkList s = (LinkList)malloc(sizeof(LNode));
s->sequence = i;
s->next = NULL;
scanf("%d", &s->data);
p->next = s;
p = s;
i++;
}
p->next = L;
}
void printCircularList(LinkList L){
printf("列印單項回圈鏈表：");
LinkList head = L;
LinkList p = L->next;
printf("%d ",head->data);
while(p!=head){//因為為回圈鏈表，所以條件為p!=head而不是p!=null
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
void josephRing(LinkList L, int m, int s){
int *outNum = new int[s], num=0;//按退出順序記錄編號
int count = 1;//報數
LinkList p = L, q = L;
while(p->next!=p){
if(count%m == 0){//滿足出列條件，出列并將序號賦給outNum陣列
q->next = p->next;
outNum[num] = p->sequence;
num++;
free(p);
p = q->next;
count = 1;
} else{
q = p;
p = p->next;
count++;
}
}
outNum[num] = p->sequence;//最后一位留在圓桌上的序號
printf("退出的編號順序是：");
for(int i = 0; i < s; i++){
printf("%d ", outNum[i]);
}
printf("\n");
} 轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/402557.html
標籤：其他