约瑟夫问题

牡丹花下死做鬼

约瑟夫问题：简单来说就是 比如一共10个人 1 2 3 4 5 6 7 8 9 10
从第一个人开始 第三个人就死然后从下一个人继续从一开始数到三死
也就是说 3 6 9三个人先死了
然后10号人就是从一接着继续  1 2 4 5 7 8 10  10号一 一号2 二号3 然后二号死了 四号 1......
要求用代码写出人死亡的顺序



这个我想所有教程讲到链表都会讲到这个问题的把~~

代码其实也不难

#include<stdio.h>
#include<malloc.h>

#define MAX 41

int n = 0;

typedef struct People
{
        int data;
        struct People * next;
}p;

p * create();//创建链表
void print(p * head);//输出当前全部人死活状况
void calc(p * head);//约瑟夫问题计算

int main()
{
        p *head;
        head = create();
        calc(head);
        printf("\n");

        //print(head);
        

        return 0;
}

p * create()
{
        p * head;
        head = (p*)malloc(sizeof(p));
        p * p1;
        p1 = (p*)malloc(sizeof(p));
        head->data = 1;
        head->next = NULL;
        p1->data = 1;
        p1->next = NULL;
        int i;
        for ( i = 0; i < MAX; i++)
        {
                if (n ==0)
                {
                        head->next = (p*)malloc(sizeof(p));
                        head->next->data = 1;
                        p1->next = head->next;
                        n++;
                }
                else
                {
                        p1->next->next = (p*)malloc(sizeof(p));
                        p1->next = p1->next->next;
                        p1->next->data = 1;
                        n++;
                }
        }
        p1->next->next = head;
        return head;
}

void print(p * head)
{
        p * p1;
        p1 = head;
        n = 0;
        while (p1->next != head)
        {
                if (p1->data)
                {
                        printf("第%d个人:活\n",n+1);
                }
                else
                {
                        printf("第%d个人:死\n",n+1);
                }
                p1 = p1->next;
                n++;
        }
}

void calc(p * head)
{
        int i = 1, j = 1;
        p * p1;
        p1 = head;
        n = 41;
        while (n != 2)
        {
                if (i != 3)
                {
                        if (p1->data)
                        {
                                i++;
                        }
                }
                else
                {
                        if (p1->data)
                        {
                                i = 1;
                                p1->data = 0;
                                n--;
                                printf("%-5d", j);
                        }
                }
                p1 = p1->next;
                if (j != MAX)
                {
                        j++;
                }
                else
                {
                        j = 1;
                }
        }
}

黑龍

前排支持
@小甲鱼  快出C教程啊 不是说要重录吗。。。