洛谷P1996 约瑟夫问题

柔情只为你懂 2022-05-29 10:16 51阅读 0赞

## 题目背景 ##

约瑟夫是一个无聊的人！！！

## 题目描述 ##

n个人(n<=100)围成一圈,从第一个人开始报数,数到m的人出列,再由下一个人重新从1开始报数,数到m的人再出圈,……依次类推,直到所有的人都出圈,请输出依次出圈人的编号.

## 输入输出格式 ##

输入格式：

n m

输出格式：

出圈的编号

## 输入输出样例 ##

输入样例\#1： 复制

10 3

输出样例\#1： 复制

3 6 9 2 7 1 8 5 10 4

## 说明 ##

m, n \\le 100

*m*,*n*≤100

解法一：

模拟

#include <stdio.h>  
    #include<iostream>
    using namespace std;
    
    int vis[101];
    
    int main()
    {
    
    	int n, m;
    	cin >> n >> m;
    	int k = 0;
    
    	for (int num = 0; num < n; num++)
    	{
    		for (int i = 0; i < m; i++)
    		{
    			if (++k>n)k = 1;
    			if (vis[k]) i--;
    		}
    		printf("%d ",k);
    		vis[k] = 1;
    	}
    
    	return 0;
    }

解法二：数学推导

参考题解：[http://blog.csdn.net/ordinarycrazy/article/details/77073455][http_blog.csdn.net_ordinarycrazy_article_details_77073455]

#include <stdio.h>  
    #include<iostream>
    using namespace std;
    int f[101][101];
    int  josef(int n, int m, int i)
    {
    	if (f[n][i]) return f[n][i];
    	if (i == 1) return (m - 1) % n;
    	return f[n][i]=(josef(n - 1, m, i - 1) + m) % n;
    }
    
    int main()
    {
    	int n, m;
    	scanf("%d%d", &n, &m);
    	
    	for (int i = 1; i <= n; i++)
    		printf("%d ", josef(n, m, i) + 1);
    	
    	return 0;
    }

[http_blog.csdn.net_ordinarycrazy_article_details_77073455]: http://blog.csdn.net/ordinarycrazy/article/details/77073455

发表评论取消回复

表情：

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

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

相关阅读

相关【P1996 约瑟夫问题】【HDU 4841 圆桌问题】【P1145 约瑟夫】再解约瑟夫环

1 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZ

桃扇骨/ 2022年10月31日 04:27/ 0 赞/ 18 阅读

相关约瑟夫问题

约瑟夫问题作者：Ackarlix 这是一个非常经典的问题：n个骑士编号1，2，...，n，围坐在圆桌旁，编号为k的骑士从1开始报数，报到m的骑士出列，然后下一个位置再从1

刺骨的言语ヽ痛彻心扉/ 2022年09月19日 13:29/ 0 赞/ 211 阅读

相关约瑟夫问题

约瑟夫环问题：一圈共有N个人，开始报数，报到M的人自杀，然后重新开始报数，问最后自杀的人是谁？ ![Center][] 第一种方法：循环思想

待我称王封你为后i/ 2022年08月08日 00:39/ 0 赞/ 194 阅读

相关约瑟夫问题

Problem Description n个人想玩残酷的死亡游戏，游戏规则如下： n个人进行编号，分别从1到n，排成一个圈，顺时针从1开始数到m，数到m的人被

￡神魔★判官ぃ/ 2022年07月14日 12:44/ 0 赞/ 183 阅读

相关约瑟夫问题

约瑟夫问题 Time Limit: 1000MS Memory Limit: 65536KB [Submit][] [ Statis

分手后的思念是犯贱/ 2022年06月18日 05:24/ 0 赞/ 187 阅读

相关约瑟夫问题

<table> <tbody> <tr> <td>成绩</td> <td>10</td> <td>开启时间</td> <td>2017

╰半夏微凉°/ 2022年06月02日 08:57/ 0 赞/ 288 阅读

相关约瑟夫问题

1.知识点：循环链表 2.题意：n个人进行编号，分别从1到n，排成一个圈，顺时针从1开始数到m，数到m的人被杀，剩下的人继续游戏，请输出最后一个人的编号 3.注意事项：

心已赠人/ 2022年05月30日 04:46/ 0 赞/ 180 阅读

相关洛谷P1996 约瑟夫问题

题目背景约瑟夫是一个无聊的人！！！题目描述 n个人(n<=100)围成一圈,从第一个人开始报数,数到m的人出列,再由下一个人重新从1开始报数,数到m的人再出圈

柔情只为你懂/ 2022年05月29日 10:16/ 0 赞/ 52 阅读

相关约瑟夫问题

Problem Description n个人想玩残酷的死亡游戏，游戏规则如下： n个人进行编号，分别从1到n，排成一个圈，顺时针从1开始数到m，数到m的人被杀，剩下的人

我就是我/ 2022年05月16日 06:06/ 0 赞/ 194 阅读

相关约瑟夫问题

约瑟夫问题 ![在这里插入图片描述][20181114211743434.jpg] 题目描述：开始有5个人围成圆形，从0号开始，数2个人，谁被数到就

灰太狼/ 2022年04月16日 00:46/ 0 赞/ 208 阅读