《高位水仙花数快速求解算法》.pdf

《《高位水仙花数快速求解算法》.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算机与现代化2015年第6期JISUANJIYUXIANDAIHUA总第238期文章编号：1006-2475(2015)06-0078-04高位水仙花数快速求解算法卫洪春(四川文理学院计算机学院，四川达州635000)摘要：为了处理超出计算机字长范围的整数，需要构造合适的数据结构，用以存储超大数据。本文研究水仙花数的特征，结合排列组合和函数单调性等相关理论，借助“栈”后进先出的特点，利用动态数组存储超大整数。这种方法突破了传统设计思路仅考虑有限长度范围内的整型数据处理的约束，使得寻找正整数范围内的水仙花数的计算工作量呈几何级减少，达到

2、了在较短时间内快速寻找正整数集合内所有水仙花数的目的，对超大整数的处理具有较好的参考作用。关键词：水仙花数；栈；存储；动态数组；字长中图分类号：TP39l文献标识码：Adoi：10．3969／j．issn．1006-2475．2015．06．017FastAlgorithmofLargeNarcissusNumberWEIHong—chun(ComputerScienceDepartmentofSichuanUniversityofArtsandScience，Dazhou635000，China)Abstract：InordertOp

3、rocessthoseintegersbeyondthescopeofcomputerword-length，weneedtoconstructsuitabledatastruc-turesforstoringbigdata．ThispaperstudiesthecharacteristicsofNarcissusnumbers；combinesthetheoryofpermutationandcombinationwithfunctionalmonotonicity；usesstackwhichhasLIFOcharacter；sto

4、reslargeintegerbydynamicarray．Thismeth-odbreaksthroughthetraditionaldesignwhichonlyconsidersprocessingfinitelengthintegers，makesthecalculationworkoffind-ingNarcissusnumbersreduceexponentiallyintherangeofpositiveintegers，achievesthepurposeoffindingallNarcissussum—bersquic

5、klyinashortperiodoftimewithinthesetofpositiveintegers．Thismethodisagoodreferencefortheprocessingoflargeinteger．Keywords：Narcissusnumber；stack；memo~；dynamicarray；word—length范围，例如，在32位系统VC6．0环境下，正整数的最0引言大值(2147483647)是有限的，超过最大值时，数据会水仙花数-1刮是指一个n位正整数(n≥3)，构成溢出；2)求解速度特别慢(每增加一

6、位数，循环次数该数的每个数字的1,1次幂之和等于它本身(例如：1’是原来的10倍)。因此需要寻找一种快速、准确的方+5+3=153)。一般的求解方法是对于一个n位法，设计合理的数据结构完成计算。正整数(a一a一：⋯aao)，先判断该数是否是自幂数；1问题分析若成立，则输出水仙花数；然后将该数加1，继续判断，直到构成这个n位数的所有数字均等于9为止。1．1高位整数的表示随后判断所有的n+1位数，依此类推。n位正整数计算机中，为了正确表示和处理超过整数范围的的水仙花数常规求解算法如图1所示。高位整数，可使用字符串方式或文件方式。但字符串当正

7、整数的位数n较小时(例如n≤8)，寻找水中的字符与数字的转换需要时间开销，文件的读写也仙花数的速度相当快。当整数位数n较大时，将存在需要时间，这将必然影响计算速度。理想的办法是尽2方面的问题：1)数据可能超过有符号正整数的表示收稿日期：2015-02-04基金项目：国家自然科学基金资助项目(61152003)；四川省教育厅项目(152／t0326)；四川文理学院智能物流创新团队资助项目作者简介：卫洪春(1972-)，男，四川达县人，四川文理学院计算机学院讲师，硕士，研究方向：软件工程，数字媒体技术。20l5年第6期生洪春：高算法79可能

8、利用整数本身来解决问题。动态数组。可以若这n个数字的某个排列所构成的n位正整数a是达到这个目的。水仙花数，则其它排列中，数字的排列顺序必然与a不同。例如1、5、3这3个数字构成的3位数的全排列有6种，其中只