文章

19

粉丝

0

获赞

134

访问

2.7k

头像
约瑟夫问题的实现 题解:C语言实现,详细注释
P5104
发布于2026年3月8日 15:23
阅读数 220

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

void main(){
	int n, k;
	scanf("%d\n%d", &n, &k);
	int *arr = (int*)malloc((n+1)*sizeof(int));		// arr[i]表示编号为i的人报数是arr[i]
	memset(arr, -1, (n+1)*sizeof(int));
	int sum=n;		// 当前存活的人数
	int num=0;		// 报数,从1~k-1,第k个报数的记为0表示淘汰
	int lastidx;	// 记录最后一个被淘汰的人的编号(arr[i]的下标)
	while(sum>0){	// sum>0表示有人存活
		for(int i=1; i<=n; i++){	// 依次更新报数
			if(arr[i]==0){			// arr[i]==0表示该人已经被淘汰
				continue;
			}
			arr[i]=++num;			// 更新报数
			if(num%k==0){			// num%k==0表示该人即将被淘汰
				arr[i]=0;			// ar[i]=0表示被淘汰,下一轮不再报数
				num=0;				// 恢复报数的初始值
				sum--;				// 当前存活人数自减
				lastidx=i;			// 记录最后一个被淘汰的编号
			}
		}
	}
	printf("%d", lastidx);
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发