约瑟夫问题:一个船上有30个人,其中有15个好人,15个坏人,从第一个人开始数数,数到9的人出列,接着下一个人为1,开始数数,直到有15个人出列,要求出列的全是坏人。
用链表解决约瑟夫问题。
//===============================================================
//Summary:
// C语言 类
//FileName:
// C语言.c
//Remarks:
// 解决约瑟夫问题:总共有30人,15个好人,15个坏人,从第一个人开始
// 数数,数到9的人出列,接着下一个人为1,开始数数,直到有15人出列,
// 要求出列的都是坏人。
//Date:
// 2019/8/6 18:01
//Author:
// 张珂(1575595743@qq.com)
//Version:
// 1.0
//===============================================================
#include<stdio.h>
#include<stdlib.h>
struct node
{
int no;
struct node * next;
};
int main()
{
int i, k;
struct node *head, *q, *p;
head = (struct node *)malloc(sizeof(struct node)); //为表头节点分配内存
head->no = -1;
head->next = head;
for (i = 30; i > 0; i--) //生成循环链表
{
p = (struct node *)malloc(sizeof(struct node));
p->next = head->next;
p->no = i;
head->next = p;
}
printf("The original circle is :\n");
while(p->next != head) //循环跳过表头节点
p= p->next;
p->next = head->next; //p指向30
for (i = 0; i < 15; i++)
{
for (k = 1; k < 9; k++)
p = p->next;
q = p->next; //p的下一个节点就是要出列的节点
p->next = q->next; //循环链表跳过要出列的节点
printf("%3d", q->no); //输出q节点的编号
free(q); //释放q节点
}
return 0;
}
运行结果如下图: