C++模拟揭秘刘谦魔术,领略数学的魅力
新的一年又开始了,大家新年好呀~。在这我想问大家一个问题,有没有同学看了联欢晚会上刘谦的魔术呢?
这个节目还挺有意思的,它最出彩的不是魔术本身,而是小尼老师“念错咒语”而导致他手里的排没有拼在一起,当时还一度冲上了热搜。

这个魔术的背后其实是一个数学上的问题,它被称为约瑟夫问题,它是一个计算机科学和数学中的问题,在计算机编程的算法中,类似问题又称为约瑟夫环,又称“丢手绢问题”。
它的故事背景是这样的:
据说著名犹太历史学家Josephus(弗拉维奥·约瑟夫斯)有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。问题是,给定了和,一开始要站在什么地方才能避免被处决。Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。
在编程上的变形一般是这样的:
N个人围成一圈,从第一个开始报数,第M个出局,第M个出局之后它的下一个又从1开始报数,直到最后剩下一个,其余人都出局。例如N=6,M=5,被杀掉的顺序是:5,4,6,2,3。
给大家模拟一下这个过程:
(第一轮数字5出局,黑色字体的数字 代表n个人,红色字体代表每个人报的数字)

(第一轮数字5出局之后剩下5个数字,从数字6开始从1报数,依次顺下去就是数字4出局)

(第三轮数字依次往后报数,数字6出局)

(第四轮数字2出局)

(第五轮数字3出局,第一个人胜利)

这是约瑟夫环问题的模拟过程,那现在大家一起来看一下程序怎么写。
第一种方法:递归
#include<iostream>
using namespace std;
int ysf(int n, int k, int i)//本函数是index=0开始
{if (i == 1)return (n+k-1) % n;if (i != 1)return (ysf(n - 1, k, i - 1) + k) % n;//即为去掉前面的人构成的新环的第i-1次
}
int main()
{int n, k;cin >> n >> k;for (int i = 1; i <= n; i++){cout << ysf(n, k, i)+1 << " ";//加1统一index=1开始}
}
第二种:队列
#include<iostream>
#include<queue>
using namespace std;
queue<int> res;
int n, k;
int main()
{cin >> n >> k;for (int i = 1; i <= n; i++){res.push(i);}int cnt = 0;while (!res.empty()){for (int i = 1; i <= k - 1; i++)//执行k-1次{res.push(res.front());//将队首元素放队尾去res.pop();}//循环结束后输出队首元素cout << res.front() << " ";res.pop();//出局}return 0;
}
第三种:循环链表
#include<iostream>
#include<cstdlib>
using namespace std;
typedef struct node
{int data;struct node* next;
}Node;
int n, k;
void Joseph_ring(int n, int k)
{//开始创建循环链表Node* head = NULL, * p = NULL, * r = NULL;//搞三个指针head = (Node*)malloc(sizeof(Node));//为head头指针申请一片空间((Node*)为强制类型转换为结构体变量指针)head->data = 1;head->next = NULL;p = head;//创建循环链表用,此时p和head指向头结点for (int i = 2; i <= n; i++)//创建剩下的n-1个结点(尾插法顺序插入){r = (Node*)malloc(sizeof(Node));r->data = i;r->next = NULL;p->next = r;p = r;}p->next = head;//首尾相接p = head;//恢复初始状态while (p->next != p)//结束条件是只剩下最后一个(当然用cnt计数也可以){for (int i = 1; i < k; i++){r = p;//用r保存该删结点的上一个结点p = p->next;}//循环结束后p指针的位置是该删结点的位置cout << p->data << " ";r->next = p->next;p = p->next;}//whlie循环结束后还剩最后一个结点要输出cout << p->data;
}
int main()
{cin >> n >> k;Joseph_ring(n,k);return 0;
}
好啦,同学们自己试一试吧~
相关文章:
C++模拟揭秘刘谦魔术,领略数学的魅力
新的一年又开始了,大家新年好呀~。在这我想问大家一个问题,有没有同学看了联欢晚会上刘谦的魔术呢? 这个节目还挺有意思的,它最出彩的不是魔术本身,而是小尼老师“念错咒语”而导致他手里的排没有拼在一起,…...
JAVA语言编写一个方法,两个Long参数传入,使用BigDecimal类,计算相除四舍五入保留2位小数返回百分数。
在Java中,你可以使用BigDecimal类来执行精确的浮点数计算,并且可以指定结果的小数位数。以下是一个方法,它接受两个Long类型的参数,并使用BigDecimal来计算它们的商,然后将结果四舍五入到两位小数,并返回一…...
SQL教学:掌握MySQL数据操作核心技能--DML语句基本操作之“增删改查“
大家好,今天我要给大家分享的是SQL-DML语句教学。DML,即Data Manipulation Language,也就是我们常说的"增 删 改 查",是SQL语言中用于操作数据库中数据的一部分。作为MySQL新手小白,掌握DML语句对于数据库数…...
【性能测试】Jmeter性能压测-阶梯式/波浪式场景总结(详细)
目录:导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结(尾部小惊喜) 前言 1、阶梯式场景&am…...
前端面试 跨域理解
2 实现 2-1 JSONP 实现 2-2 nginx 配置 2-2 vue 开发中 webpack自带跨域 2 -3 下载CORS 插件 或 chrome浏览器配置跨域 2-4 通过iframe 如:aaa.com 中读取bbb.com的localStorage 1)在aaa.com的页面中,在页面中嵌入一个src为bbb.com的iframe&#x…...
JetBrains TeamCity 身份验证绕过漏洞复现(CVE-2024-27198)
0x01 产品简介 JetBrains TeamCity是一款由JetBrains开发的持续集成和持续交付(CI/CD)服务器。它提供了一个功能强大的平台,用于自动化构建、测试和部署软件项目。TeamCity旨在简化团队协作和软件交付流程,提高开发团队的效率和产品质量。 0x02 漏洞概述 JetBrains Team…...
设计模式—单例模式
单例模式(Singleton Pattern)是一种常用的软件设计模式,其核心思想是确保一个类仅有一个实例,并提供一个全局访问点来获取这个实例。单例模式主要用于控制资源的访问,比如配置文件的读取,数据库的连接等&am…...
Android在后台读取UVC摄像头的帧数据流并推送
Android在后台读取UVC摄像头的帧数据流并推送 添加UvcCamera依赖库 使用原版的 saki4510t/UVCCamera 在预览过程中断开可能会闪退,这里使用的是 jiangdongguo/AndroidUSBCamera 中修改的版本,下载到本地即可。 https://github.com/jiangdongguo/AndroidU…...
vue单向数据流介绍
Vue.js 的单向数据流是其核心设计原则之一,也是 Vue 响应式系统的基础。在 Vue.js 中,数据流主要是单向的,从父组件流向子组件。这种设计有助于保持组件之间的清晰通信,减少不必要的复杂性和潜在的错误。 以下是 Vue 单向数据流的…...
OpenMMlab AI实战营第四期培训
OpenMMlab AI实战营第四期培训 OpenMMlab实战营第四次课2023.2.6学习参考一、什么是目标检测1.目标检测下游视觉任务2.图像分类 v.s. 目标检测 二、目标检测实现1.滑窗 Sliding Window2.滑窗的效率问题3.改进思路(1)消除滑窗中的重复计算(2&a…...
React轻松开发平台:实现高效、多变的应用开发范本
在当今快节奏的软件开发环境中,追求高效、灵活的应用开发方式成为了开发团队的迫切需求。React低代码平台崭露头角,为开发人员提供了一种全新的开发范式,让开发过程更高效、更灵活,从而加速应用程序的开发周期和交付速度。 1. 快…...
多域名SSL证书:保护多个网站的安全之选
什么是多域名SSL证书? 多域名SSL证书,顾名思义,是指一张SSL证书可以保护多个域名。与传统的单域名SSL证书相比,多域名SSL证书可以在一个证书中绑定多个域名,无需为每个域名单独购买和安装SSL证书。这样不仅可以节省成…...
HarmonyOS—HAP唯一性校验逻辑
HAP是应用安装的基本单位,在DevEco Studio工程目录中,一个HAP对应一个Module。应用打包时,每个Module生成一个.hap文件。 应用如果包含多个Module,在应用市场上架时,会将多个.hap文件打包成一个.app文件(称…...
金三银四,程序员如何备战面试季
金三银四,程序员如何备战面试季 一个人简介二前言三面试技巧分享3.1 自我介绍 四技术问题回答4.1 团队协作经验展示 五职业规划建议5.1 短期目标5.2 中长期目标 六后记 一个人简介 🏘️🏘️个人主页:以山河作礼。 🎖️…...
VUE3项目学习系列--项目配置(二)
在项目团队开发过程中,多人协同开发为保证项目格式书写格式统一标准化,因此需要进行代码格式化校验,包括在代码编写过程中以及代码提交前进行自动格式化,因此需要进行在项目中进行相关的配置使之代码格式一致。 一、eslint配置 …...
idea:springboot项目搭建
目录 一、创建项目 1、File → New → Project 2、Spring Initializr → Next 3、填写信息 → Next 4、web → Spring Web → Next 5、填写信息 → Finish 6、处理配置不合理内容 7、注意事项 7.1 有依赖包,却显示找不到依赖,刷新一下maven 二…...
如何保证某个程序系统内只运行一个,保证原子性
GetMapping("/startETL") // Idempotent(expireTime 90, info "请勿90秒内连续点击")public R getGaugeTestData6() {log.info("start ETL");//redis设置t_data_load_record 值为2bladeRedis.set("t_data_load_record_type", 2);Str…...
golang常见面试题
1. go语言有哪些优点、特性? 语法简便,容易上手。 支持高并发,go有独特的协程概念,一般语言最小的执行单位是线程,go语言支持多开协程,协程是用户态线程,协程的占用内存更少,协程只…...
探索Python编程世界:从入门到精通
一.Python 从入门到精通 随着计算机科学的发展,编程已经成为了一种必备的技能。而 Python 作为一种简单易学、功能强大的编程语言,越来越受到人们的喜爱。本文将为初学者介绍 Python 编程的基础知识,帮助他们踏入 Python 编程的大门…...
Spark Shuffle Tracking 原理分析
Shuffle Tracking Shuffle Tracking 是 Spark 在没有 ESS(External Shuffle Service)情况,并且开启 Dynamic Allocation 的重要功能。如在 K8S 上运行 spark 没有 ESS。本文档所有的前提都是基于以上条件的。 如果开启了 ESS,那么 Executor 计算完后&a…...
【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
oracle与MySQL数据库之间数据同步的技术要点
Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异,它们的数据同步要求既要保持数据的准确性和一致性,又要处理好性能问题。以下是一些主要的技术要点: 数据结构差异 数据类型差异ÿ…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...
AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别
【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而,传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案,能够实现大范围覆盖并远程采集数据。尽管具备这些优势…...
深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向
在人工智能技术呈指数级发展的当下,大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性,吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型,成为释放其巨大潜力的关键所在&…...
绕过 Xcode?使用 Appuploader和主流工具实现 iOS 上架自动化
iOS 应用的发布流程一直是开发链路中最“苹果味”的环节:强依赖 Xcode、必须使用 macOS、各种证书和描述文件配置……对很多跨平台开发者来说,这一套流程并不友好。 特别是当你的项目主要在 Windows 或 Linux 下开发(例如 Flutter、React Na…...
Monorepo架构: Nx Cloud 扩展能力与缓存加速
借助 Nx Cloud 实现项目协同与加速构建 1 ) 缓存工作原理分析 在了解了本地缓存和远程缓存之后,我们来探究缓存是如何工作的。以计算文件的哈希串为例,若后续运行任务时文件哈希串未变,系统会直接使用对应的输出和制品文件。 2 …...
Linux安全加固:从攻防视角构建系统免疫
Linux安全加固:从攻防视角构建系统免疫 构建坚不可摧的数字堡垒 引言:攻防对抗的新纪元 在日益复杂的网络威胁环境中,Linux系统安全已从被动防御转向主动免疫。2023年全球网络安全报告显示,高级持续性威胁(APT)攻击同比增长65%,平均入侵停留时间缩短至48小时。本章将从…...
