多项式乘积算法设计与分析.docVIP

PAGE  PAGE 9 算法设计与分析课程设计论文 课题名称：多项式乘积的分治算法设计与实现 院系：计算机科学与信息工程学院 专业：计算机科学与技术（信息方向）11-1 姓名学号：潘强 201103020005 指导教师：冯慧玲 2013年12月 目录  TOC \o 1-2 \h \z \u  HYPERLINK \l _Toc375644827 一、算法介绍  PAGEREF _Toc375644827 \h 3  HYPERLINK \l _Toc375644828 二、问题描述 3  HYPERLINK \l _Toc375644829 三、相关概念和数据结构介绍  PAGEREF _Toc375644829 \h 4  HYPERLINK \l _Toc375644830 四、算法设计与流程图  PAGEREF _Toc375644830 \h 4  HYPERLINK \l _Toc375644831 1.算法设计  PAGEREF _Toc375644831 \h 4  HYPERLINK \l _Toc375644832 2.流程控制图  PAGEREF _Toc375644832 \h 5  HYPERLINK \l _Toc375644833 五、算法分析  PAGEREF _Toc375644833 \h 7  HYPERLINK \l _Toc375644834 六、应用举例与程序代码  PAGEREF _Toc375644834 \h 7  HYPERLINK \l _Toc375644835 1.应用举例  PAGEREF _Toc375644835 \h 7  HYPERLINK \l _Toc375644836 2.核心代码  PAGEREF _Toc375644836 \h 7  HYPERLINK \l _Toc375644837 七、运行截图  PAGEREF _Toc375644837 \h 10  HYPERLINK \l _Toc375644838 八、总结  PAGEREF _Toc375644838 \h 11  多项式乘积算法设计与分析 一、算法介绍 在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如 HYPERLINK /view/297739.htm \t _blank 排序算法( HYPERLINK /view/115472.htm \t _blank 快速排序， HYPERLINK /view/90797.htm \t _blank 归并排序)，傅立叶变换( HYPERLINK /view/1006229.htm \t _blank 快速傅立叶变换)等。 分治法在每一层递归上都有三个步骤： 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题； 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题； 合并：将各个子问题的解合并为原问题的解。 它的一般的算法设计模式如下： Divide-and-Conquer(P) 1. if |P|≤n0 2. then return(ADHOC(P)) 3. 将P分解为较小的子问题 P1 ,P2 ,...,Pk 4. for i←1 to k 5. do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi 6. T ← MERGE(y1,y2,...,yk) △ 合并子问题 7. return(T) 其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。ADHOC(P)是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时直接用算法ADHOC(P)求解。算法MERGE(y1,y2,...,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,...,Pk的相应的解y1,y2,...,yk合并为P的解。 二、问题描述 用分治算法解决多项式乘积问题 由于任意大整数都可以看作是一多项式，所以大整数相乘是多项式乘积的一个特例，通过解决大整数乘积，即是解决了多项式的乘积问题。 三、相关概念和数据结构介绍 1.因为两个数可以任意大，所以通过数组实现，这个大整数乘积的实现运用整型数组来实现，这样就把两个数