当前位置: 首页 > news >正文

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++模拟揭秘刘谦魔术,领略数学的魅力

新的一年又开始了&#xff0c;大家新年好呀~。在这我想问大家一个问题&#xff0c;有没有同学看了联欢晚会上刘谦的魔术呢&#xff1f; 这个节目还挺有意思的&#xff0c;它最出彩的不是魔术本身&#xff0c;而是小尼老师“念错咒语”而导致他手里的排没有拼在一起&#xff0c;…...

JAVA语言编写一个方法,两个Long参数传入,使用BigDecimal类,计算相除四舍五入保留2位小数返回百分数。

在Java中&#xff0c;你可以使用BigDecimal类来执行精确的浮点数计算&#xff0c;并且可以指定结果的小数位数。以下是一个方法&#xff0c;它接受两个Long类型的参数&#xff0c;并使用BigDecimal来计算它们的商&#xff0c;然后将结果四舍五入到两位小数&#xff0c;并返回一…...

SQL教学:掌握MySQL数据操作核心技能--DML语句基本操作之“增删改查“

大家好&#xff0c;今天我要给大家分享的是SQL-DML语句教学。DML&#xff0c;即Data Manipulation Language&#xff0c;也就是我们常说的"增 删 改 查"&#xff0c;是SQL语言中用于操作数据库中数据的一部分。作为MySQL新手小白&#xff0c;掌握DML语句对于数据库数…...

【性能测试】Jmeter性能压测-阶梯式/波浪式场景总结(详细)

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 1、阶梯式场景&am…...

前端面试 跨域理解

2 实现 2-1 JSONP 实现 2-2 nginx 配置 2-2 vue 开发中 webpack自带跨域 2 -3 下载CORS 插件 或 chrome浏览器配置跨域 2-4 通过iframe 如&#xff1a;aaa.com 中读取bbb.com的localStorage 1)在aaa.com的页面中&#xff0c;在页面中嵌入一个src为bbb.com的iframe&#x…...

JetBrains TeamCity 身份验证绕过漏洞复现(CVE-2024-27198)

0x01 产品简介 JetBrains TeamCity是一款由JetBrains开发的持续集成和持续交付(CI/CD)服务器。它提供了一个功能强大的平台,用于自动化构建、测试和部署软件项目。TeamCity旨在简化团队协作和软件交付流程,提高开发团队的效率和产品质量。 0x02 漏洞概述 JetBrains Team…...

设计模式—单例模式

单例模式&#xff08;Singleton Pattern&#xff09;是一种常用的软件设计模式&#xff0c;其核心思想是确保一个类仅有一个实例&#xff0c;并提供一个全局访问点来获取这个实例。单例模式主要用于控制资源的访问&#xff0c;比如配置文件的读取&#xff0c;数据库的连接等&am…...

Android在后台读取UVC摄像头的帧数据流并推送

Android在后台读取UVC摄像头的帧数据流并推送 添加UvcCamera依赖库 使用原版的 saki4510t/UVCCamera 在预览过程中断开可能会闪退&#xff0c;这里使用的是 jiangdongguo/AndroidUSBCamera 中修改的版本&#xff0c;下载到本地即可。 https://github.com/jiangdongguo/AndroidU…...

vue单向数据流介绍

Vue.js 的单向数据流是其核心设计原则之一&#xff0c;也是 Vue 响应式系统的基础。在 Vue.js 中&#xff0c;数据流主要是单向的&#xff0c;从父组件流向子组件。这种设计有助于保持组件之间的清晰通信&#xff0c;减少不必要的复杂性和潜在的错误。 以下是 Vue 单向数据流的…...

OpenMMlab AI实战营第四期培训

OpenMMlab AI实战营第四期培训 OpenMMlab实战营第四次课2023.2.6学习参考一、什么是目标检测1.目标检测下游视觉任务2.图像分类 v.s. 目标检测 二、目标检测实现1.滑窗 Sliding Window2.滑窗的效率问题3.改进思路&#xff08;1&#xff09;消除滑窗中的重复计算&#xff08;2&a…...

React轻松开发平台:实现高效、多变的应用开发范本

在当今快节奏的软件开发环境中&#xff0c;追求高效、灵活的应用开发方式成为了开发团队的迫切需求。React低代码平台崭露头角&#xff0c;为开发人员提供了一种全新的开发范式&#xff0c;让开发过程更高效、更灵活&#xff0c;从而加速应用程序的开发周期和交付速度。 1. 快…...

多域名SSL证书:保护多个网站的安全之选

什么是多域名SSL证书&#xff1f; 多域名SSL证书&#xff0c;顾名思义&#xff0c;是指一张SSL证书可以保护多个域名。与传统的单域名SSL证书相比&#xff0c;多域名SSL证书可以在一个证书中绑定多个域名&#xff0c;无需为每个域名单独购买和安装SSL证书。这样不仅可以节省成…...

HarmonyOS—HAP唯一性校验逻辑

HAP是应用安装的基本单位&#xff0c;在DevEco Studio工程目录中&#xff0c;一个HAP对应一个Module。应用打包时&#xff0c;每个Module生成一个.hap文件。 应用如果包含多个Module&#xff0c;在应用市场上架时&#xff0c;会将多个.hap文件打包成一个.app文件&#xff08;称…...

金三银四,程序员如何备战面试季

金三银四&#xff0c;程序员如何备战面试季 一个人简介二前言三面试技巧分享3.1 自我介绍 四技术问题回答4.1 团队协作经验展示 五职业规划建议5.1 短期目标5.2 中长期目标 六后记 一个人简介 &#x1f3d8;️&#x1f3d8;️个人主页&#xff1a;以山河作礼。 &#x1f396;️…...

VUE3项目学习系列--项目配置(二)

在项目团队开发过程中&#xff0c;多人协同开发为保证项目格式书写格式统一标准化&#xff0c;因此需要进行代码格式化校验&#xff0c;包括在代码编写过程中以及代码提交前进行自动格式化&#xff0c;因此需要进行在项目中进行相关的配置使之代码格式一致。 一、eslint配置 …...

idea:springboot项目搭建

目录 一、创建项目 1、File → New → Project 2、Spring Initializr → Next 3、填写信息 → Next 4、web → Spring Web → Next 5、填写信息 → Finish 6、处理配置不合理内容 7、注意事项 7.1 有依赖包&#xff0c;却显示找不到依赖&#xff0c;刷新一下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语言有哪些优点、特性&#xff1f; 语法简便&#xff0c;容易上手。 支持高并发&#xff0c;go有独特的协程概念&#xff0c;一般语言最小的执行单位是线程&#xff0c;go语言支持多开协程&#xff0c;协程是用户态线程&#xff0c;协程的占用内存更少&#xff0c;协程只…...

探索Python编程世界:从入门到精通

一.Python 从入门到精通 随着计算机科学的发展&#xff0c;编程已经成为了一种必备的技能。而 Python 作为一种简单易学、功能强大的编程语言&#xff0c;越来越受到人们的喜爱。本文将为初学者介绍 Python 编程的基础知识&#xff0c;帮助他们踏入 Python 编程的大门&#xf…...

Spark Shuffle Tracking 原理分析

Shuffle Tracking Shuffle Tracking 是 Spark 在没有 ESS(External Shuffle Service)情况&#xff0c;并且开启 Dynamic Allocation 的重要功能。如在 K8S 上运行 spark 没有 ESS。本文档所有的前提都是基于以上条件的。 如果开启了 ESS&#xff0c;那么 Executor 计算完后&a…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

STM32HAL库USART源代码解析及应用

STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...