C语言处理约瑟夫问题（丢手绢）

水深无声 2022-05-27 06:09 236阅读 0赞

（部分经验援引自其他人）

**问题描述：**

在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。

在此，我们对该问题进行通用化，假定有n个人围成一个圈，按顺序进行拍号。从第一个人开始报数，当报到k时，这个人就要退出，剩下的人接着依次进行报数，直至最后仅剩一个人。问最后那个人是原来的第几号？

利用数组和指针解决该问题时，该问题的解决思路为：首先我将每一个人在数组中的值0，当其编号除以K的余数为0时，将该人在数组中的值赋予1，这样在循环过程中，在此遇得到该人时，就直接跳过（相当于该人退出）。源代码如下：

void find(int *p,int n,int t)
    {
    	int call_n=0,out_n=0,*q; 
    	q=p+n;
    	while(1)
    	{
    		if(*p==0)
    		{
    			if(out_n==n-1)break;//限定只剩一个人时结束循环 
    			call_n++;
    			call_n%=t;//求余 
    			if(call_n==0)
    			{
    				*p=1;
    				out_n++;
    			}	
    		}
    	p++;
    	if(p==q)p=(q-n);//当循环到数组末端时，重新循环 
    	}
    	printf("最后剩余编号%d\n",p+1-a);
    }
    int main(int argc, char *argv[]) {
    	int n,call_n=0,out_n=0,*p,t;
    	printf("请输入人数：\n");//输入人数 
        scanf("%d",&n);
        printf("请输入到几退出\n");//数到t时退出 
        scanf("%d",&t);
    	int a[1000]={0};
    	find(a,n,t);
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，236人围观）

还没有评论，来说两句吧...

相关阅读

相关 C语言约瑟夫环问题

约瑟夫环问题描述：每一个结点有两个数据域和一个指针域，数据域分别存储为id和password，指针域指向下一个结点（图1-1）； ![201910162214

比眉伴天荒/ 2023年06月08日 06:21/ 0 赞/ 16 阅读

相关数据结构与算法--我们来玩丢手绢（约瑟夫环问题）

我们来玩丢手绢昨天我们打扑克，今天我们丢手绢丢手绢我们都知道这个游戏，他的由来由约瑟夫（Josephus）提出来的据说著名犹太历史学家Jos

谁借莪１个温暖的怀抱￠/ 2022年10月13日 15:52/ 0 赞/ 157 阅读

相关丢手帕问题(约瑟夫问题)

/ 作者：linshan 功能：丢手帕问题(约瑟夫问题) / package com.test4; publ

╰+攻爆jí腚メ/ 2022年08月18日 13:28/ 0 赞/ 139 阅读

相关约瑟夫问题c、Java语言实现

n个人围成一圈，从第k人个开始报数，假设数到m的人出圈，最后剩下一个，求这个人的编号？一、链表实现 c 语言实现： include<stdio.h>

雨点打透心脏的1/2处/ 2022年08月11日 19:28/ 0 赞/ 170 阅读

相关数据结构 C语言约瑟夫问题

一、问题描述：约瑟夫问题一个旅行社要从n个旅客中选出一名旅客，为他提供免费的环球旅行服务。旅行社安排这些旅客围成一个圆圈，从帽子中取出一张纸条，用上面写的正整数m作为报数

拼搏现实的明天。/ 2022年06月13日 08:26/ 0 赞/ 201 阅读

相关 C语言链表约瑟夫问题

约瑟夫问题 Problem Description n个人想玩残酷的死亡游戏，游戏规则如下： n个人进行编号，分别从1到n，排成一个圈，顺时针

你的名字/ 2022年06月01日 05:55/ 0 赞/ 182 阅读

相关 C语言处理约瑟夫问题（丢手绢）

（部分经验援引自其他人）问题描述：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是

水深无声/ 2022年05月27日 06:09/ 0 赞/ 237 阅读

相关 C语言实现约瑟夫

C语言实现约瑟夫环 Q：约瑟夫环问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数

分手后的思念是犯贱/ 2022年05月06日 23:36/ 0 赞/ 157 阅读

相关约瑟夫环--C语言

约瑟夫（Joseph）问题的一种描述是：编号为1，2，3，…，n的n个人按顺时针方向围坐一圈。每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开

分手后的思念是犯贱/ 2022年04月02日 08:21/ 0 赞/ 185 阅读

相关 Josephus problem（约瑟夫问题，丢手绢问题）

约瑟夫问题 -------------------- 约瑟夫环问题是一个数学应用题：已知n个人（以编号1，2，3.....，n)围坐在一张圆桌的周围。从编号为k

蔚落/ 2021年11月26日 12:26/ 0 赞/ 349 阅读