当前位置: 首页 > 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;
}

好啦,同学们自己试一试吧~

相关文章:

  • Python 程序基本结构的使用
  • 循环队列:一道使数据结构萌新知道什么是“愁滋味“的题目
  • 字符串逆序
  • web坦克大战小游戏
  • Verilog参数、Verilog参数和属性冲突、整数处理
  • 【ArcPy】简化ArcGISPro默认Python环境体量
  • YOLOv8从入门到入土使用教程!(二)目标预测
  • QT使用FFMPEG库开发视频播放器
  • 惠普 DsekJet GT 5810/5820常见问题及解决方法
  • 低代码平台开发——基于React(文末送书)
  • MySQL相关问题
  • NLP_文本特征处理_4(代码示例)
  • 初级软件测试面试题
  • 计算机组成原理-第四章 指令系统【期末复习|考研复习】
  • Python与HTTP服务交互
  • [数据结构]链表的实现在PHP中
  • 【RocksDB】TransactionDB源码分析
  • Apache的80端口被占用以及访问时报错403
  • AzureCon上微软宣布了哪些容器相关的重磅消息
  • bootstrap创建登录注册页面
  • Git同步原始仓库到Fork仓库中
  • HTTP中的ETag在移动客户端的应用
  • JAVA_NIO系列——Channel和Buffer详解
  • JavaScript创建对象的四种方式
  • Java基本数据类型之Number
  • js对象的深浅拷贝
  • linux安装openssl、swoole等扩展的具体步骤
  • socket.io+express实现聊天室的思考(三)
  • Spring Cloud Alibaba迁移指南(一):一行代码从 Hystrix 迁移到 Sentinel
  • 关于springcloud Gateway中的限流
  • 理解在java “”i=i++;”所发生的事情
  • 十年未变!安全,谁之责?(下)
  • 我的zsh配置, 2019最新方案
  • 吴恩达Deep Learning课程练习题参考答案——R语言版
  • 在electron中实现跨域请求,无需更改服务器端设置
  • JavaScript 新语法详解:Class 的私有属性与私有方法 ...
  • python最赚钱的4个方向,你最心动的是哪个?
  • 湖北分布式智能数据采集方法有哪些?
  • 机器人开始自主学习,是人类福祉,还是定时炸弹? ...
  • 正则表达式-基础知识Review
  • ​【已解决】npm install​卡主不动的情况
  • ![CDATA[ ]] 是什么东东
  • $ is not function   和JQUERY 命名 冲突的解说 Jquer问题 (
  • (02)Hive SQL编译成MapReduce任务的过程
  • (待修改)PyG安装步骤
  • (附源码)python旅游推荐系统 毕业设计 250623
  • (附源码)springboot金融新闻信息服务系统 毕业设计651450
  • (附源码)springboot学生选课系统 毕业设计 612555
  • (附源码)springboot掌上博客系统 毕业设计063131
  • (附源码)ssm考试题库管理系统 毕业设计 069043
  • (附源码)基于SpringBoot和Vue的厨到家服务平台的设计与实现 毕业设计 063133
  • (黑马出品_高级篇_01)SpringCloud+RabbitMQ+Docker+Redis+搜索+分布式
  • (每日持续更新)jdk api之FileFilter基础、应用、实战
  • (未解决)jmeter报错之“请在微信客户端打开链接”
  • (一)为什么要选择C++