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

落日映苍穹つ 2022-12-24 04:52 80阅读 0赞

### 多项式A除以B ###

![t1][]  
![t2][]

--------------------

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

(x3\-1) / (x-1) = x2\+x+1  
多项式除法的演示图![多项式除法][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]

--------------------

#### 解题思路：模拟 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;
    }

![运行结果][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center 1]  
递归会出现超时，效率没能达到题目要求。

##### 方案二：循环 #####

#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;
    }

![运行结果][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center 2]  
循环能通过全部样例。

--------------------

#### 总结 ####

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

[t1]: /images/20221120/e4ca9438ff4e4516b55445d3b4185fab.png
[t2]: /images/20221120/4c7600d153c54eae85722ab1fa320e16.png
[Link 1]: https://baike.baidu.com/item/%E5%A4%9A%E9%A1%B9%E5%BC%8F%E9%99%A4%E6%B3%95/2703247?fr=aladdin
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20201126193500915.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201126194456236.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20201126194700349.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4=,size_16,color_FFFFFF,t_70#pic_center