约瑟夫环

问题：将n个人按自然数编号后围成一圈开始报数，每报到m的人自杀，求最后幸存者编号

方法一 数学递推

#include<stdio.h>
int main()
{
	int n, m, p = 0;
	scanf("%d", &n);
	for(int i = 2;i <= n;i++)
	p = (p + m) % i;
	printf("%d", p + 1);
	return 0;
}

递推公式：

f ( N , M ) = ( f ( N − 1 , M ) + M ) % N

f ( N , M )表示，N个人报数，每报到M时杀掉那个人，最终胜利者的编号
f ( N − 1 , M ) 表示，N-1个人报数，每报到M时杀掉那个人，最终胜利者的编号

方法二 数组循环移动

方法引入：

用指针实现数组循环移动

任务描述
题目描述:有n个整数，要求你编写一个函数使其向右循环移动m个位置
####相关知识（略）
####编程要求
请仔细阅读右侧代码，结合相关知识，在Begin-End区域内进行代码补充。
输入
输入n m表示有n个整数，移动m位
输出
输出移动后的数组
####测试说明
样例输入：
10 5
1 2 3 4 5 6 7 8 9 0
样例输出：
6 7 8 9 0 1 2 3 4 5

#include<stdio.h>
int *solve(int *s, int n, int m){
    /*********Begin*********/
    int k = m % n;
    if(k == 0) return s;
	int *p = &s[n - k];
	int *q = p + m;
	for(int i = 0;i < n - k;i++)
	*q++ = *s++ ; 
	return p; 
    /*********End**********/
}
int main(void)
{
    int n, m, s[110];
    scanf("%d%d", &n, &m);
    for(int i = 0;i < n;i++)
        scanf("%d", &s[i]);
    int *ans;
    /*********Begin*********/
    ans = solve(s, n, m);
    /*********End**********/
    for(int i = 0;i < n;i++){
        if(i == 0)    printf("%d", *ans++ );
        else printf(" %d", *ans++ );
    }
    return 0;
}

看完上述例子我们想到
约瑟夫自杀环中，从第一个人开始，报到m的人自杀，下一个报数人从1开始报数，开始下一轮报数，直到下一个报到m的人自杀。我们先将问题简化即7个人报到3的人自杀。我们通过循环移动让每一轮自杀都处于第一轮报数自杀的状态。
1 2 3 4 5 6 7（1 2）
4 5 6 7 1 2（4 5）
7 1 24 5（7 1）
4 5 7 1（4 5）
1 4 5（1 4）
1 4
荧光黄：报到m自杀的人
删除线和括号：
一轮报数已经结束，上一轮幸存者由删除线被移到括号处 进行下一轮报数。
将这组数展开：
1 2 3 4 5 6 7 1 2 4 5 7 1 4 5 1 4 1 4 4 4 0
两指针移动情况如下图
数字下标表示指针在该轮中的移动情况，如*p1,*q1代表第一轮报数指针的移动情况

双指针法实现数组循环移动

#include<stdio.h>
#define N 1000
int a[N];//用全局变量初始化除键入元素外的其他元素全为0
int main()
{
	int i, n;
	scanf("%d", &n);
	int *p = a, *q = a + n;
	for(i = 0;i < n;i++)
	a[i] = i + 1;
	while(*p != *q)
	{
		for(i = 0;i < 2;i++)
		*q++ = *p++;//将上一轮幸存者移到下一轮
		p++;
	}
	p--;
	printf("%d ", *p);
	return 0;
}

方法三 链表法

约瑟夫环顾名思义他是个环嘛，用链表法可将数据连成环状

#include<stdio.h>
#include<stdlib.h>
#define N 1000
int main()
{
	typedef struct Josephus_circle
	{
		int num;
		Josephus_circle *next;
	}ring;
	ring *head, *tail, *newN, *man, *alive;
	int i, n;
	scanf("%d", &n);
	head = (ring*)malloc(sizeof(ring));
	head->num = 1;
	tail = head;
	for(i = 2;i <= n;i++)
	{	
		newN = (ring*)malloc(sizeof(ring));
		newN->num = i;
		tail->next = newN;
		tail = newN;
	}	
	tail->next = head;
	man = head;//将数据连成环
	while(n != 1)
	{	
		for(i = 1;i < 3;i++)
		{
			alive = man;
			man = man->next;
		} 
		alive->next = man->next;
		alive =  alive->next;
		free(man);//释放man指针所指向的空间，但指针本身空间没有被释放
		man = alive;
		n--;	
	}
	printf("%d ", alive->num);
}

free函数说明

free函数无返回值，他的功能是释放指针变量p所指向的内存单元。此时p指向的那个内存单元将会被释放并还给操作系统，不在归他使用。操作系统可以重新将他分配给其他变量使用。大家还记得什么是“释放”？所谓释放并不是清空内存空间，而是将该内存标记为“可用状态”，使操作系统在分配内存时可以将他重新分配给其他变量使用。

但是需要注意的是：指针变量p被释放之后，他仍然是指向那块内存空间的，p也仍可以被使用，只是那块内存空间已经不再属于他了。

希望以上讲解对你有帮助哦！
各位客官觉得真的很赞的话可以点赞本博客后打赏一波哦