约瑟夫环问题（报数问题）

川长思鸟来 2022-08-06 12:20 145阅读 0赞

先说一下什么是约瑟夫环问题，这是百科的解释：

约瑟夫环（[约瑟夫问题][Link 1]）是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

思路：

因为n个人不定，所以采用链表。因为是连续报数的，所以是用循环链表。每数到m，那个m号的人就删除掉，然后从他身后一位重新开始，再数到m，再删除，一直这样。怎么样才能停止呢？就是当一开始的队伍没人的时候。就是一开始按顺序建立一个有顺序的链表1~n，再根据m删除，删除掉的人又重新组成一个链表，这就是出局的顺序。怎么根据m来删除呢？当从1号开始数，经过m-1个人就是要删除的那位。就是2,3,...m-1。再从m-1的后一位开始当作1，再经过m-1个人这样重复。

下面我给出我写的代码：

/* 关于我写的函数说明一下
     * head，root变量分别代表一开始按顺序的队伍和出局顺序的队伍
     * 插入函数中因为两个表的形成方式不同所以插入方式有所不同
     * 销毁函数也是一样
     * 约瑟夫问题的解决主要体现是在删除函数上
     */
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct Node
    {
    	int		num;
    	struct Node	*next;
    }Node;
    
    
    /* 初始化链表 */
    int InitList(Node **head, int n);
    
    /* 添加至链表,要做成循环链表 */
    int InsertList(Node *head, int n, int flag);	/* flag代表不同插入方式 */
    
    /* 删除 */
    int DeleteList(Node *head, Node *root, int m);
    
    /* 输出链表 */
    int DisplayList(Node *head);
    
    /* 销毁链表 */
    int DestroyList(Node *head, int flag);		/* 代表不同销毁方式 */
    
    /* 转置函数 */
    int Transpose(Node *head);
    
    int main(void)
    {
    	Node	*head = NULL;	/* 一开始存储按顺序的队伍 */
    	Node	*root = NULL;	/* 最后退出顺序的队伍 */
    	int	m = 0;		/* 指定退出的号码 */
    	int	n = 0;		/* 游戏的人数 */
    	int	flag = 0;	/* 用来表示在插入函数时0代表head, 1代表root */
    	printf("请输入人数和退出的号码：\n");
    	scanf("%d %d", &n, &m);
    
    	/* 初始化 */
    	InitList(&head, n);	/* 这个是一开始按顺序派对的队伍 */
    	InitList(&root, n);	/* 这个是到最后储存退出顺序的队伍 */
    	
    	/* 添加 */
    	InsertList(head, n, flag);
    	
    	/* 输出 */
    	printf("按顺序排队：\n");
    	DisplayList(head);
    
    	/* 根据指定的号码m来删除 */
    	DeleteList(head, root, m);
    	Transpose(root);		/* 因为在删除函数中以头插法生成，所以需要倒置 */
    
    	/* 输出 */
    	printf("退出完毕！现在输出游戏退出顺序：\n");
    	DisplayList(root);
    	
    	/* 销毁链表 */
    	DestroyList(head, flag);
    	flag = 1;
    	DestroyList(root, flag);
    
    	return 0;
    }
    
    /* 初始化链表 */
    int InitList(Node **head, int n)
    {
    	(*head) = (Node *)malloc(sizeof(Node));
    	(*head)->num = n;		/* 头结点的num变量就储存人数n */
    	(*head)->next = NULL;
    	return 1;
    }
    
    /* 添加至链表，要做成循环链表 */
    int InsertList(Node *head, int n, int flag)
    {
    	Node	*rear = head;
    	Node	*current = head;
    	Node	*new = NULL;
    	int	i = 0;
    
    	/* 这是head的插入方式，尾插法 */
    	if (flag == 0)
    	{
    	for (i = 1; i <= n; i++)
    	{
    		new = (Node *)malloc(sizeof(Node));
    
    		if (new == NULL)
    		{
    			perror("Malloc error");
    			exit(1);
    		}
    		else
    		{
    			new->num = i;
    			rear->next = new;
    			rear = new;
    		}
    		rear->next = NULL;
    	}
    	rear->next = head->next;	/* 形成循环链表 */
    	}
    	/* 这是root的插入方式，头插法,可以不用循环链表，因为游戏已经结束 */
    	else
    	{
    		new = (Node *)malloc(sizeof(Node));
    
    		if (new == NULL)
    		{
    			perror("Malloc error");
    			exit(1);
    		}
    		else
    		{
    			new->num = n;
    			new->next = current->next;
    			current->next = new;
    		}
    	}
    
    return 1;
    }
    
    /* 删除 */
    int DeleteList(Node *head, Node *root, int m)
    {
    	Node	*current = head->next;
    	Node	*previous = NULL;
    	int	i = 0;
    	int	count = head->num;
    	int	flag = 1;
    
    	while (count != 0)	/* 此时队伍没人，就退出 */	
    	{
    		while (1)
    		{
    
    			/* 经过m-1个之后current指针就会指向要退出的元素 */
    			if (i == m-1)
    			{
    				i = 0;	/* 重新开始计数 */
    				break;
    			}
    
    			previous = current;
    			current = current->next;
    			i++;
    			
    		}
    		previous->next = current->next;			/* 删除元素 */
    		InsertList(root, current->num, flag);		/* 将删除出来的元素添加至新的链表中 */
    		free(current);
    		count--;					/* 每free一次就减少一个人 */
    		current = previous->next;			/* 从被删掉元素的后一位重新开始 */
    	}
    	return 1;
    }
    
    /* 输出链表 */
    int DisplayList(Node *head)
    {
    	Node	*current = head->next;
    	int	count = head->num;	
    	int	i = 1;
    	
    	while (1)
    	{
    		if (i != count)
    			printf("%d->", current->num);
    		else
    		{
    			printf("%d\n", current->num);
    			break;
    		}
    			current = current->next;
    		i++;	
    	}
    
    	return 1;
    }
    
    /* 销毁链表 */
    int DestroyList(Node *head, int flag)
    {
    	
    	Node	*current = head;
    	Node	*previous = NULL;
    	int	count = head->num;	
    	int	i = 1;
    	
    	if(flag == 0)
    		free(head);
    	else
    	while (current != NULL)
    	{
    		previous = current;
    		current = current->next;
    		free(previous);
    	}
    	return 1;
    }
    
    /* 转置函数 */
    int Transpose(Node *head)
    {
    	Node *p1, *p2, *p3 = NULL;
    	p1 = head->next;
    	p2 = p1->next;
    
    	while (p2 != NULL)
    	{
    		p3 = p2->next;
    		p2->next = p1;
    		p1 = p2;
    		p2 = p3;
    	}
    	head->next->next = NULL;
    	head->next = p1;
    
    	return 1;
    }

现在给出程序运行的结果：

![20150124083934592][]

因为是新手，所以不懂得怎么优化代码，请多多包含。

[Link 1]: http://baike.baidu.com/view/213217.htm
[20150124083934592]: /images/20220806/b159d1ad00f4411282f8f7a575287b1b.png