解决约瑟夫问题

约瑟夫问题:一个船上有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;
}

运行结果如下图:
image
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容