经典数据结构与算法

《经典数据结构与算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、经典数据结构与算法线性表队列堆栈排序查找二叉树线性表案例1Recaman问题Recaman'sSequenceTimeLimit:1000ms,SpecialTimeLimit:2500ms,MemoryLimit:65536KBProblem10010:NospecialjudgementProblemdescriptionTheRecaman'ssequenceisdefinedbya0=0;form>0,am=am−1−mifthersultingamispositiveandnotalreadyinthesequence,other

2、wiseam=am−1+m.ThefirstfewnumbersintheRecaman'sSequenceis0,1,3,6,2,7,13,20,12,21,11,22,10,23,9...Givenk,yourtaskistocalculateak.InputTheinputconsistsofseveraltestcases.Eachlineoftheinputcontainsanintegerkwhere0<=k<=500000.Thelastlinecontainsaninteger−1,whichshouldnotbepro

3、cessed.OutputForeachkgivenintheinput,printonelinecontainingaktotheoutput.SampleInput710000-1SampleOutput2018658解题思路定义两个线性表：一个记录ai的值,一个记录某个值是否已经被占用。核心代码及解释inta[500001],b[3020000];//a数组如题目描述，b数组是Bool数组，只有0/1值，0表示没占//用，1表示已经被占用intmain(){a[0]=0;b[]=0；for(i=1;i<500001;i++){a[i]

4、=a[i-1]-i;if(a[i]<=0

5、

6、b[a[i]]==1)a[i]=a[i-1]+i;b[a[i]]=1; }//标记是否使用while(scanf("%d",&n),n+1)printf("%d",a[n]);return 0;}队列案例1约瑟夫问题案列2选助手ProblemdescriptionPersons,whosenumberorderisfrom1toN,holdapassword(thestraightintegerlessthan10000)eachpersonandsitaroundclockwise.Atf

7、irstwechooseapositiveintegerfactorasthecountoffnumberMandstarttonumberclockwisefromnumberone.AswenumbertoMthepersonwhonumbersMleavestherankandwhosepasswordwillbethenewnumberM.Andthenstarttonumberagainfromthepersonwhoissitclockwisenexttothepersonwhohasbeenoutofftherankjustb

8、eforethen.Continuelikethis,untilallpeopleareoutofftherankcompletely.Pleasedesignaprogramofleavingorder.InputTherehavesomegroupsdata.FirstlineofeachgroupdataistwointegersN,M(0

9、0,0,whichmeanstheendofinputdata.OutputToeachgroupofdata,accordingtotheorderwhichleavesoutputstheirserialnumber.Betweenthenumeralseparateswithablankspace.Eachgroupofdatamonopolizelineofoutputs.SampleInput720317248443123400SampleOutput61472353214解题思路数据结构的循环队列定义队列为Structqueue

10、{Datapassword;*queuenext;}化简一下Queue[0]=1;queue[I]=I+1;queue[n]=0;核心代码及解释joseph(intm,intn,