c c 算法实例（example of c c algorithm）

《c c 算法实例（example of c c algorithm）》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

cc++算法实例（ExampleofCc++algorithm）CC++,algorithmexampleFirst,numbertheoreticalgorithmThegreatestcommondivisorof1.FunctionGCD(a,b:integer):integer;BeginIfb=0thengcd:=aElsegcd:=gcd(B,amodB);End;Theleastcommonmultipleofthe2.FunctionLCM(a,b:integer):integer;BeginIfa0doInc(LCM,a);End; Thesolutionof3.primenumbersA.determineifanumberisprimeinasmallrange:Functionprime(n:integer):Boolean;VarI:integer;BeginForI:=2toTRUNC(sqrt(n))doIfnmodI=0thenbeginPrime:=false;exit;End;Prime:=true;End;B.determineswhetherthenumberwithintherangeofLongintisaprimenumber(includingaprimetablelessthan50000):Proceduregetprime;VarI,j:longint; P:array[1..50000]ofboolean;BeginFillchar(P,sizeof(P),true);P[1]:=false;I:=2;Whilei<50000dobeginIfp[i]thenbeginJ:=i*2;Whilej<50000dobeginP[j]:=false;Inc(J,I);End;End;Inc(I);End;L:=0; Fori:=1to50000doIfp[i]thenbeginInc(L);pr[l]:=i;End;End;{getprime}Functionprime(x:longint):integer;Vari:integer;BeginPrime:=false;Fori:=1toldoIfpr[i]>=xthenbreakElseifxmodpr[i]=0thenexit;Prime:=true;End;{prime}Two,graphtheoryalgorithm 1.minimumspanningtreeA.Primalgorithm:Procedureprim(v0:integer);VarLowcost,closest:array[1..Maxn]ofinteger;I,J,K,min:integer;BeginFori:=1tondobeginLowcost[i]:=cost[v0,i];Closest[i]:=v0;End;Fori:=1ton-1dobegin{lookforthenearestvertexk}notspanningthespanningtreeMin:=maxlongint;Forj:=1tondoIf(lowcost[j]0)thenbegin Min:=lowcost[j];K:=j;End;Lowcost[k]:=0;{vertexKisaddedtothespanningtree}AddanewedgeKtoclosest[k]}inthe{spanningtree{modifythelowcostandclosestvaluesofeachpoint}Forj:=1tondoIfcost[k,j]0dobeginI:=find(e[q].v1);j:=find(e[q].v2);Ifi<>jthenbeginInc(TOT,e[q].len);Vset[i]:=vset[i]+vset[j];vset[j]:=[];Dec(P);End;Inc(Q);End;Writeln(TOT);End;2.shortestpathSolvingtheshortestpathofsinglesourcepointbyA.labeling method:VarA:array[1..Maxn,1..Maxn]ofinteger;B:array[1..Maxn]ofinteger;{b[i]referstotheshortestpathfromvertexitosourcepoint}Mark:array[1..Maxn]ofboolean;Procedurebhf;VarBest,best_j:integer;BeginFillchar(mark,sizeof(mark),false);Mark[1]:=true;b[1]:=0;{1assourcepoint}RepeatBest:=0;Fori:=1tondoIfmark[i]then{everypointthathascalculatedtheshortestpath} Forj:=1tondoIf(notmark[j])and(a[i,j]>0)thenIf(best=0)or(b[i]+a[i,j]0thenbeginB[best_j]:=best;mark[best_j]:=true;End;Untilbest=0;End;{bhf}B.Floyedalgorithmsolvestheshortestpathbetweenallvertexpairs:Procedurefloyed;BeginForI:=1tondoForj:=1tondo Ifa[I,j]>0thenp[I,j]:=Ielsep[I,j]:=0;{p[I,j]representstheprecursornodeofJontheshortestpathfromItoj}Fork:=1tondo{enumerationintermediatenode}Fori:=1tondoForj:=1tondoIfa[i,k]+a[j,k]0thenpre[i]:=v0elsepre[i]:=0;End;Mark[v0]:=true;Repeat{everycycleaddsanodeclosesttothe1setandadjuststheparametersofothernodes}Min:=maxint;u:=0;{urecordsthenearestnodefromthe1set}Fori:=1tondoIf(notmark[i])and(d[i]0thenbegin Mark[u]:=true;Fori:=1tondoIf(notmark[i])and(a[u,i]+d[u],thenEe[I]=Ve[j];TheneareststarttimeofD.edgeactivityisEl[I],andiftheedgeIisrepresentedby,thenEl[I]=Vl[k]-w[j,K];IfEe[j]=El[j],theactiveJisthekeyactivity,andthepathcomposedofkeyactivitiesisthecriticalpath.Solvingmethod:A.startsfromthesourcepointtopsort,determineswhetherthereisaloopandcalculatesVe;B.startsatthesink,topsort,andVl;C.calculatesEeandEl;6.topologicalsort Findthepointofpenetration0,deletealltheedgesconnectedtoit,andrepeattheprocessrepeatedly.Examplesfindasequence,wherethesumofanycontinuousPtermispositive,thesumofanyQtermisnegative,andifnot,theoutputNO.7.loopproblemEulerloop(DFS)Definition:acircuitthatpassesonlyonceoneachedgeofagraph.(sufficientandnecessaryconditions:graphswithandwithoutsingularities)hamiltoniancycleDefinition:acircuitthatpassesonlyoncepervertexofagraph.OnestrokeNecessaryandsufficientconditions:thenumberofsingularpointsandthenumberofsingularpointsare0or2.9.judgingwhetherthereisanegativeloopBellman-fordalgorithminthegraphX[I],y[I],t[I]denotethestartingpoint,endpointandweightoftheIedgerespectively.AtotalofNnodesandmedges. ProcedureBellman-FordBeginForI:=0ton-1dod[I]:=+infinitive;D[0]:=0;ForI:=1ton-1doForj:=1tomdo{enumerationeachside}Ifd[x[j]]+t[j]=bestthenexit;{s[n]istheweightand}ofthefirstnitemsIfk<=nthenbeginIfv>w[k]thensearch(k+1,v-w[k]);Search(k+1,V);End;End;LDPF[I,j]selectsseveralitemsinthefirstIitemstomakethevolumeexactlyJ,whichisBooleantype.Implementation:transformingoptimizationproblemsintodeterministicproblemsF[I,j]=f[I-1,j-w[i]](w[I]<=j<=v)boundary:f[0,0]:=true.ForI:=1tondoForj:=w[I]toVdoF[I,j]:=f[I-1,j-w[I]];Optimization:thecurrentstateisonlyrelatedtotheprevious stagestate,andcanbereducedtoonedimension.F[0]:=true;ForI:=1tondobeginF1:=f;Forj:=w[I]toVdoIff[j-w[I]]thenf1[j]:=true;F:=f1;End;B.seeksthemaximumvaluethatcanbeputin.F[I,j]forcapacityI,takethemaximumvalueobtainedbeforetheJbackpack.F[i,j]=max{f[I-w[J],j-1]+P[J],f[I,j-1]}C.asksthenumberofexactlyfilledcases.DP:Procedureupdate;VarJ,k:integer; BeginC:=a;Forj:=0tondoIfa[j]>0thenIfj+now<=nthenInc(c[j+now],a[j]);A:=c;End;TwoReusableknapsackAasksforthemostweightyoucanputin.F[I,j]selectsseveralitemsinthefirstIitemstomakethevolumeexactlyJ,whichisBooleantype.ThestatetransitionequationisF[I,j]=f[I-1,J-w[I]*k](k=1..Jdivw[I])B.seeksthemaximumvaluethatcanbeputin.USACO1.2ScoreInflation Acontest,totaltimeTfixed,thereareseveralkindsofalternativetitle,eachtitleoptionalintoanunlimitednumber,eachsubjecthasaTi(thetimerequiredtoanswerthisquestion)andaSi(answerthisquestionscore),istochooseanumberoftopics,sothatthetotaltimeofthesolutionoftheproblemsinTwithinthepremiseofthemaximumtotalscore,maximumscore.Easytothinkof:F[i,j]=max{f[i-k*w[j],j-1]+k*p[j]}(0<=k<=Idivw[j])Amongthem,f[i,j],whenthecapacityisI,themaximumofthejknapsackcanreach.*implementation:BeginFillChar(F,SizeOf(f),0);Fori:=1ToMDoForj:=1ToNDoIfi-problem[j].time>=0ThenBeginT:=problem[j].point+f[i-problem[j].time]; Ift>f[i]Thenf[i]:=t;End;Writeln(f[M]);End.C.asksthenumberofexactlyfilledcases.Ahoi2001Problem2Thenumberofexpressionsforthesumofprimenumberswithessentiallydifferentnaturalnumbersn.First,generatethepermutationofthecoefficientsofeachprimenumber,andtestthemonebyone,whichisthemethod.Proceduretry(dep:integer);VarI,j:integer;BeginCal;{thisprocesscalculatestheresultofthecurrentcoefficient,andnowistheresult}Ifnow>nthenexit;{pruning}Ifdep=l+1thenbegin{generatesallcoefficients} Cal;Ifnow=nthenInc(TOT);Exit;End;Fori:=0tondivpr[dep]dobeginXs[dep]:=i;Try(dep+1);Xs[dep]:=0;End;End;Thinkingtwo,recursivesearchefficiencyishigherProceduretry(DEP,rest:integer);VarI,J,x:integer;BeginIf(rest<=0)or(dep=l+1)thenbeginIfrest=0thenInc(TOT); Exit;End;Fori:=0torestdivpr[dep]doTry(dep+1,rest-pr[dep]*i);End;{main:try(1,n);}Ideathree:dynamicprogrammingcanbeusedtosolveUSACO1.2moneysystemVitems,BackpackCapacityofN,thetotalnumberofmethods.Transferequation:Procedureupdate;VarJ,k:integer;BeginC:=a;Forj:=0tondo Ifa[j]>0thenFork:=1tondivnowdoIfj+now*k<=nthenInc(c[j+now*k],a[j]);A:=c;End;{main}BeginRead(now);{readtheweightofthefirstobject}I:=0;{a[i]isthetotalnumberofIwhentheknapsackcapacityis}Whilei<=ndobeginA[i]:=1;Inc(I,now);end;{definingtheweightofthefirstitem,theweightoftheintegermultiplesis1,astheinitialvalue}.AFori:=2toVdoBeginRead(now); Update;{dynamicupdate}End;Writeln(a[n]);Four,sortingalgorithmA.quicksort:Procedureqsort(L,r:integer);VarI,J,mid:integer;BeginI:=l;j:=r;mid:=a[(l+r)div2];{thenumberofthecurrentsequenceinthemiddlepositionisdefinedasthemiddlenumber}RepeatWhilea[i]middoDec(J);{intherighthalfofthesearchforasmallernumberthanthemiddle}Ifi<=jthenbegin{ifyoufindasetofnumbersthatareinconsistentwiththesortingtarget,exchangethem}Swap(a[i],a[j]); Inc(I);Dec(J);{}continuetofind}End;Untili>j;Ifla[j]thenswap(a[i],a[j]);End; D.bubblesortProcedurebubble_sort;VarI,J,k:integer;BeginFori:=1ton-1doForj:=ndowntoi+1doIfa[j]r)or(a[i]<=a[j])){satisfyingtherequirementofthecurrentelementoftheleftsequenceThenbeginTmp[t]:=a[i];Inc(I); EndElsebeginTmp[t]:=a[j];Inc(J);End;Inc(t);End;Fori:=ptoRdoa[i]:=tmp[i];End;{merge}Proceduremerge_sort(VaRa:listtype;P,r:integer);{mergesorta[p..R]}Varq:integer;BeginIfp<>rthenbeginQ:=(p+r-1)div2;Merge_sort(a,P,Q);Merge_sort(a,q+1,R); Merge(a,P,Q,R);End;End;{main}BeginMerge_sort(a,1,n);End.G.radixsortIdea:sortingeachofthemfromlowtohighFive.HighprecisioncalculationDefinitionofhighprecisionnumbers:TypeHp=array[1..Maxlen]ofinteger;1.highprecisionadditionProcedureplus(a,b:hp;VARc:hp);VarI,len:integer; BeginFillchar(C,sizeof(c),0);Ifa[0]>b[0]thenlen:=a[0]elselen:=b[0];Fori:=1tolendobeginInc(c[i],a[i]+b[i]);Ifc[i]>10thenbeginDec(c[i],10);Inc(c[i+1]);end;{carry}End;Ifc[len+1]>0thenInc(len);C[0]:=len;End;{plus}2.highprecisionsubtractionProceduresubstract(a,b:hp;VARc:hp);var，i，整数；开始fillchar（C，sizeof（C），0）； 如果A[0]>0]则为：另一个[0]，即：[b]0]；对于i==1到莱恩开始股份有限公司（c，I，]；如果cii<0然后开始（c，i，10）；DEC（c[i+1]）；结束；当（莱恩1）和（C=0）做DEC（镜头）；c[0]==莱恩；结束；3。高精度乘以低精度程序多（一：惠普；B：LongInt；VaRC：HP）；var，i，整数；开始fillchar（C，sizeof（C），0）；=a[0]；对于i==1到莱恩开始公司（C，I，]；公司（C+1），（A（*）B）div10）； C=i：=C[i]mod10；结束；公司（莱恩）；而（C[镜头]>=10）开始处理最高位的进位}{c[镜头+1]：=C[莱恩]div10；c=10；公司（莱恩）；结束；而（Len>1）和（C[镜头]=0）做DEC（LEN）；{}若不需进位则调整Lenc[0]==莱恩；结束；{乘}4。高精度乘以高精度程序high_multiply（A，B：惠普；varC：惠普}var，i，j，莱恩：整数；开始 fillchar（C，sizeof（C），0）；对于i：=1到a[0]对于j==1到B[0]开始公司（C[我+J-1]，一个[我]*B[J]）；公司（C[我]，[我]C+J-1DIV10）；C[我]：=C+J-1签证J-1][我+模10；结束；1=0[0]+；当（莱恩1）和（C=0）做DEC（镜头）；c[0]==莱恩；结束；5。高精度除以低精度程序将（一：惠普；B：LongInt；HP；var变量D：LongInt）；{var，i，整数； 开始fillchar（C，sizeof（C），0）；=：[0]；d＝0；我：=Len到1开始d=d*10+A[i]；c；D:；结束；当（透镜1）和（c＝0）时，DEC（透镜）；c[0]==莱恩；结束；6。高精度除以高精度程序high_devide（A，B：惠普；varC，D：HP）；VaRI，莱恩：整数；开始 fillchar（C，sizeof（C），0）；fillchar（D，sizeof（D），0）；=：[0]；d[0]＝1；我：=Len到1开始乘法（d，10，d）；D[1]：=[i]；而（比较（d，b）>=0）做{即D>=b}开始减法（D，B，D）；股份有限公司（丙）；结束；结束；而（Len>1）和（参数[Len]=0）做DEC（LEN）；c.len：=Len；结束； 六、树的遍历1。已知前序中序求后序过程解决（前置，中间：字符串）；varI：整数；开始如果（预=“”或（“=”）退出；I：=POS（预[1]，中）；解决（复印件（预，2，我），复制（中，1，：））；解决（复制（预，i+1，长度（预）I），复制（中间，我+1，长度（中）I））；职位：=岗位+预[1]；{加上根，递归结束后后即为后序遍历}结束；2。已知中序后序求前序过程解决（中间，邮政：字符串）；varI：整数；开始 如果（中=“”或（POST=“”）然后退出；i：=（POST（长度（POST）]，中间）；预：=预+岗位（岗位）[长度]；{加上根，递归结束后预即为前序遍历}解决（复印件（中、1、I-1），复制（后，1，：））；解决（复制（中，我+1，长度（中）I），复制（POST，i，长度（POST）I））；结束；3。已知前序后序求中序的一种函数ok（S1），s2:string):boolean;wasi,l:integer;p:boolean;beginok:=true;l:=length(s1).fori:=1toldobeginp:=false; j:=1twoldoifs1[i]=s2[j]thenp:=true;ifnotp,thenbeginok:=false;exit;than;than;than;theproceduresolve(pre,post:string);wasi:integer;beginif(pre='''')or(post='''')thenexit;in:=0;repeatinc();untilok(copy(pre),2(i),copy(item1));solve(copy(pre),2(i),copy(item1));midstr:=midstr+pre[1]; solve(copy(pre,in+2,length(pre)-in-1),copy(mail,i+1,length(post)-in-1));than;七进制转换1.任意正整数进制间的互化除n取余2.实数任意正整数进制间的互化乘n取整3.负数进制:设计一个程序,读入一个十进制数的基数和一个负进制数的基数,并将此十进制数转换为此负进制下的数:-r∈{-2,-3,-4,-20}八全排列与组合的生成1.排列的生成:(1..n)thesolveprocedure(dep:integer);wasi:integer;begin ifdep=n+1thenbeginwriteln(s);exit;than;fori:=1tondoifnotused[in]thenbegins:=s+chr(in+word(''0''));used[i]:=true;solve(dep+1);s:=copy(s,1,length(s)-1);used[i]:=false;than;than;2.组合的生成(1..n中选取k个数的所有方案)thesolveprocedure(deppre:integer);wasi:integer;beginifdep=k+1thenbeginwriteln(s);exit;than;fori:=1tondo if(notused[in])and(>pre)thenbegins:=s+chr(in+word(''0''));used[i]:=true;solve(dep+1,i);s:=copy(s,1,length(s)-1);used[i]:=false;than;than;九.查找算法1.折半查找functionbinsearch(k:keytype):integer;waslow,gu,mid:integer;beginlow:=1;hig:=n;mid:=(low+hig)div2;while(a[mid].key<>k)and(low<=hig)dobeginifa[mid].key>kthenhig:=mid-1conclusionlow:=mid+1; mid:=(low+hig)div2;than;iflow>guthenmid:=0;binsearch:=mid;than;2.树形查找二叉排序树:每个结点的值都大于其左子树任一结点的值而小于其右子树任一结点的值.查找functiontreesrh(k:keytype):pointer;wasq:pointer;beginq:=root;while(q<>nile)and(q^.key<>c)doifk目标然后开始若未移到目标}{移动（k-1,6-now-goal）剩下的先移到没用的柱上；{} 方法（K从现在到目标）；H[目标[目标]，h，0+1=h]：[现在，nowp]；H[现在]：nowp=0；公司（h，目标，0）；DEC（h，现在，0）]；移动（k-1，目标剩下的移到目标上）；{}结束；十二、DFS框架noip2001数的划分程序工作（DEP、预、S：LongInt）；{入口为工作（1,1，n）}{DEP为当前试放的第DEP个数，预为前一次试放的数，S为当前剩余可分的总数}varj：LongInt；开始如果开始的话如果s=前，那么公司（R）；退出；结束；J：=前期的DIV2做工作（DEP+1，J，S-J）； 结束；类似：过程尝试（DEP：整数）；varI：整数；开始如果开始如果TOT>=一个[dep-1]然后公司（和）；出口；结束；我：=一个[dep-1]TOTDIV2开始a=；尝试（DEP+1）；股份有限公司（TOT，I）；结束；结束；{}十三、BFS框架 ioi94房间问题头：=1；尾：＝0；当尾<头】开始公司（尾）；对于k=1到n做如果K方向可扩展然后开始公司（头）；目录[头]。X：=列表[尾巴]。xdx[K]；{扩展出新结点列表[头]}列表[头]；处理新结点列表[头]；结束；结束；十五、数据结构相关算法1。链表的定位函数LOC（我：整数）：我个结点的指针}{寻找链表中的第指针；程序LOC（L：链表；我：整数）：指针； 变量指针；j：整数；开始P：=l.head；J=0；如果（我>=1）和（我<=l.len）然后而Ji开始p＝p；下一个；j（j）；结束；=p；结束；2。单链表的插入操作程序插入（L：链表；我：整数；X：数据类型）；var，q：指针；开始p：=LOC（l，i）；新（q）；q=数据； 下一步：下一步；下：=q；公司（l.len）；结束；3。单链表的删除操作程序删除（L：链表；我：整数）；var，q：指针；开始P：=LOC（L，I-1）；q=p=。next;p^.next:=q^.next;with(q).dec(l.len);end;4.双链表的插入操作(插入新结点q) p:=loc(l,i);new(q).q^.data:=x;q^.pre:=p;q^.next:=p^.next;p^.next:=q;q^.next^.pre:=q;5.双链表的删除操作p:=loc(l,i);(p为要删除的结点}p^.pre^.next:=p^.next;p^.next^.pre:=p^.pre;with(p);