首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 网络技术 > 网络基础 >

(多项式演算4.7.6)POJ 2527 Polynomial Remains(多项式除法)

2013-10-27 
(多项式运算4.7.6)POJ 2527 Polynomial Remains(多项式除法)例把被除式、除式按某个字母作降幂排列,并把所

(多项式运算4.7.6)POJ 2527 Polynomial Remains(多项式除法)

把被除式、除式按某个字母作降幂排列,并把所缺的项用零补齐,写成以下这种形式:

(多项式演算4.7.6)POJ 2527 Polynomial Remains(多项式除法)

然后商和余数可以这样计算:

  1. 将分子的第一项除以分母的最高次项(即次数最高的项,此处为x)。结果写在横线之上(x3 ÷ x = x2).
    (多项式演算4.7.6)POJ 2527 Polynomial Remains(多项式除法)
  2. 将分母乘以刚得到结果(最终商的第一项),乘积写在分子前两项之下(同类项对齐) (x2 · (x ? 3) = x3 ? 3x2).
    (多项式演算4.7.6)POJ 2527 Polynomial Remains(多项式除法)
  3. 从分子的相应项中减去刚得到的乘积(消去相等项,把不相等的项结合起来),结果写在下面。((x3 ? 12x2) ? (x3 ? 3x2) = ?12x2 + 3x2 = ?9x2)然后,将分子的下一项“拿下来”。
    (多项式演算4.7.6)POJ 2527 Polynomial Remains(多项式除法)
  4. 把减得的差当作新的被除式,重复前三步(直到余式为零或余式的次数低于除式的次数时为止.被除式=除式×商式+余式 )
    (多项式演算4.7.6)POJ 2527 Polynomial Remains(多项式除法)
  5. 重复第四步。这次没什么可以“拿下来”了。
    (多项式演算4.7.6)POJ 2527 Polynomial Remains(多项式除法)

横线之上的多项式即为商,而剩下的 (?123) 就是余数。

(多项式演算4.7.6)POJ 2527 Polynomial Remains(多项式除法)

算数的长除法可以看做以上算法的一个特殊情形,即所有 x 被替换为10的情形。



/* * POJ_2527.cpp * *  Created on: 2013年10月26日 *      Author: Administrator */#include <iostream>#include <cstdio>using namespace std;const int maxn = 10010;int main(){int n,k;int val[maxn];while(scanf("%d%d",&n,&k)!=EOF,n!=-1 || k !=-1){int i;for(i = 0 ; i <= n ; ++i){scanf("%d",&val[i]);}//进行除法运算for(i = n ; i >= k ; --i){if(val[i] == 0){continue;}val[i-k] = val[i-k] - val[i];val[i] = 0;}//调整数组长度,即高位的0不用输出int t = n;while(val[t] == 0 && t > 0){--t;}for(i = 0 ; i < t ; ++i){printf("%d ",val[i]);}printf("%d\n",val[t]);}return 0;}


热点排行