博客

约瑟夫环 (100分)

N个人围成一圈顺序编号，从1号开始按1、2、3…顺序报数，报p者退出圈外，其余的人再从1、2、3开始报数，报p的人再退出圈外，以此类推。 请按退出顺序输出每个退出人的原序号。

输入格式:

输入只有一行，包括一个整数N(1<=N<=3000)及一个整数p(1<=p<=5000)。

输出格式:

按退出顺序输出每个退出人的原序号，数据间以一个空格分隔，但行尾无空格。

输入样例:

在这里给出一组输入。例如：

7 3

输出样例:

3 6 2 7 5 1 4

目前在学循环链表，所以用的循环链表写。

这是我目前想到的最简单的解决方法，比较直接（我还没有想到其他方法哈哈哈）

按照测试用例 选择 7 3来看，容易知道输出顺序是这样的：

我的想法是访问一个节点后，就把节点的值赋值为0，然后后面用if语句判断是否为0，决定是否输出，不为0就输出数据，为0就跳过。






用的

尾插法


步骤：

1. 创建链表节点
2. 创建循环链表
3. 关键代码解决约瑟夫问题

WA代码：

#include <stdio.h>
#include <stdlib.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
typedef struct node
{
	int data;
	struct node *next;
}node;
int main(int argc, char *argv[]) 
{
	node *head = NULL;
	head = (node*)malloc(sizeof(node));
	head->data = 1;
	head->next = NULL;
	node *p = head;
	//尾插法建造链表 
	int i,n,k;
	scanf("%d",&n);
	scanf("%d",&k);
	//针对约瑟夫问题可以使用for循环来建立链表 
	for(i=2;i<=n;i++)
	{
		node *q = NULL;
		q = (node*)malloc(sizeof(node));
		q->data = i;
		q->next = NULL;
		p->next = q; 
		p = q;
		q = q->next;
	}
	p->next = head;
	/*p = head是行不通的
	必须得令一个新指针t指向p 
	debug:验证循环链表 
	node *t = p;
	t = head;
	while(t!=NULL)
	{
		printf("%d ",t->data);
		t = t->next;
	}*/
	//以上代码把数据为1~n的循环链表建立成功 
	
	//约瑟夫问题：
	int cnt = 1;
	node *t = p;
	t = head;
	
	while(t!=NULL)
	{
		if(cnt!=k)
		{
			if(t->data!=0)
			{
				cnt++;
			}
			t = t->next;
		}
		else
		{
			//第一次遍历时遇到满足条件的元素就输出，然后赋值为0 
			if(t->data!=0)
			{
				cnt = 1;
				printf("%d ",t->data);
				t->data = 0;
			}
			t = t->next;
		}
	}
		t = head;
		while(t!=NULL)
		{
			t = t->next;
			free(head);
			head = t;
		}
		return 0;	
}

循环条件里用的 t ！= NULL是错误的，（就算销毁完了链表，还是无法跳出循环？？）；

AC题解：

#include <stdio.h>
#include <stdlib.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
typedef struct node
{
	int data;
	struct node *next;
}node;
int main(int argc, char *argv[])
{
	node *head = NULL;
	head = (node*)malloc(sizeof(node));
	head->data = 1;
	head->next = NULL;
	node *p = head;
	//尾插法建造链表
	int i,n,k;
	scanf("%d",&n);
	scanf("%d",&k);
	//针对约瑟夫问题可以使用for循环来建立链表
	for(i=2;i<=n;i++)
	{
		node *q = NULL;
		q = (node*)malloc(sizeof(node));
		q->data = i;
		q->next = NULL;
		p->next = q;
		p = q;
		q = q->next;
	}
	p->next = head;
	node* q = head;
	/*p = head是行不通的
	必须得令一个新指针t指向p
	debug:验证循环链表
	node *t = p;
	t = head;
	while(t!=NULL)
	{
		printf("%d ",t->data);
		t = t->next;
	}*/
	//以上代码把数据为1~n的循环链表建立成功

	//约瑟夫问题：
	int cnt = 1;
	node *t = p;
	t = head;
    int x = 0;
    //这里引入x的意义是在于方便对比循环次数
	while(x != n)
	{
		if(cnt!=k)
		{
			if(t->data!=0)
			{
				cnt++;
			}
			t = t->next;
		}
		else
		{
			//第一次遍历时遇到满足条件的元素就输出，然后赋值为0
			if(t->data!=0)
			{
				cnt = 1;
				x++;
				printf("%d",t->data);
				if(x != n)
                    printf(" ");
				t->data = 0;
			}
			t = t->next;
		}
	}
		t = head;
		x = 0;
        //注意循环条件不能是while(t!=NULL)
		while(x != n)
		{
			t = t->next;
			free(head);
			x++;
			head = t;
		}
		return 0;
}

可以用x计数，x作为判断循环是否进入的条件

继续努力。