约瑟夫环和一元多项式

约瑟夫环

一、问题描述    

假设有 n 个人围成一圈，从第一个人开始报数，报数到 m 的人将被淘汰出圈，然后从下一个人开始继续从 1 报数，如此重复，直到最后只剩下一个人。求最后剩下的这个人的编号。

二、问题分析

可以使用循环链表来模拟这个过程。

1.创建一个包含 n 个节点的循环链表，每个节点代表一个人，节点中存储这个人的编号。

2.从第一个节点开始报数，每报到 m，就将对应的节点从链表中删除。

3.重复这个过程，直到链表中只剩下一个节点，这个节点所代表的人的编号就是问题的答案。

数据元素：

数据元素之间的逻辑结构为线性结构

选择的存储结构为链式存储结构，因为有大量的删除操作，链式存储结构便于进行删除操作

三、举例分析    

例如，有 7 个人，从 1 开始报数，报到 3 的人被淘汰。

初始状态：1、2、3、4、5、6、7 围成一圈。

第一次报数：报到 3 的人被淘汰，此时圈子里剩下 1、2、4、5、6、7。

第二次报数：从 4 开始，报到 6 的人被淘汰，圈子里剩下 1、2、4、5、7。

第三次报数：从 7 开始，报到 2 的人被淘汰，圈子里剩下 1、4、5、7。

第四次报数：从 4 开始，报到 7 的人被淘汰，圈子里剩下 1、4、5。

第五次报数：从 1 开始，报到 5 的人被淘汰，圈子里剩下 1、4。

第六次报数：从 4 开始，报到 1 的人被淘汰，最后剩下 4。

所以，在这个例子中，最后剩下的人的编号是 4。

四、具体实现

#include <stdio.h>
#include <stdlib.h>// 定义链表节点结构
struct Node {int data;struct Node* next;
};// 创建循环链表
struct Node* createCircularList(int n) {struct Node* head = NULL;struct Node* prev = NULL;for (int i = 1; i <= n; i++) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));newNode->data = i;newNode->next = NULL;if (!head) {head = newNode;} else {prev->next = newNode;}prev = newNode;}prev->next = head;return head;
}// 解决约瑟夫环问题
int josephusProblem(int n, int m) {struct Node* current = createCircularList(n);struct Node* prev = NULL;while (current->next!= current) {for (int i = 1; i < m; i++) { //相当于计数prev = current;current = current->next;}prev->next = current->next;//这里是删除操作struct Node* temp = current;current = current->next;free(temp);}int result = current->data;free(current);return result;
}int main() {int n,m;     //n为总人数，m为报到的数scanf("%d %d",&n,&m);int lastPerson = josephusProblem(n, m);printf("最后剩下的人的编号是：%d\n", lastPerson);return 0;
}

以下是运行结果

也可以用数学公式解决这个问题

有N个人围成一圈（编号为1～N），从第1号开始进行1、2、3报数，凡报3者就退出，下一个人又从1开始报数……直到最后只剩下一个人时为止。请问此人原来的编号是多少?

输入格式:

在一行中给出1个不超过100的正整数N。

输出格式:

在一行中输出最后剩下那个人的编号。

输入样例:

10

输出样例:

4
#include<stdio.h>
int main()
{int n,m=3,i,s=0;scanf("%d",&n);for(i=2;i<=n;i++){s=(s+m)%i;}printf("%d",s+1);
}

 一元多项式运算

一、问题分析

1.一元多项式的表示    

一元多项式可以用链表来表示，每个节点表示多项式中的一项，包含系数和指数两个数据域。 例如，多项式     可以表示为三个节点的链表，第一个节点的系数为 3，指数为 2；第二个节点的系数为 2，指数为 1；第三个节点的系数为 1，指数为 0。

2.运算的实现    

加法：将两个多项式对应项的系数相加，如果指数相同则合并为一项，否则分别插入到结果多项式中。    

减法：与加法类似，但是需要将被减多项式的每一项系数取相反数后再进行加法运算

 

二、实现步骤

  1. 定义链表节点结构 
       struct PolyNode {int coef; // 系数int exp; // 指数struct PolyNode* next;};
  2. 创建多项式 输入多项式的项数，然后依次输入每一项的系数和指数，创建链表表示的多项式。 
       struct PolyNode* createPolynomial() {int n;printf("输入多项式的项数：");scanf("%d", &n);struct PolyNode* head = NULL;struct PolyNode* prev = NULL;for (int i = 0; i < n; i++) {struct PolyNode* newNode = (struct PolyNode*)malloc(sizeof(struct PolyNode));printf("输入第 %d 项的系数和指数：", i + 1);scanf("%d%d", &newNode->coef, &newNode->exp);newNode->next = NULL;if (!head) {head = newNode;} else {prev->next = newNode;}prev = newNode;}return head;}

  3. 打印多项式 遍历链表，按照系数和指数的格式输出多项式。
   void printPolynomial(struct PolyNode* head) {if (!head) {printf("0\n");return;}struct PolyNode* current = head;while (current) {if (current->coef!= 0) {if (current->coef > 0 && current!= head) {printf("+");}if (current->exp == 0) {printf("%d", current->coef);} else if (current->exp == 1) {printf("%dx", current->coef);} else {printf("%dx^%d", current->coef, current->exp);}}current = current->next;}printf("\n");}

 

4.多项式加法与减法 同时遍历两个多项式，比较指数大小，将对应项的系数相加，或者将较小指数的项直接插入到结果多项式中。

例如：

 

 A，B的存储结构示意图：

先比较A,B的第一个结点内的指数大小，显然0比1小，所以直接把A的第一个结点放进新的链表里。 然后用B的第一个结点与A的第二个结点的指数比较，两者都是1，如果是加法，把两个结点内的系数进行相加，如果是减法，把要减去的多项式的结点的系数变为相反数相加即可。 然后将得到的结果与系数组成一个新的结点，放进新的链表里。 以此类推。

加法：

   struct PolyNode* addPolynomial(struct PolyNode* poly1, struct PolyNode* poly2) {struct PolyNode* result = NULL;struct PolyNode* prev = NULL;struct PolyNode* current1 = poly1;struct PolyNode* current2 = poly2;while (current1 && current2) {struct PolyNode* newNode = (struct PolyNode*)malloc(sizeof(struct PolyNode));if (current1->exp > current2->exp) {newNode->coef = current1->coef;newNode->exp = current1->exp;current1 = current1->next;} else if (current1->exp < current2->exp) {newNode->coef = current2->coef;newNode->exp = current2->exp;current2 = current2->next;} else {newNode->coef = current1->coef + current2->coef;newNode->exp = current1->exp;current1 = current1->next;current2 = current2->next;}newNode->next = NULL;if (!result) {result = newNode;} else {prev->next = newNode;}prev = newNode;}while (current1) {struct PolyNode* newNode = (struct PolyNode*)malloc(sizeof(struct PolyNode));newNode->coef = current1->coef;newNode->exp = current1->exp;newNode->next = NULL;prev->next = newNode;prev = newNode;current1 = current1->next;}while (current2) {struct PolyNode* newNode = (struct PolyNode*)malloc(sizeof(struct PolyNode));newNode->coef = current2->coef;newNode->exp = current2->exp;newNode->next = NULL;prev->next = newNode;prev = newNode;current2 = current2->next;}return result;}

减法

   struct PolyNode* subtractPolynomial(struct PolyNode* poly1, struct PolyNode* poly2) {struct PolyNode* temp = poly2;while (temp) {temp->coef = -temp->coef;temp = temp->next;}return addPolynomial(poly1, poly2);}

 

多项式乘法 逐项相乘，将结果插入到结果多项式中，然后合并同类项。

   struct PolyNode* multiplyPolynomial(struct PolyNode* poly1, struct PolyNode* poly2) {struct PolyNode* result = NULL;struct PolyNode* current1 = poly1;while (current1) {struct PolyNode* current2 = poly2;while (current2) {struct PolyNode* newNode = (struct PolyNode*)malloc(sizeof(struct PolyNode));newNode->coef = current1->coef * current2->coef;newNode->exp = current1->exp + current2->exp;newNode->next = NULL;struct PolyNode* temp = result;struct PolyNode* prev = NULL;while (temp && temp->exp > newNode->exp) {prev = temp;temp = temp->next;}if (temp && temp->exp == newNode->exp) {temp->coef += newNode->coef;free(newNode);} else {if (!prev) {result = newNode;} else {prev->next = newNode;}newNode->next = temp;}current2 = current2->next;}current1 = current1->next;}return result;}

 

5.主函数 调用上述函数，实现多项式的输入、运算和输出

   int main() {struct PolyNode* poly1 = createPolynomial();struct PolyNode* poly2 = createPolynomial();printf("多项式 1：");printPolynomial(poly1);printf("多项式 2：");printPolynomial(poly2);struct PolyNode* sum = addPolynomial(poly1, poly2);printf("两多项式之和：");printPolynomial(sum);struct PolyNode* difference = subtractPolynomial(poly1, poly2);printf("两多项式之差：");printPolynomial(difference);struct PolyNode* product = multiplyPolynomial(poly1, poly2);printf("两多项式之积：");printPolynomial(product);return 0;}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/413187.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

DDR3详解

DDR3详解

1.DDR3简介 DDR3 SDRAM&#xff0c;全称第三代双倍速率同步动态随机存取存储器&#xff0c;简称 DDR3&#xff0c;双倍速率&#xff08;double-data-rate&#xff09;&#xff0c;是指时钟的上升沿和下降沿都发生数据传输&#xff1b;同步&#xff0c;是指DDR3数据的读取写入是…
阅读更多...
使用 nuxi build-module 命令构建 Nuxt 模块

使用 nuxi build-module 命令构建 Nuxt 模块

title: 使用 nuxi build-module 命令构建 Nuxt 模块 date: 2024/8/31 updated: 2024/8/31 author: cmdragon excerpt: nuxi build-module 命令是构建 Nuxt 模块的核心工具，它将你的模块打包成适合生产环境的格式。通过使用 --stub 选项，你可以在开发过程中加快模块构建速度…
阅读更多...
linux Vim的安装和基本使用

linux Vim的安装和基本使用

Vim 什么是 Vim Vim是一个高度可定制的文本编辑器&#xff0c;源自Unix系统的vi编辑器。它被广泛用于类Unix系统中&#xff0c;包括Linux、Mac OS和Windows平台。Vim特别受到程序员的青睐&#xff0c;因为它提供了丰富的编程功能&#xff0c;如代码补全、编译及错误跳转等。这…
阅读更多...
Kubernetes 上安装 Jenkins

Kubernetes 上安装 Jenkins

安装 Helm curl https://raw.githubusercontent.com/helm/helm/main/scripts/get-helm-3 | bash添加 Jenkins Helm 仓库 首先添加 Jenkins Helm 仓库 helm repo add jenkins https://charts.jenkins.io helm repo update安装 Jenkins 使用 Helm 安装 Jenkins 的最新版本&…
阅读更多...
产品经理角度分析：朋友圈点赞与评论仅共同好友可见

产品经理角度分析：朋友圈点赞与评论仅共同好友可见

你有没有在刷朋友圈时&#xff0c;看到某位朋友发了条状态&#xff0c;下面一堆点赞和评论&#xff0c;然后他自己来个“统一回复下&#xff0c;感谢大家”&#xff1f; 这种现象就像是在朋友圈里开了个小型新闻发布会&#xff0c;大家在台下疯狂举手&#xff0c;结果发言人最后…
阅读更多...
ip地址变化是什么意思？手机地址ip一直变化怎么办

ip地址变化是什么意思？手机地址ip一直变化怎么办

IP地址作为互联网设备的唯一标识&#xff0c;‌其稳定性对于网络连接至关重要。‌然而&#xff0c;‌手机IP地址频繁变动可能带来一系列问题。‌本文将深入探讨IP地址变化的含义、‌IP地址频繁变动的原因&#xff0c;‌以及提供手机地址IP一直变化的有效应对策略。‌ 一、IP地址…
阅读更多...
使用pgdump、pgrestore迁移数据表到docker部署的postgis

使用pgdump、pgrestore迁移数据表到docker部署的postgis

将本地数据同步到内网服务器&#xff0c;使用的postgis&#xff0c;表含空间字段 备份 本地使用pgadmin 4进行备份&#xff0c;pgrestore的命令参数找起来麻烦&#xff0c;这个可以界面操作&#xff0c;比较方便 说明 说明的截图来自pgadmin&#xff0c;点击这个打开 …
阅读更多...
GitLab私有代码仓库搭建与使用

GitLab私有代码仓库搭建与使用

文章目录 一、安装GitLab1、下载安装2、修改配置3、启动gitlab4、登录 二、使用1、ssh-key 参考资料 一、安装GitLab 1、下载安装 gitlab-ce的rpm包清华源地址&#xff1a; https://mirrors.tuna.tsinghua.edu.cn/gitlab-ce/yum/el7/?CN&OD 本次使用gitlab-ce-17.1.1-c…
阅读更多...
论文精读：JACS —— Sb2Si2Te6与Sc2Si2Te6热电性能

论文精读：JACS —— Sb2Si2Te6与Sc2Si2Te6热电性能

摘要节选: 本文以层状Sb2Si2Te6和Sc2Si2Te6为模型体系&#xff0c;采用密度泛函理论结合半经典玻尔兹曼输运理论&#xff0c;全面研究和比较了它们的热电性能。 由于较低的散射率和更明显的带色散&#xff0c;Sb2Si2Te6与Sc2Si2Te6相比具有优越的导电性。 在将导带轨道特性从…
阅读更多...
【微信小程序】SpringBoot集成微信小程序（多小程序集成）

【微信小程序】SpringBoot集成微信小程序（多小程序集成）

SpringBoot集成微信小程序 前言一、前置工作1、获取appId和appSecret核心参数 二、SpringBoot集成微信小程序1、引入pom依赖2、yml配置3、java代码文件3.1、Properties 配置类3.2 Configuration 服务类 4、使用示例4.1、获取登录后的session信息&#xff1a;openId4.2、获取当前…
阅读更多...
若依框架 MyBatis 改为 MyBatis-Plus 的实现步骤

若依框架 MyBatis 改为 MyBatis-Plus 的实现步骤

本文只做了简单的实现&#xff0c;具体的细节需根据自己的需求进一步实现。如果实现中遇到问题欢迎留言讨论。 引入 MyBatis-Plus 引入相关依赖&#xff08;pom.xml&#xff09; 推荐先直接在顶级 pom.xml 中直接依赖&#xff0c;等调试通过之后&#xff0c;在去按需依赖&…
阅读更多...
理解进程与线程

理解进程与线程

1.1理解分时技术 随着计算器处理能力的逐步提高&#xff0c;计算机处理多道程序成为了可能。 所谓分时技术&#xff0c;就是把处理器的运行时间分成很短的时间片&#xff0c;按时间片轮流把处理器给各程序使用。这样在时间线上表现为线性&#xff0c;但是在体感上感觉是一起执…
阅读更多...
Java:时区的用法

Java:时区的用法

文章目录 ZoneId常见用法 ZonedDateTime常见方法 代码 黑马学习笔记 ZoneId 常见用法 ZonedDateTime 常见方法 代码 package NewTime;import java.time.Clock; import java.time.ZoneId; import java.time.ZonedDateTime;/*** Author: ggdpzhk* CreateTime: 2024-08-31*/ pu…
阅读更多...
后台框架-统一数据格式2

后台框架-统一数据格式2

在上一篇中&#xff0c;当在Controller类中需要返回统一格式的数据时&#xff0c;需要实例化一个R&#xff0c;有时候觉得还是不够简洁&#xff0c;那有没有一种方法Controller中直接返回对象&#xff0c;但是返回的对象统一保存到如下格式的data中&#xff1f; ResponseBody…
阅读更多...
YASKAWA机器人维修操作命令攻略-移动命令运用案例

YASKAWA机器人维修操作命令攻略-移动命令运用案例

移动命令 1. MOVJ 命令运用案例&#xff1a; MOVJ VJ50.00 PL2 NWAIT UNTIL IN(1)ON 含义&#xff1a;在这个点以关节坐标&#xff0c;按 50.00%的再现速度&#xff0c;定位精度为 2&#xff0c;同时执行下一条非移动 指令&#xff0c;判断输入信号 1 为 on 后&#xff0c;执行…
阅读更多...
【Python机器学习】NLP词频背后的含义——距离和相似度

【Python机器学习】NLP词频背后的含义——距离和相似度

我们可以使用相似度评分&#xff08;和距离&#xff09;&#xff0c;根据两篇文档的表示向量间的相似度&#xff08;或距离&#xff09;来判断文档间有多相似。 我们可以使用相似度评分&#xff08;和举例&#xff09;来查看LSA主题模型与高维TF-IDF模型之间的一致性。在去掉了…
阅读更多...
Windows中pip换源

Windows中pip换源

step1&#xff1a;检查是否安装 输入如下&#xff0c;出现版本号&#xff0c;就是安装好了 pip -V或pip --version pip3 -V pip3 --version step2&#xff1a;找到&#xff08;创建&#xff09;配置文件 对于 Windows 用户&#xff0c;配置文件在【%APPDATA%\pip\pip.ini】文…
阅读更多...
C语言典型例题56

C语言典型例题56

《C程序设计教程&#xff08;第四版&#xff09;——谭浩强》 例题4.8 将范围为100~200的不能被3整除的数输出。 代码&#xff1a; //《C程序设计教程&#xff08;第四版&#xff09;——谭浩强》 //例题4.8 将范围为100~200的不能被3整除的数输出。//#include <stdio.h>…
阅读更多...
【B端产品知识总结】系统消息提醒及消息推送设计思想

【B端产品知识总结】系统消息提醒及消息推送设计思想

目录 前言 一、简述消息通知 1、第一步盘点消息推送渠道 2、第二步消息推送项盘点 3、第三步确定消息通知内容和操作反馈 二、系统消息项通知梳理 1、明确消息推送渠道 2、盘点产品业务消息项 3、撰写通知内容与操作反馈 三、如何设计消息中心 ⒈、设计消息中心入口&…
阅读更多...
Java：路径计算与障碍物处理

Java：路径计算与障碍物处理

Java 实现寻找字符串数组中的最长公共前缀及不同路径数量计算&#xff08;含障碍物&#xff09; 在计算机科学和软件开发中&#xff0c;经常需要解决一些基本但实用的问题。本文将介绍两种常见问题的解决方案&#xff1a;一是从一组字符串中找出最长公共前缀&#xff1b;二是计…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023