• 多项式乘法c语言
2019-10-26 14:53:45

本文代码中FFT使用递归版本实现

FFT加速多项式乘法原理不多说了，直接贴代码如下：

在vs2017上测试成功

#include "pch.h"
#define _CRT_SECURE_NO_WARNINGS
#include "stdlib.h"
#include "math.h"
#include "stdio.h"

#define N 8
#define MAXN 100

#define Pi  3.1415927   //定义圆周率Pi
#define LEN sizeof(struct Compx)  //定义复数结构体大小

//-----定义复数结构体-----------------------
typedef struct Compx
{
double real;
double imag;
}Compx;

//-----复数乘法运算函数---------------------
struct Compx mult(struct Compx b1, struct Compx b2)
{
struct Compx b3;
b3.real = b1.real*b2.real - b1.imag*b2.imag;
b3.imag = b1.real*b2.imag + b1.imag*b2.real;
return(b3);
}

//-----复数减法运算函数---------------------
struct Compx sub(struct Compx a, struct Compx b)
{
struct Compx c;
c.real = a.real - b.real;
c.imag = a.imag - b.imag;
return(c);
}

//-----复数加法运算函数---------------------
struct Compx add(struct Compx a, struct Compx b)
{
struct Compx c;
c.real = a.real + b.real;
c.imag = a.imag + b.imag;
return(c);
}

void fft(Compx *a, int n, int inv);

int main()
{
int i;

int x[N] = { 0 }, y[N] = { 0 };

printf("\nN=%d\n" , N);
printf("\n输入两个多项式的系数，输入系数为N多项式长度的一半\n");
printf("\n输入第一个多项式的系数\n");
for (i = 0; i < N/2; i++)
{
scanf("%d", &x[i]);
}

printf("\n输入第二个多项式的系数\n");
for (i = 0; i < N/2; i++)
{
scanf("%d", &y[i]);
}

struct  Compx * a = (struct Compx *)malloc(N*LEN);			//为结构体分配存储空间
struct  Compx * b = (struct Compx *)malloc(N*LEN);
struct  Compx * c = (struct Compx *)malloc(N*LEN);

//初始化=======================================
printf("\na多项式初始化：\n");
for (i = 0; i < N; i++)
{
a[i].real = x[i];
a[i].imag = 0;
printf("%.4f ", a[i].real);
printf("+%.4fj  ", a[i].imag);
printf("\n");
}
printf("\nb多项式初始化：\n");
for (i = 0; i < N; i++)
{
b[i].real = y[i];
b[i].imag = 0;
printf("%.4f ", b[i].real);
printf("+%.4fj  ", b[i].imag);
printf("\n");
}
printf("\n结果c多项式初始化：\n");
for (i = 0; i < N; i++)
{
c[i].real = 0;
c[i].imag = 0;
printf("%.4f ", c[i].real);
printf("+%.4fj  ", c[i].imag);
printf("\n");
}

fft(a, N, 1);

printf("\n第一个多项式FFT计算结果：\n");
for (i = 0; i < N; i++)
{
printf("%.4f ", a[i].real);
printf("+%.4fj  ", a[i].imag);
printf("\n");
}

fft(b, N, 1);

printf("\n第二个多项式FFT计算结果：\n");
for (i = 0; i < N; i++)
{
printf("%.4f ", b[i].real);
printf("+%.4fj  ", b[i].imag);
printf("\n");
}

for (i = 0; i < N; i++)
a[i] = mult(a[i] , b[i]);

fft(a, N, -1);
for (i = 0; i < N; i++) {
c[i].real = a[i].real / N;
c[i].imag = a[i].imag / N;
}

printf("\n乘积多项式结果：\n");
for (i = 0; i < N; i++)
{
printf("%.4f ", c[i].real);
printf("+%.4fj  ", c[i].imag);
printf("\n");
}

return 0;
}

void fft(Compx *a, int n, int inv) {
if (n == 1)return;
int mid = n / 2;
static Compx b[MAXN];
int i;
for (i = 0; i < mid; i++) {
b[i] = a[i * 2];
b[i + mid] = a[i * 2 + 1];
}

for (i = 0; i < n; i++)
a[i] = b[i];
fft(a, mid, inv);
fft(a + mid, mid, inv);//分治
for (i = 0; i < mid; i++)
{
Compx x;
x.real = cos(2 * Pi*i / n);
x.imag = inv * sin(2 * Pi*i / n);

b[i] = add(a[i], mult(x, a[i + mid]));
b[i + mid] = sub(a[i] , mult(x , a[i + mid]));
}
for (i = 0; i < n; i++)
a[i] = b[i];
}

更多相关内容
• 105 多项式乘法 C语言源代码文件
• 多项式乘法 什么是多项式？ 由若干个单项式相加组成的代数式叫做多项式（若有减法：减一个数等于加上它的相反数）。 多项式中的每个单项式叫做多项式的项，这些单项式中的最高项次数，就是这个多项式的次数。 ...

# 多项式乘法

#### 什么是多项式？

由若干个单项式相加组成的代数式叫做多项式（若有减法：减一个数等于加上它的相反数）。
多项式中的每个单项式叫做多项式的项，这些单项式中的最高项次数，就是这个多项式的次数。 多项式中不含字母的项叫做常数项。

#### 在C语言中怎么表示？

最简单直观的方式就是：

将多项式对应的系数储存在数组中，而数组下标就是项的指数

#### 最后写出相应的代码

#include <stdio.h>

int main()
{
int i, j, m, n;

scanf("%d", &m);
double a[m + 1];
for (i = 0; i <= m; i++)
scanf("%lf", &a[i]);

scanf("%d", &n);
double b[n + 1];
for (i = 0; i <= n; i++)
scanf("%lf", &b[i]);

double c[m + n + 1];
for (i = 0; i <= m + n; i++)
c[i] = 0;

for (i = 0; i <= m; i++)
for (j = 0; j <= n; j++)
c[i + j] += a[i] * b[j];

printf("%f*x^%d", c[0], 0);
for (i = 1; i <= m + n; i++)
printf(" + %f*x^%d", c[i], i);

return 0;
}


### 测试一下

#### 例如

(1 + 2x + 3x ^2)·(1 + 2x)=1 + 4x + 7x ^2 + 6x ^3

#### 下一篇：多项式除法

https://blog.csdn.net/m0_52313753/article/details/112585857

展开全文
• 1.多项式表示 数据结构设计 //将struct与typedef分开定义 typedef struct PolyNode *Polynomial; //使用 typedef 给一个还未完全声明的类型 PolyNode 起了一个新别名Polynomial struct PolyNode{ int coef; //...

# 设计函数分别求两个一元多项式的乘积与和。

### 输入格式:

输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。

### 输出格式:

输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。

### 输入样例:

4 3 4 -5 2 6 1 -2 0
3 5 20 -7 4 3 1

### 输出样例:

15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0

## 求解思路

### 1.多项式表示

#### 数据结构设计

//将struct与typedef分开定义
typedef struct PolyNode *Polynomial;	//使用 typedef 给一个还未完全声明的类型 PolyNode 起了一个新别名Polynomial
struct PolyNode{
int coef;			//系数
int expon;			//指数
};


### 2.程序框架

int main()
{
Polynomial P1,P2,PP,PS;
//读入多项式1，P1、P2都是链表结构的指针
//读入多项式2
//乘法运算并输出，返回的也是指针
PP=Mult(P1,P2);
PrintPoly(PP);
//加法运算并输出
PrintPoly(PS);
return 0;
}


### 3.读多项式

题目要求先输入有多少项，再一对对输入系数和指数，中间用空格分隔

Rear初值是多少？

两种处理方法：

1. Rear初值为NULL，在Attach函数中根据Rear是否为NULL做不同处理
2. Rear指向一个空结点，最后再删除空结点（一致性更强）
Polynomial ReadPoly()
{
Polynomial P,Rear,t;
int c,e,N;
//先读入一个整数
scanf("%d",&N);
//链表头空结点
P=(Polynomial)malloc(sizeof(struct PolyNode));
Rear=P;
//再一对对读系数指数
while(N--)
{
scanf("%d %d",&c,&e);
//每读入一个结点，插在当前结果表达式的后面。rear要改变，所以传指针
Attach(c,e,&Rear);
}
//删除临时生成的头节点
t=P;
free(t);
return P;
}


//传入系数、指数、Polynomial类型的指针（Polynomial本身也是指针）
void Attach(int c,int e,Polynomial *pRear)
{
Polynomial P;

//申请新结点，结点类型为结构体PolyNode
P=(Polynomial)malloc(sizeof(struct PolyNode));
//对新结点赋值
P->coef=c;
P->expon=e;
*pRear=P;	//修改pRear的值
}



### 4.加法实现

int compare(int e1,int e2){
if(e1>e2) return 1;
else if(e1<e2) return -1;
else return 0;
}

Polynomial PS,rear,temp;
int sum;
//构造空结点，rear指向当前处理结果的尾巴
PS=(Polynomial)malloc(sizeof(struct PolyNode));
rear=PS;
while(P1&&P2){
switch(compare(P1->expon,P2->expon)){
case 1:
Attach(P1->coef,P1->expon,&rear);
break;
case -1:
Attach(P2->coef,P2->expon,&rear);
break;
case 0:
sum=P1->coef+P2->coef;
if(sum) Attach(sum,P1->expon,&rear);//coef=0 then do nothing
break;
}
}
while(P1){
Attach(P1->coef,P1->expon,&rear);
}
while(P2){
Attach(P2->coef,P2->expon,&rear);
}
temp=PS;
free(temp);
return PS;
}


### 5.乘法实现

将P1当前项(c1i,e1i)乘P2当前项（c2i,e2i),并插入到结果多项式中。关键是要找到插入位置（要求指数递减）
初始结果多项式可由P1第一项乘P2获得（如上）

Polynomial Mult(Polynomial P1,Polynomial P2)
{
Polynomial P,Rear,t1,t2,t;
int c,e;
//P1、P2相乘， 只要有一个为空，返回null
if(!P1||!P2) return NULL;
t1=P1;
t2=P2;
//申请空结点
P=(Polynomial)malloc(sizeof(struct PolyNode));
Rear=P;
//先用P1的第一项乘以P2，得到P
while(t2){
Attach(t1->coef*t2->coef,t1->expon+t2->expon,&Rear);
}
//两重循环 t1每一项乘t2每一项
while(t1){
t2=P2;
Rear=P;	//Rear一开始指向P
while(t2){
e=t1->expon+t2->expon;	//指数相加得到当前指数
c=t1->coef*t2->coef;	//系数相乘得到当前系数
//找插入位置。比较指数，将当前结果按照指数降序插进结果多项式
else{								//系数相加后等于0，删掉
free(t);
}
}else{										//Rear的下一项的指数小于要插入的指数，可以插入
t=(Polynomial)malloc(sizeof(struct PolyNode));	//申请一个新结点
t->coef=c;t->expon=e;
}
}
}
//第一个空结点要删掉
t2=P;
free(t2);

return P;
}


### 6.多项式输出

链表遍历

void PrintPoly(Polynomial P)
{ /* 输出多项式 */
int flag = 0; /* 辅助调整输出格式用 */
if (!P) {
printf("0 0\n");
return;
}
while (P) {
if (!flag)
flag = 1;
else
printf(" ");
printf("%d %d", P->coef, P->expon);
}
printf("\n");
}


### 运行结果

展开全文
• 一元多项式A 、B 按降次排列，用带头结点的链表存储，求 C=A ×B，试编程实现。 代码实现 #include<stdio.h> #include<stdlib.h> typedef struct Lnode{ int coef; //定义系数 int exp; //定义...
• ## 问题描述

一元多项式A 、B 按降次排列，用带头结点的链表存储，求 C=A ×B，试编程实现。

• ## 代码实现

#include<stdio.h>
#include<stdlib.h>

typedef struct Lnode{
int coef;	//定义系数
int exp;	//定义指数
struct Lnode *next;	//指向下一项
}Lnode;

void Write(Lnode *node);	//输出函数
void Mul(Lnode *node_a,Lnode *node_b,Lnode *node_c);	//乘法运算

int main(void)
{
Lnode *lnode_a=(Lnode *)malloc(sizeof(Lnode));	//多项式A
Lnode *lnode_b=(Lnode *)malloc(sizeof(Lnode));	//多项式B
Lnode *lnode_c=(Lnode *)malloc(sizeof(Lnode));	//结果多项式C
lnode_c->next=NULL;
printf("请输入多项式A:\n");
printf("\n请输入多项式B:\n");
Mul(lnode_a->next,lnode_b->next,lnode_c);
printf("\n多项式A、B之积C为：\n");
Write(lnode_c->next);

return 0;
}

{
int kaiguan=1; 	char r=getchar();			//kaiguan开关，用于判断存取为系数还是指数
node->next=(Lnode *)malloc(sizeof(Lnode));	//建立头结点
node=node->next;	node->coef=0;	node->exp=0;
while(r!='\n')
{
if(r=='+')
{
node->next = ( Lnode* )malloc( sizeof( Lnode ) );
node=node->next;	node->coef=0;	node->exp=0;
kaiguan=1-kaiguan;
}
else	if(r=='x'||r=='X')	kaiguan=1-kaiguan;				//调整开关状态
else	if(kaiguan)	node->coef=10*(node->coef) + (r-48);	// ascII码存取数字
else	node->exp=10*(node->exp) + (r-48);
r=getchar();
}

node->next=NULL;
}

void Write(Lnode *node)
{
printf("%dX^%d ",node->coef,node->exp);
node=node->next;
while(node->next != NULL)
{
printf("+ %dX^%d ",node->coef,node->exp);
node=node->next;
}
if(node->exp != 0)
printf("+ %dX^%d",node->coef,node->exp);
else if(node->coef != 0)
printf("+ %d",node->coef);
}

void Mul(Lnode *node_a,Lnode *node_b,Lnode *node_c)
{
Lnode *node_d=(Lnode *)malloc(sizeof(Lnode));	//D用于存放B的每一项与A的乘积
Lnode *memmory=node_d; 							//memmory记住D的头结点
node_d->next=(Lnode *)malloc(sizeof(Lnode));
while(node_b!=NULL)
{
while(node_a!=NULL)
{
node_d=node_d->next;
node_d->exp=node_a->exp+node_b->exp;
node_d->coef=node_a->coef*node_b->coef;
node_d->next=(Lnode *)malloc(sizeof(Lnode));
node_a=node_a->next;
}
node_d->next=NULL;
node_d=(Lnode *)malloc(sizeof(Lnode));
memmory=node_d;
node_d->next=(Lnode *)malloc(sizeof(Lnode));
node_b=node_b->next;
}
}

{
Lnode *node_c=node_a,*node_d=node_b->next;	//C的地址为A的前一项，D的地址与B同时
node_a=node_a->next;						//将B的每一项加入至A中，无需新建一个单链表；
node_b=node_b->next;                        //也可新建一个单链表，同时比较A、B的第一项，依次向后延申
while(node_b!=NULL)
{
if(node_a==NULL)
{
node_a=(Lnode *)malloc(sizeof(Lnode));
node_a->exp=0;
node_a->coef=0;
node_a->next=NULL;
}
if(node_a->exp==node_b->exp)
{
node_a->coef=node_a->coef+node_b->coef;
node_a=node_a->next;
node_b=node_b->next;
node_c=node_c->next;
node_d=node_d->next;
}
else if(node_a->exp > node_b->exp)
{
node_a=node_a->next;
node_c=node_c->next;
}
else if(node_a->exp < node_b->exp)
{
node_c->next=node_b;
node_b=node_b->next;
node_d->next=node_a;
node_d=node_b;
node_c=node_c->next;
}
}
}
• ## 知识总结

1. 线性表是具有相同特性数据元素的一个有限序列，其中序列所含元素的个数叫做线性表的长度。
2. 线性表的存储结构：顺序存储结构链式存储结构。前者为顺序表，后者为链表
3. 顺序表的两个特性：随机访问特性占用连续的存储空间（存储分配只能预先进行）。
4. 链表的三个特性：不支持随机访问结点的存储空间利用率稍低于线性表支持存储空间的动态分配
6. 顺序表和链表的比较

(1)  基于空间的比较

1）存储分配：顺序表  一次性分配； 链表  多次分配

2）存储密度：顺序表  密度=1      ； 链表  密度<1

(2)  基于时间的比较

1） 存取方式：顺序表  随机存储  ；  链表  顺序存储

2）  插入/删除 移动元素个数： 顺序表  近一半元素；链表  不移动元素

展开全文
• 通过C语言实现多项式的相加，相乘等操作
• [PAT] 一元多项式乘法与加法运算 C语言实现 [PAT] 02-线性结构1 一元多项式乘法与加法运算 设计函数分别求两个一元多项式的乘积与和。 输入格式: 输入分2行，每行分别先给出多项式非零...
• 0* 完成时间: 2003年2月22日*--------------------------------------------------------------------* 改进说明: 可以实现多个多项式的加法、减法、乘法，并且比书中算法更加* 合理。例如: 连加a b c d,连减a-b-c-d...
• 设有一元多项式Am(x)和Bn(X)，编程实现多项式Am(x)和Bn(x)的加法、减法和乘法运算。其中多项 式描述为： Am(x)=A0+A1x1+A2x2+A3x3+….+Amxm； Bn(x)=B0+B1x1+B2x2+B3x3+….+Bnxn。 程序源代码： DS.h #include <...
• 一、概述通过C语言使用链式存储结构实现一元多项式加法、减法和乘法的运算。按指数降序排列。二、需求分析建立一元多项式并按照指数降序排列输出多项式，将一元多项式输入并存储在内存中，能够完成两个多项式的加减...
• 一元多项式求和实质上是合并同类项的过程，其运算规则为： （1）若两项的指数相等，则系数相加； （2）若两项的指数不等，则将两项加在结果中。
• 计算多项式乘法c语言课程设计的一类，比较简单。
• 《数据结构》一书中单元课后实验题：用c语言实现多项式乘法
• 两个一元多项式乘法的实现，采用二维数组存储变量x的系数和指数，通过对指数的排序输出
• 1.通过对本题目的设计，使学生更加系统地理解和掌握C语言的基本概念、语言语法和编程技巧。 2.通过本课程设计，重点锻炼学生在指针、结构体，链表等方面的编程能力，为将来学习数据结构课程和使用C、VC进行软件开发...
• ## 最小二乘法 多项式拟合 C语言实现

万次阅读 多人点赞 2018-01-30 09:07:20
最小二乘法 多项式拟合 C语言实现
• GF(2^8)这是啥我就不多做解释了，某度某科...因为是二进制上的转化，所以我们可以先将输入的两个十六进制串转化为二进制，转化完后对它们进行乘法运算(下面会有样例)得到多项式mx，然后找到最高幂的次数，比较一下与...
• 利用卷积求多项式乘法 对于多项式乘法f(x)=(a0+a1x+……+anxn)∗(b0+b1x+……+bmxm)f(x)=(a_0+a_1x+……+a_nx^n)*(b_0+b_1x+……+b_mx^m)f(x)=(a0​+a1​x+……+an​xn)∗(b0​+b1​x+……+bm​xm),其中 f(x)=c0+c1x...
• C语言编写的简单的多项式乘法程序，用于实现低次的多次式相乘，简便快捷。
• C++多阶拟合（附echarts画图代码）细微修改，更通用 细微修改，更通用 .../* 本实验根据数组x[], y[]列出的一组数据，用最小二乘法求它的拟合曲线。 近似解析表达式为y = a0 + a1 * x + a2 * x^2 + a3 * x^3;...
• 乘法的实现采样插入法，首先用第一个多项式的第一项乘这个多项式，然后其他项依次插入到多项式，这种做法的好处是直观，容易实现 #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; typedef ...
• 多项式相乘作为一个很好的数学问题，采用编程手段会提高解决问题的效率，因此切合实际地完成程序是有很重要的意义的。计算机最开始是为了解决数学问题的数值计算而研制的，最早的编程语言如FORTRAN也是为了解决...
• 课程设计第二组1一元多项式的加法和乘法 C语言
• 《一元稀疏多项式计算器C语言课程设计》由会员分享，可在线阅读，更多相关《一元稀疏多项式计算器C语言课程设计(26页珍藏版)》请在人人文库网上搜索。1、学号2014-2015学年 第二学期1308210115软件工程课程设计报告...
• 一、题意理解设计函数分别求两个一元多项式的乘积与和，例：[text{已知以下两个多项式：} \begin{align}& 3x^4-5x^2+6x-2 \& 5x^{20}-7x^4+3xend{align}][text{多项式和为：} \begin{align}5x^{20}-4x^4-5x^...
• 使用链表实现多项式的加法和乘法，数据结构常见问题的C语言实现
• 下面是关于这道题的图片 关于这道题的闲谈 啊 这道题确实折磨人 我还能依稀记得我就是受了上道题目的影响 导致这道题刚开始的时候是用的不创造新的节点...加法相对于乘法考虑的更少 更简单一点 首先就是L1的第一个数
• /***************************************************...目标：多项式乘法 exp: A(X)=2X^3+4 B(x)=4X^4+2X^3 C(X)=A(x)*B(x)=8X^7+4X^6+16X^4+8X^3 思路： 1.创建两个链表,用于存储两个多项式 用链式存储 系
• C语言实现一元多项式的加减法

...