约瑟夫问题

发表于 | 分类于 | 阅读数
字数统计: 484 | 阅读时长 ≈ 2

约瑟夫问题的实现

算法题目

n个人围成一个圈，每个人分别标注为1、2、…、n，要求从1号从1开始报数，报到k的人出圈，接着下一个人又从1开始报数，如此循环，直到只剩最后一个人时，该人即为胜利者。例如当n=10,k=4时，依次出列的人分别为4、8、2、7、3、10，9、1、6、5，则5号位置的人为胜利者。给定n个人，请你编程计算出最后胜利者标号数。（要求用单循环链表完成。）

输入

1
2
第一行为人数n;
第二行为报数k。

输出

1
输出最后胜利者的标号数。

样例输入

1
2
10 
4

样例输出

1
5

算法分析

由于是约瑟夫问题，这是一个超经典的一个题目，其中以前试过用数组做，不过好像要模拟其中的过程，所以其中的思维必须要清晰，而约瑟夫问题用单循环链表来做，逻辑会变得非常的简单，写下这篇博客，也是想记录链表的创建与删除，在约瑟夫问题上，链表真的起到了很大的作用。

算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include"iostream"
#include"cmath"
#include"cstring"
#include"stdlib.h"
using namespace std;
typedef struct node
{
	int data;
	node *next;
}Link;
void creat(Link *&L,int n)    //创建链表 
{
	Link *p;
	Link *r;
	L=(Link *)malloc(sizeof(Link));
	L->data=1;
	L->next=r;
	r=L;
	for(int i=2;i<n+1;i++)
	{
		p=(Link *)malloc(sizeof(Link));
		p->data=i;
		r->next=p;
		r=p;
 	}
 	r->next=L;
 	L=r;
}
int main()
{
    int n,k;
    cin>>n>>k;
    Link *L;
    Link *p;
    creat(L,n);
    int flag=1;    //判断是否删除结点 
    while(L!=L->next)
    {
        if(flag==k)
        {
      
        	p=L->next;
        	L->next=p->next;
        	free(p);
        	flag=1;
		}
		else
		{
			L=L->next;
			flag++;
		}
 
	}
	cout<<L->data;
	return 0;
}