约瑟夫环和一元多项式

2024-08-31 23:28
文章标签 多项式 一元 约瑟夫

本文主要是介绍约瑟夫环和一元多项式，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

约瑟夫环

一、问题描述    

假设有 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.chinasem.cn/article/1125294。

相关文章

poj3750约瑟夫环，循环队列

poj3750约瑟夫环，循环队列

Description 有N个小孩围成一圈，给他们从1开始依次编号，现指定从第W个开始报数，报到第S个时，该小孩出列，然后从下一个小孩开始报数，仍是报到S个出列，如此重复下去，直到所有的小孩都出列（总人数不足S个时将循环报数），求小孩出列的顺序。 Input 第一行输入小孩的人数N（N<=64） 接下来每行输入一个小孩的名字(人名不超过15个字符) 最后一行输入W,S (W < N)，用
阅读更多...
PHP约瑟夫环问题

PHP约瑟夫环问题

#循环 function circle($arr,$idx,$k){for($i=0;$i<$idx;$i++){$tmp = array_shift($arr);array_push($arr,$tmp);}$j = 1;while(count($arr) > 0){$tmp = array_shift($arr);if($j++%$k == 0){echo $tmp."\n";}else{a
阅读更多...
一些数学经验总结——关于将原一元二次函数增加一些限制条件后最优结果的对比（主要针对公平关切相关的建模）

一些数学经验总结——关于将原一元二次函数增加一些限制条件后最优结果的对比（主要针对公平关切相关的建模）

1.没有分段的情况 原函数为一元二次凹函数（开口向下），如下： 因为要使得其存在正解，必须满足，那么。 上述函数的最优结果为：，。 对应的mathematica代码如下： Clear["Global`*"]f0[x_, a_, b_, c_, d_] := (a*x - b)*(d - c*x);(*(b c+a d)/(2 a c)*)Maximize[{f0[x, a, b,
阅读更多...
一元分类、二元分类、多类分类、多标签学习

一元分类、二元分类、多类分类、多标签学习

unary classification -- 一元分类 维基百科中的定义是：一类分类，即一元分类，通过仅包含该类的对象的训练数据中学习，试图能够在所有对象中识别该特定类的对象。 one-class classification是由[Moya & Hush][1]在1996年提出的，目前已有很多这方面的研究。一个类似的问题是PU Learning，后者是以半监督的学习方式从正类样本和未标记样本
阅读更多...
算法笔记02--归纳法之多项式求值（Horner规则）

算法笔记02--归纳法之多项式求值（Horner规则）

多项式求值 假设有n+2个实数a0,a1,...,an和x的序列，求多项式 p_nx = a_nx^n + a_n-1x^n-1 + ...+ a_1x + a_0; 则需要乘法：n+n-1 + ...+2+1 = n(n+1)/2 需要加法：n 可见算法效率为O（n^2） 而p_nx = ((...((((a_n)x + a_n-1)x + a_n-2)x + a_n-3)....)
阅读更多...
约瑟夫问题(多解)——POJ 3750

约瑟夫问题(多解)——POJ 3750

对应POJ题目：点击打开链接 小孩报数问题 Time Limit: 1000MS Memory Limit: 65536KB 64bit IO Format: %I64d & %I64u Submit Status Description 有N个小孩围成一圈，给他们从1开始依次编号，现指定从第W个开始报数，报到第S个时，该小孩出列，然后从下一个小孩开始报数，
阅读更多...
约瑟夫问题的五种实现方法

约瑟夫问题的五种实现方法

一、队列 #include <stdio.h>#include <queue>using namespace std;queue<int> q;int n, m, cnt, out, a[101]; //a[i]=0表示在圈里 int main(){scanf("%d %d", &n, &m);for(int i=1; i<=n; i++){q.push(i);}while(!q
阅读更多...
链表（篇5）用链表实现多项式相加

链表（篇5）用链表实现多项式相加

使用链接实现两个多项式相加 例： 输入：第一数= 5x ^ 2 + 4x ^ 1 + 2x ^ 0第二数= 5x ^ 1 + 5x ^ 0输出：5x ^ 2 + 9x ^ 1 + 7x ^ 0输入：第一数= 5x ^ 3 + 4x ^ 2 + 2x ^ 0第二数= 5x ^ 1 + 5x ^ 0输出：5x ^ 3 + 4x ^ 2 + 5x ^ 1 + 7x ^ 0 代码
阅读更多...
【机器学习】基扩展的基本概念以及其中的多项式回归、样条方法和广义可加模型的简单介绍（含python代码实例）

【机器学习】基扩展的基本概念以及其中的多项式回归、样条方法和广义可加模型的简单介绍（含python代码实例）

引言 基扩展是提升模型性能的重要工具，正确选择和应用基扩展方法可以显著提高模型的预测能力和解释性 文章目录 引言一、基扩展1.1 基扩展定义1.2 基扩展方法1.2.1 多项式基扩展1.2.2 样条基扩展1.2.3 径向基函数（RBF）1.2.4 傅里叶基扩展1.2.5 wavelet基扩展1.2.6 单隐藏层神经网络 1.3 应用场景1.4 使用基扩展的注意点 二、多项式回归2.
阅读更多...
理解 约瑟夫环

理解 约瑟夫环

总结了个小经验，有时候光靠看是看不出什么端倪来的，还必须得动下笔，比划比划也许就那么简单 #include <stdio.h> #include <stdlib.h> typedef struct Node {  int data;  struct Node *next; }Node;   Node *CreatList(int n)    //创建一个含n个人的循环链表 { int i;
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2