天梯题集——多项式A除以B（多项式除法，递归与循环的效率比较）

多项式A除以B

多项式除法
这里就不展开介绍多项式除法，只需将多项式看成一个整体就类似于整数除法。

(x³-1) / (x-1) = x²+x+1
多项式除法的演示图

解题思路：模拟 A / B 多项式除法

方案一：递归

#include<bits/stdc++.h>
using namespace std;
double Q[1000010], R[1000010];
double a[1000010], b[1000010];
int q[1000010], index_b=0;

void f(int max_a, int max_b){
	double d = a[max_a]/b[max_b];
	
	for(int i=0; i<index_b; i++)
		a[q[i]+max_a-max_b] -= b[q[i]]*d;
	
	Q[max_a-max_b]=d;
	if(max_a==max_b){
		memcpy(R, a, sizeof(a));
		return;
	}
	max_a--;
	while(max_a>max_b&&fabs(a[max_a])<1e-8) max_a--;
	f(max_a, max_b);
	return;
}

int main(){
	int max_a=0, max_b=0;
	int index;
	cin>>index;
	for(int i=0; i<index; i++){
		int x, y;
		cin>>x>>y;
		a[x] = y;
		max_a = max(x, max_a);
	}
	cin>>index_b;	//主要是想剪枝
	for(int i=0; i<index_b; i++){
		int x, y;
		cin>>x>>y;
		q[i] = x;	//主要是想剪枝
		b[x] = y;
		max_b = max(x, max_b);
	}
	f(max_a, max_b);
	
	//统计个数 
	int cnt_q=0, cnt_r=0;
	for(int i=max_a; i>=0; i--){
		if(abs(Q[i])>0.0445) cnt_q++;
		if(abs(R[i])>0.0445) cnt_r++;
	}
	
	//输出 
	if(cnt_q!=0){
		cout<<cnt_q;
		for(int i=max_a-max_b; i>=0; i--)
			if(abs(Q[i])>0.0445)
				printf(" %d %.1lf", i, Q[i]);
	}
	else
		cout<<"0 0 0.0";
	cout<<endl;
	
	if(cnt_r!=0){
		cout<<cnt_r;
		for(int i=max_b-1; i>=0; i--)
			if(abs(R[i])>0.0445)
				printf(" %d %.1lf", i, R[i]);
	}
	else
		cout<<"0 0 0.0";
	
	return 0;
} 

递归会出现超时，效率没能达到题目要求。

方案二：循环

#include<bits/stdc++.h>
using namespace std;
double Q[1000010], R[1000010];
double a[1000010], b[1000010];
const double eps = 1e-8;

void slove(int max_a, int max_b){
	for(int i=max_a; i>=max_b; i--){
		if(fabs(a[i]) > eps){
			double c = a[i]/b[max_b];   
			Q[i-max_b] = c;
			
			for(int j=max_b; j>=0; j--){
				if(fabs(b[j])>eps)
					a[i-max_b+j] -= c * b[j];
			}
		}
	}
	memcpy(R, a, sizeof(a));
	return;
}

int main(){
	int max_a=0, max_b=0, x, y;
	int index;
	cin>>index;
	for(int i=0; i<index; i++){
		cin>>x>>y;
		a[x] = y;
		max_a = max(x, max_a);
	}
	cin>>index;
	for(int i=0; i<index; i++){
		cin>>x>>y;
		b[x] = y;
		max_b = max(x, max_b);
	}
	slove(max_a, max_b);
	
	//统计个数 
	int cnt_q=0, cnt_r=0;
	for(int i=max_a; i>=0; i--){
		if(abs(Q[i])>0.0445) cnt_q++;
		if(abs(R[i])>0.0445) cnt_r++;
	}
	
	//输出 
	if(cnt_q!=0){
		cout<<cnt_q;
		for(int i=max_a-max_b; i>=0; i--)
			if(abs(Q[i])>0.0445)
				printf(" %d %.1lf", i, Q[i]);
	}
	else
		cout<<"0 0 0.0";
	cout<<endl;
	
	if(cnt_r!=0){
		cout<<cnt_r;
		for(int i=max_b-1; i>=0; i--)
			if(abs(R[i])>0.0445)
				printf(" %d %.1lf", i, R[i]);
	}
	else
		cout<<"0 0 0.0";
	
	return 0;
} 

循环能通过全部样例。

总结

在循环和递归的比较中，循环效率更高，但我依稀记得有人曾说过递归都能用循环实现，只是会更加复杂、繁琐。
循环和递归各有所长，好好把握吧…