当前位置 博文首页 > 用心编码:算法-循环链表[约瑟夫问题之进阶]
1.问题描述:
约瑟夫问题:进阶
有 n 个人,初始时按照顺序围成一圈而坐,每个人都有一个密码。
从任意一个人开始,制定报数上线M,当有人报数为M时,该人死亡,从下一个人开始报数,该人报数前指定报数上限M为该人的密码。
至到所有人都死亡结束游戏,输出死亡顺序编号。
2.代码:
#include "stdafx.h"
#include "stdlib.h"
using namespace std;
typedef int TYPE;
typedef struct Node {
TYPE data;
TYPE password;
Node* next;
}Node;
// random
TYPE random[21] = {
0,5,4,5,6,3,10,19,4,7,12,14,15,17,21,5,22,23,24,25,26
};
Node* create_list(int n) {
int i;
Node* head = (Node*) malloc(sizeof(Node));
head->data = 1;
head->password = random[1];
Node* temp = head;
for (i = 2; i <= n;i++) {
Node* node = (Node*)malloc(sizeof(Node));
node->data = i;
node->password = random[i%20 + 1];
if (i == n) {
node->next = head;
}
temp->next = node;
temp = node;
}
return head;
}
void joseph_new(int M,Node* head) {
if (head == head->next) {
printf("%d \n", head->data);
return;
}
Node* current = head;
Node* temp = head;
while (M-- > 1) {
temp = current;
current = current->next;
}
temp->next = current->next;
printf("%d \n", current->data);
joseph_new(current->password, current->next);
}
int main()
{
Node* head = create_list(10);
joseph_new(5,head);
return 0;
}
cs