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

数组与链表算法-数组与多项式

目录

数组与链表算法-数组与多项式

多项式数组表达式

C++代码


数组与链表算法-数组与多项式

多项式是数学中相当重要的表达方式,如果使用计算机来处理多项式的各种相关运算,那么通常使用数组或链表来存储多项式。

多项式数组表达式

假如一个多项P(X) = a_{n}X^{n} + a_{n-1}X^{n-1} + ... + a_{1}X + a_{0},这个多项式P(X)就被称为n次多项式。一个多项式如果使用数组结构存储在计算机中的话,表示法有以下两种:

(1)使用一个n+2长度的一维数组来存放,数组的第一个位置存储多项式的最大指数n,数组之后的各个位置从指数n开始,依次递减按序存储对应项的系数:

        P = (n, a_{n}, a_{n-1}, ... , a_{1}, a_{0})

存储在A(1:n+2)中,例如P(X) = 2X^{5} + 3X^{4} + 5X^{2} + 4X + 1,可转换为A数组来表示,例如:

        A = [5, 2, 3, 0, 5, 4, 1]

使用这种表达法的优点是在计算机中运用时,对于多项式各种运算(如加法与乘法)的设计比较方便。不过,如果多项式的系数为多半为零,例如X^{100}+1,就太浪费内存空间了。

C++代码

#include<iostream>
using namespace std;

void PolySum(int* arrA, int* arrB, int* arrResoult) {
	arrResoult[0] = arrA[0];
	for (int i = 1; i < arrA[0] + 2; i++) {
		arrResoult[i] = arrA[i] + arrB[i];		
	}
}

void PrintPoly(int* arr) {
	int MaxExp = arr[0];
	for (int i = 1; i < arr[0] +2; i++) {
		if (arr[i] != 0) {
			if (MaxExp != 0)
				cout << arr[i] << "X^" << MaxExp << " ";
			else
				cout << arr[i];
			if (MaxExp - 1 >= 0)
				cout << " + ";
		}
		MaxExp--;
	}
	cout << endl;
}

int main() {
	int* PolyA = new int[]{ 4,3,7,0,6,2 };
	int* PolyB = new int[]{ 4,1,5,2,0,9 };
	int* PolyResoult = new int[PolyA[0]+2] {0};
	cout << "多项式A:";
	PrintPoly(PolyA);
	cout << "多项式B:";
	PrintPoly(PolyB);
	PolySum(PolyA, PolyB, PolyResoult);
	cout << "A + B =  ";
	PrintPoly(PolyResoult);
	return 0;
}

输出结果

(2)只存储多项式中的非零项。如果有m个非零项,就使用2m+1长的数组来存储每一个非零项的指数及系数,但数组的第一个元素存储的是这个多项式非零项的个数。

例如P(X) = 2X^{5} + 3X^{4} + 5X^{2} + 4X + 1,可表示成A(1:2m+1)数组,如下所示:

        A = \left \{ 5, 2, 5, 3, 4, 5, 2, 4, 1, 1, 0 \right \}

这种方法的优点是在多项式零项较多时可以减少对内存空间的浪费,但缺点是在为多项式设计各种运算时会复杂许多。

使用多项式的两种数组表示法来存储多项式P(X) = 8X^{5} + 7X^{4} + 5X^{2} + 12,结果如下:

  • P = (5, 8, 7, 0, 5, 0, 12) 
  • P = (5, 8, 5, 7, 4, 5, 2, 12, 0)

注意,在上面这个例子中,第二种数组表示法并没有体现出减少对内存空间的浪费的优点,这是因为多项式P(X)的零项并不多,只是缺了X^{3}X这两项。


http://www.kler.cn/a/108457.html

相关文章:

  • window安装TradingView
  • 汽车IVI中控开发入门及进阶(44):杰发科智能座舱芯片
  • JavaScript中函数调用时的参数传递
  • Gin-vue-admin(1):环境配置和安装
  • nest 学习3
  • java全栈day19--Web后端实战(java操作数据库3)
  • 速卖通商品详情API接口获取aliexpress速卖通商品详情信息、销量、价格、商品规格信息参数调用示例说明
  • vue2 quill 视频上传 ,基于ruoyi vue,oss
  • 『阿里云盘 AList Kodi』家庭影院搭建指南
  • 本机spark 通idea连接Oracle的坑
  • Redis原理-IO模型和持久化
  • LeetCode 2656. K 个元素的最大和【数学】简单
  • 基于springboot实现休闲娱乐代理售票平台系统项目【项目源码+论文说明】
  • 数据库MySQL(五):多表查询
  • 【转信创】银河麒麟:系统安全机制
  • 【LeetCode每日一题合集】2023.10.23-2023.10.29(简单的一周)
  • SparkSQL综合案例-省份维度的销售情况统计分析
  • 【深度学习】Python使用指定gpu运行代码
  • 基于 matplotlib 实现的基本排序算法的动态可视化项目源码,通过 pyaudio 增加音效,冒泡、选择、插入、快速等排序
  • RabbitMQ (4)
  • 机器学习之IV编码,分箱WOE编码
  • 云起无垠典型案例入选《2023软件供应链安全洞察》报告
  • MySQL-DQL【数据查询语言】(图码结合)
  • 首次cmake 多目录构建失败
  • 微信小程序 slot 不显示
  • 私有云:【3】NFS存储服务器的安装