组合算法的研究与实现

《组合算法的研究与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、天津工业大学硕士学位论文组合算法的研究与实现姓名：郭燕莎申请学位级别：硕士专业：计算机应用技术指导教师：张大坤20080101摘要伴随着2l世纪信息社会的到来，计算机的应用已渗透NT社会生活的各个领域，其基本实现从根本上说是通过软件来完成的，而软件开发与设计的核心则是算法的设计与实现，最终，组合算法又构成了计算机算法的中心内容。纵观全世界的经济与软件产业的发展情况，美国均处于霸主地位。从中，我们可以间接地看到组合算法的重要性，不仅在当今，将来更是如此，实践已经证明了这一点。本文对组合算法进行了初步

2、的研究，首先分析了该课题的历史背景及研究意义；其次提出了棋盘多项式的非递归算法，并与其它算法进行了比较，在速度上提高了3"--5倍；再次是对组合数学中的常用算法：错位排列、正整数的分拆、排列组合三个算法进行了研究，并做了相应的改进和比较；随后对上述所研究的算法加以实现，同时进行了集成，使之成为一个小型的组合算法软件；最后对所研究的算法进行了总结，并针对难点提出了今后的努力方向。综上所述，对组合算法的研究具有理论意义和实用价值，尤其是本文提出的棋盘多项式的非递归算法，较之递归算法不仅在速度上有了明显

3、的提高，而且在给出总方案数的同时，也给出了具体的排列方案，操作方便、快捷。关键词容斥原理棋盘多项式错排正整数的分拆Abstract、矾ththetwenty-firstcentury’Scomingoftheinformationsociety,thecomputershavealreadyapplytomanykindsofareasinthesociety，onthewhole,whichisbasicallycompletedbytheset,rare,atthesametime，theco

4、reofthesoftwaredevelopmentanddesignmentisthedesignmentandrealizationofthearithmetics，finally,combinationarithmeticsconstitutethecoreofthecomputerarithmetics．Fromthedevelopmentstateoftheeconomyandthesoftware，Americaisonthehegemonystate．Byit．wecanindire

5、ctlys∞theimportanceofthecombinationarithmetics，notonlythenowadays，butalsothefuture,whichhavetestifiedbythepractice．Thethesisresearchsseveralbasicarithmeticsofthecombinationarithmetics．Firstly,itanalyzesthehistoricalbackgroundandthemeaningofresearch；Se

6、condly,itputsforwardthenon-recursivealgorithmonthechessBoardpolynomial，andcompareswiththeotherarithmetics，asaresult,thenoll-recursivealgorithmimprovesthreetojfivetimesOilthespeed；Thirdly,itresearchsthreeotherbasicarithmeticsofthecombinatorics：derangem

7、ent,partitionofthepositiveinteger,arrangementandcombination，makessomebettermentsandcomparesimultaneously；Then,itrealizesandintegratestheabovearithmetics。whichareformedasoftwareofthecombinationarithmetics；Finally,itsummarizesalltheresearchs，andprovides

8、thenextgoalsaimingatthecurrentproblems．Tosumup，theresearchonthecombinationarithmeticshastheacademicsignificanceandtheapplicability,especiallytothenon-recursivealgorithmonthechessBoardpolynomial，whichnotonlyhasaobviousimprovementonthespeed．buta