基于分治策略求解方程根的个数

:2006-01-06:(2004kj265):(1963-),,,,,,,,,,(,246011):n,n:;;;:TP301.6:A:1673-629X(2006)09-0041-03SeekingforRootsofEquationBasedonStrategyofDivideandConquerQIANMeng,CHENGYu2sheng,CHENGShu2lin,YEMin,WANGZhi2hua,QILe(SchoolofComputer&Information,AnqingTeachersCollege,Anqing246011,China)Abstract:Theseekingforrootsofn-membershyper-polynomialequationhaslargetimecomplexityduetothesizeofn.Inthispaper,theefficiencyofalgorithmisimprovedbyoperatingofbinarybasedonthestrategyofdivideandconqueraswellasusingtheHashtableandthelinearmethodtoresolvetheconflicts.Keywords:strategyofdivideandconquer;Hashfunction;binaryoperation;searchNK,,Strassen[1],,n1n[2,3]:k1xp11+k2xp22++knxpnn=0,x1,x2,,xn,k1,k2,,kn,p1,p2,,pn,;;1xiM(i=1,2,,n),(231)1n6;1M150;|k1Mp1|+|k2Mp2|++|knMpn|2312,6,,xiM,O(M6),M,:A,B,A+B=0A,B;A,B,A,S-data,BA+B=0,n6,6A,B5,AO(M),BO(M5),O(M5),:,?,A,B3,A,BO(M3),O(M3),n,M,F(n)16920069COMPUTERTECHNOLOGYANDDEVELOPMENTVol.16No.9Sep.2006©1994-2007ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.(n),O(MF(n)),O(MF(n))T(n)O(MF(n))+O(MF(n))=2O(MF(n)),n,:F(n)=n/2T(n):2O(Mn/2),[4],[1,5][6]3n,t,t=nDIV2(DIV);At,BA,Bn/2n=6,,A:k1xp11+k2xp22++knxpttAss1503=3375000,3375000,3375000s,:s,:TypeSqlistS-dataAsDoublexS-dataCountAsDoubleEndType3.111(1)(form-load):(2)(cmdComputer-Click):Clickcmd2Computer-Click(3)(check):(4)(searchHash):B,A,Count,0,,Count0S-data,,,(h(k)+i)modp,Count0,(5)(insertHash):,Count0,0,S-dataCount1,0,Count1(6)(left-computer):n,A,AsinsertHash,(7)(right-computer):n,B,B,searchHashA,A+B=0resultCount,(8)(Output-answer):231,3.23.2.1:p,3375000,p=3375000,h(k)=kmodp3.2.2S-dataCount0,Count,0S-data3.2.3s,,p,h(k),(h(k)+i)modp,i=1,2,3,(h(k),,)3.3,form-load,,,cmdComputer-Click,check2416©1994-2007ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.(S),in2sertHash(S)searchHash(S)s,,left-computer,cmdComputer-Clickright-computer,B,searchHash(S)A+B=0,right-computer,cmdComputer-Clickoutput-answerOutput-answer,,,,41n=4,M=150,k1=k3=1,k2=k4=-1,pi=2(i=1,2,3),p4=3,n,5167,222n=6,M=150,k1=k2=k3=1,k4=k5=k6=-1,pi=1,(231),3311NMk1,p1k2,p2k3,p3k4,p4k5,p5k6,p6131501,2-1,21,2178241501,2-1,21,2-1,35167361501,11,11,1-1,1-1,1-1,1431501,61,11,1521501,3-1,11,1N631511,6-1,11,1M72.11501,31,2N828.51,21,2M931502.5,21,21,21031501,21,2.51,25,A,B,A,,B,AA+B=0,;,,VB,:[1].[M].:,2001.[2].[EB/OL].=261-NOI2001-2001-10-27.[3].[EB/OL].[4].[J].,1996,6(6):28-30.[5],.[J].,1994,4(3):21-24.[6].[M].:,2001.(3):[1]BierEA,SloanKR.Two-parttexturemappings[J].IEEEComputerGraphicsandApplication,1986,6(9):40-53.[2],.[J].,1999,36(4):446-450.[3],.[J].,1998,3(7):578-582.[4],.[J]1,2004,16(9):1982-1984.[5]RogersDF.ProceduralElementsforComputerGraphics[M].Beijing:ChinaMachinePress,20021531-534.349:©1994-2007ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.