浅析约瑟夫自杀环(C语言)

约瑟夫环

问题:将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代表第一轮报数指针的移动情况
浅析约瑟夫自杀环(C语言)

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

#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也仍可以被使用,只是那块内存空间已经不再属于他了。

希望以上讲解对你有帮助哦!
各位客官觉得真的很赞的话可以点赞本博客后打赏一波哦
浅析约瑟夫自杀环(C语言)

上一篇:python_003--列表的操作和for循环


下一篇:如何利用python实现生命游戏