java编程-第6课算法和实现经典题

经典算法的Java实河内塔问题河内之塔(TowersofHanoi)是法国人M.Claus(Lucas)于1883年从带至法ardLucas曾提及这个故事，据说创世纪时Benares有一座教塔，是由三支钻石棒（Pag）所支撑，开始时神在第一根棒上放置64个由上至下依由小至大排数搬运完毕之时，此塔将毁损，而也就是世界来临之时。如果柱子标为ABC，要由A搬至C，在只有一个盘子时，就将它直接搬至C，当有两个盘子，就将Bn2^n-1，时，则所需次数为：264-1 15为50005850//Java的实importpublicclassHanoi publicstaticvoidmain(Stringargs[])throwsIOException int BufferedReader buf=newBufferedReader(newInputStreamReader(System.in n= Hanoihanoi=new hanoi.move(n,'A','B',}}publicpublicvoidmove(intn,chara,charb,charc) ifn1System.out.printlnna else move(n-1,a,c, System.out.println(na move(n-1,b,a, }费式数 Fibonacci1、12、3、5、8、13、21、34、55、89......fn=fn-1+fn- ifn>fn= ifn=0,//Java的实现publicclassFibonacci publicstaticvoidmain(String[]args) int[]fib=new fib[0]= fib[1]= for(inti=2;i<fib.length;i++)fib[i]=fib[i-1]+fib[i- for(inti=0;i<fib.length;i++)System.out.print(fib[i]+" }巴斯卡（Pascal）三角巴斯卡（Pascal）三角形基本上就是在解nCrnCr，其中n为row，而r为column，如下：1C02C02C13C03C13C24C04C14C24C3巴斯卡三角形中的nCr可以使用以下这个来计算，以避免阶乘运算时的nCr=[(n-r+1)*nCr-1]/rnC0=1//java实importimportpublicclassPascalextendsJFrame publicPascal() setSize(520, setSize(700, privatelongcombi(intn,intr) int longp= for(i=1;i<=r;i++)p=p*(n-i+1)/ return publicvoidpaint(Graphicsg) g.clearRect(0,0,getSize().width, finalintN= intn,r, for(n=0;n<=N;n++) for(r=0;r<=n;r++)g.drawString(""+combi(n,r),(N-*20+r*40,n*20+ publicstaticvoidmain(Stringargs[]) Pascalfrm=new }蒙地卡罗法求卡罗的基本原理为以乱数配合面 来进行解题这种以机率来解题的方式PIPI1，PI，1，如下图所示：之一圆内，假设所投射的飞标（点）有n点，在圆内的飞标（点）有c点，则依比例来算，就会得到上图中最后的。X^2+Y^21//java实publicclassPI publicstaticvoidmain(String[]args) finalintN= intsum= for(inti=1;i<N;i++) doublex= doubley= if((x*x+y*y)<1) System.out.println("PI="+(double)4*sum/ }最大公因数、最小公倍最大公因数使用辗转相除法来求，最小公倍数则由这个来求*LCM//java实importpublicpublic Lcm public publicstatic Of(intm,intn) int while(n!=0) r=m% m= n= return returnm*n Of(m, publicstaticintlcmOf(int returnm*n Of(m, publicstaticvoidmain(String[]args)throwsIOException BufferedReaderln=newBufferedReader(newInputStreamReader(System.in)); intx= of("+x+","+y+")="+ of("+x+","+y+")="+ System.out.println("LCM System.out.println("LCMof("+x+","+y+")=" }阿姆斯153135333153ArmstrongArmstrongArmstrong位数......，这只要使用除法与余数运算就可以了，例如输入inputabc，则：a=input/b=(input%100)/c=input%//java实publicclassArmstrong publicstaticvoidmain(String[]args) for(inti=100;i<=999;i++) inta=i/ intb=(i%100)/ intc=i% if(a*a*a+b*b*b+c*c*c==i)System.out.print(i+""); }最大访ix[i]y[i]在资料输入完毕之后x[i]与y[i]分别进（由小到大道理很简单，//java实importimportpublicclassMaxVisit publicstaticintmaxGuest(int[]x,int[]y,inttime) intnum= for(inti=0;i<x.length;i++) if(time>x[i]) if(time>y[i])num-- return publicstaticvoidmain(String[]args)throwsIOException BufferedReaderbuf=newBufferedReader(newin System.out.println("范例：10 java.util.ArrayListlist=new while(true) Stringinput= if(input.equals("-1")) int[]x=new int[]y=new for(inti=0;i<x.length;i++) Stringinput=(String) String[]strs=input.split(" x[i]= y[i]= for(inttime=0;time<25;time++) System.out.println(timeMaxVisit.maxGuest(x,y,time)); }洗牌（乱数排列新排列，只不过洗牌多了一个花色判断的动作而已。初学者通常会直接想到，随机产生1～N的乱数并将之存入阵列中，后来产生的以1～52的乱数排列为例好了，可以将阵列先依序由1到52填入，然后使用一1～52//java实publicclassShuffleCard publicstaticvoidmain(Stringargs[]) finalintN= int[]poker=newint[N+ //初始化 for(inti=1;i<=N;i++)poker[i]= 洗 for(inti=1;i<=N;i++) intj=(int)(Math.random()* if(j==0)j= inttmp= poker[i]= poker[j]= for(inti=1;i<=N;i++) //判断花 switch((poker[i]-1)/13) case case case case 牌数 intremain=poker[i]% switch(remain) case System.out.print("K case System.out.print("Q case System.out.print("J System.out.print(remain+" if(i%13==0) }约瑟夫问题（Josephus据名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后39Josephus39不要被敌人到，于是决定了一个方式，41个人排成一个圆圈，由第1个人有人都身亡为止。然而Josephus和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场游戏。约瑟夫问题可用代数分析来求解，将这个问题扩大好了，假设现在您与m个朋友己与朋友免于游戏，这两个圆圈内圈是排列顺序，而外圈是顺序，如下41由索引1开始列出就可以得知每个位置的顺序这就是约瑟夫排列41个31754031618267371983527920321041211128391222331329由上可知，最后一个的是在第31个位置，而倒数第二个的要排在第16//java实publicclassJosephus publicstaticint[]arrayOfJosephus(intnumber,intper) int[]man=new for(intcount=1,i=0,pos=-1;count<=number;count++) do pos(pos1number状处 if(man[pos]==0) ifiper数3 i= }while man[pos]= return publicstaticvoidmain(String[]args) int[]man=Josephus.arrayOfJosephus(41, intalive= for(inti=0;i<41;i++)System.out.print(man[i]+" for(inti=0;i<41;i++) if(man[i]>(41-alive))elseelse if((i+1)%5==0)System.out.print(" }排列组数的排列组合有：123、132、2、、、。12341[234]、2[134]、3[124]、4[123]进行排列，这边利用旋0间隔，例如：1234-234234-2变为21134324-23312124423-2344123123//java实publicclassPermutation publicstaticvoidperm(int[]num,inti) if(i<num.length-1) for(intj=i;j<=num.length-1;j++) inttmp=////旋转该区段最右边数字 for(intk=j;k>i;k--)num[k]=num[k- num[i]= perm(num,i+ 还 for(intk=i;k<j;k++)num[k]=num[k+ num[j]= }else //显示此次排 for(intj=1;j<=num.length-1;j++)+" publicstaticvoidmain(String[]args) int[]num=newint[4+ for(inti=1;i<=num.length-1;i++)num[i]= perm(num, }得的，当然学生的分数可能相同。这个问题基本上要解不难只要使用额外的一个阵列走访分数阵列就可以了，for(i=0;i<count;i++){juni[i]=1;for(j=0;j<count;j++){if(score[j]>score[i])}}printf("得分\t\n");for(i0;icounti++)printf("%d\t%d\n",score[i],上面这个方法虽然简单，但是反覆计算的次数是n^2，如果n值变大，那么运算junin+2，0，如下所接下来走访分数阵列，并在分数所对应的阵列索引元素上加1，如下所示最后阵列中的「分数+1」」就是得该分数的，如下所示：这样的方式看起来复杂，其实不过在计算某分数之前的人数，假设89分之前的人数为x人，则89分自然就是x+1了，这也是为什么阵列最右边要设定为1的原因；如果89分有y88分自然就是x+y+1，整个阵列右边importpublicclassScoreRank publicstaticvoidmain(String[] throwsNumberFormatException,IOException finalintMAX= finalintMIN= int[]score=newint[MAX+ int[]juni=newint[MAX+ BufferedReaderreader=newBufferedReader(newInputStreamReader(System.in)); intcount= do score[count++]= }while((score[count-1]!=- for(inti=0;i<count;i++) juni[MAX+1]= for(inti=MAX;i>=MIN;i--)juni[i]=juni[i]+ for(inti=0;i<count;i++) System.out.println(score[i]+"\t"+juni[score[i]+ }选择、插入、气泡排选择排序（Selectionsort）、插入排序（Insertionsort）与气泡排序blesort（O(n2)然而它们排序的方式确是值得观察与探讨的。排序前：70803137101486033[1]803137107048603380[110]3137807048603380[11031333748607080]80，像是玩朴克一样牌分作两堆，每次从后面一堆的牌抽出最前端的牌，然，排序前：9277678684558543[7792]678684558543677792[677792]8684558543676777[8677792]6845585436786786888492855678[6843556777848592]67[684355676777848592]排序前：95279049805869182790498058691850[95]95586509069[80802749691850[58809095]27691849[5058809095]691827[495058809095]6918[27495058809095]由于接下来不会再发生交换动作，排序提早i+2n//Java实publicclassBasicSort publicstaticvoidselectionSort(int[]number) forinti0inumber.length1i++ intm= for(intj=i+1;j<number.length; if(number[j]<number[m])m=j;====if(i!=m)swap(number,i,m); publicstaticvoidinjectionSort(int[]number) for(intj=1;j<number.length;j++) inttmp= inti=j- while(tmp<number[i]) number[i+1]= if(i==-1) number[i+1]= publicstaticvoidbubbleSort(int[]number) booleanflag= for(inti=0;i<number.length-1&&flag;i++) flag= for(intj=0;j<number.length-i-1;j++) if(number[j+1]<number[j]) swap(number,j+1, flag= privatestaticvoidswap(int[]number,inti,intj) int t= number[i]= number[j]= publicstaticvoidmain(String[]args) //测试 int[]a= 10,9,1,100,20,200,39,45,23,18,2,2, //测试选择排序 for(intx:a)System.out.print(x+" int[]b=new b= for(intx:b)System.out.print(x+" //测试插入排序 for(intx:a)System.out.print(x+" int[]c=new c= for(intx:c)System.out.print(x+" //测试气泡排序 for(intx:a)System.out.print(x+" int[]d=new d= for(intx:d)System.out.print(x+" }快速排序（一定），虽然快速排序法在状况下可以达O(n2)，但是在多数的情况下，快速对左边与右边数列进行排序，而影响快速排序法效率的正是的选择。这边所介绍的快速演算如下：将最左边的数设定为轴，并记录其值为令索引i从数列左方往右方找，直到找到大于s的数令索引js如果i>=j，则离开回圈如果ij，则交换索引ij将左侧的轴与j进行交换s，s，轴左右两边进行递回，就可以对完成排序的目的，例如下面的实例，*表示要交换的数，[]表示轴：[41] 76* 45 69 [41] 36 45* 69 [41] 36 19 21* [41] 36 19 69 21 36 [41] 69 41递回至排序完成。//java实publicclassQuickSort publicstaticvoidsort(int[]number) sort(number,0,number.length- privatestaticvoidsort(int[]number,intleft,intright) if(left<right) ints= inti= intj=right+ while(true) //向右 while(i+1<number.length&&number[++i]< //向左 while(j-1>-1&&number[--j]> if(i>=j) swap(number,i, number[left]= number[j]= sort(number,left,j- //对左边进行 sort(number,j+1, //对右边进行 privatestaticvoidswap(int[]number,inti,intj) int t= number[i]= number[j]= }快速排序（二在这个例子中，取中间的元素s作比较，同样的先得右找比s大的索引i，然后找比sjij412476114564216919首先left0，right9，(left+right)/2=4（取整数的商），所以轴为索引4的位置，比较的元素是45，您往右找比45大的，往左找比45小的进行交41 76* [45] 69 69 69[41 36 21] 69 publicclassQuickSort publicstaticvoidsort(int[]number) sort(number,0,number.length- privatestaticvoidsort(int[]number,intleft,intright) if(left<right) ints=number[(left+right)/ inti=left- intj=right+ while(true) //向右 while(number[++i]< //向左 while(number[--j]> if(i>=j) swap(number,i, sort(number,left,i- //对左边进行 sort(number,j+1, //对右边进行 privatestaticvoidswap(int[]number,inti,intj) int t= number[i]= number[j]= }快速排序（三之前轴的选择是快速排序法的效率关键之一在这边的快速排序法的轴选择方式更加快了快速排序法的效率，它是来自演算法名书IntroductiontoAlgorithms之中。先说明这个快速排序法的概念，它以最右边的值s作比较的标准，将整个数列分ss份，如下所示：在排序的过程中，ij然后将s作，如下所示：整个演算的过程，直接摘录虚拟码来作说明publicclassQuickSort3 publicstaticvoidsort(int[]number) sort(number,0,number.length- privatestaticvoidsort(int[]number,intleft,intright) if(left<right) intq=partition(number,left, sort(number,left,q- sort(number,q+1, privatestaticintpartition(intnumber[],intleft,intright) ints= inti=left- for(intj=left;j<right;j++) if(number[j]<=s) swap(number,i, swap(number,i+1, returni+ privatestaticvoidswap(int[]number,inti,intj) int t= number[i]= number[j]= }合并排publicclassMergeSort publicstaticint[]sort(int[]number1,int[]number2) int[]number3=newint[number1.length+ inti=0,j=0,k= while(i<number1.length&&j<number2.length) if(number1[i]<=number2[j])number3[k++]= elsenumber3[k++]= whilewhile(i<number1.length)number3[k++]=while(j<number2.length)number3[k++]=return}}基数排Om)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于LSD（Leastsgnificantdigital）MSD（Mostsgnificantdigital），LSDMSDLSD73,22,93,43,55,14,28,65,39,09012345678981,22,73,93,43,14,55,65,28,012345678914,22,28,39,43,55,65,73,81,LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好，MSD的方式恰与LSD相反，是由数为基底开始进行分配，其他的演算publicclassRadixSort publicstaticvoidsort(int[]number,intd) intk= intn= int[][]temp=new int[]order=new while(n<=d) for(inti=0;i<number.length;i++) intlsd=((number[i]/n)% temp[lsd][order[lsd]]= for(inti=0;i<number.length;i++) if(order[i]!= for(intj=0;j<order[i];j++) number[k]= order[i]= n*= k= publicstaticvoidmain(String[]args) int[]data= 73,22,93,43,55,14,28,65,39,81,33, RadixSort.sort(data, for(inti=0;i<data.length;i++) System.out.print(data[i]+" }循序查找法（使用卫兵while(i<MAX)if(number[i]==k)}这个方法基本上没有错，但是可以加以改善，可以利用设定卫兵的方式，省去if判断式，卫兵通常设定在数列最后或是最前方，假设设定在列前方好了（索引0的位置我们从数列后方向前找如果找到指定的资料时其索引值不是0，表示在数列走访完之前就找到了，在程式的撰写上，只要使用一个while回圈就可以了。publicclassLinearSearch publicstaticintsearch(int[]number,intdes) int[]tmp=newint[number.length+ for(inti=1;i<tmp.length;i++) tmp[i]=number[i- tmp[0]= intk= inti= while(tmp[i]!=k)i-- returni-}} publicstaticvoidmain(String[]args) int[]number= 1,4,2,6,7,3,9, intfind=LinearSearch.search(number, if(find0System.out.println elseSystem.out.println( }二分查0）：[32457576768839092324575767[6883909295]9092，再搜寻右边的数列，这次就找到所要的数了：324575767688390[9295]publicclassBinarySearch publicstaticintsearch(int[]number,intdes) intlow= intupper=number.length- while(low<=upper) intmid=(low+upper)/ if(number[mid]<des)low=mid+ elseif(number[mid]>des)upper=mid- elsereturn return- publicstaticvoidmain(String[]args) int[]number= 1,4,2,6,7,3,9, intfind=BinarySearch.search(number, if(find1System.out.println elseSystem.out.println( }插补查行搜寻，在搜寻的对象大于500时，插补搜寻比二分搜寻法来的快速。相同的，至于中间值的寻找是透过比例运算，如下所示，其中K是指定要寻找的对象，而mpublicclassInterpolationSearch publicstaticintsearch(int[]number,intdes) intlow= intupper=number.length- while(low<=upper) intmid=(upper-low)*(des-number[low])/(number[upper]-number[low])+low; if(mid<low||mid>upper)return- if(des<number[mid])upper=mid- elseif(des>number[mid])low=mid+ elsereturn return- publicstaticvoidmain(String[]args) int[]number= 1,4,2,6,7,3,9, intfind=InterpolationSearch.search(number, if(find1System.out.println elseSystem.out.println( }费式查二分搜寻法每次搜寻时都会将搜寻区间分为一半所以其搜寻时间为O(log(2)n)，log(2)表示以2为底的log值，这边要介绍的费氏搜寻，其利用费氏数列作O(logn)。氏数列这在之前有提过费氏搜寻会先透过计算求出第一个要搜寻数的10一定是F5，而第一个要搜寻的位置有两个可能，例如若在下面的数列搜寻的话（01- 195F5=5F4、F3、F20由于第一个搜寻值索引F5=5处的值小于19，所以此时必须对齐数列右方，也F5+27，然后如同上述的方式进行搜寻，如至于第一个搜寻值是如何找到的？我们可以由以下这个来求得其中n为搜Fx+m=nFx<=nFxn10Fx+m=取Fx =8,m=2，所以我们可以对照费氏数列得x=6，然而第一个数的可能位置之一并不是F6，而是第x-1的费氏数，也就是F5 =5。如果数列number在索引5处的值小于指定的搜寻值，则第一个搜寻位置就是索5m， m5277m费氏搜寻看来难懂，但只要掌握Fx+m=n这个，自己找几个实例算一publicclassFibonacciSearch publicstaticintsearch(int[]number,intdes) int[]fib= intx=findX(fib,number.length+1, intm=number.length- inti= if(number[i]<des)i+= while(fib[x]>0) if(number[i]<des)i+=fib[-- elseif(number[i]>des)i-=fib[-- elsereturn return- privatestaticint[]createFibonacci(intmax) int[]fib=new for(inti=0;i<fib.length;i++) fib[i]= fib[0]= fib[1]= for(inti=2;i<max;i++)fib[i]=fib[i-1]+fib[i- return privatestaticintfindX(int[]fib,intn,intdes) inti= while(fib[i]<=n) return publicstaticvoidmain(String[]args) int[]number= 1,4,2,6,7,3,9, intfind=FibonacciSearch.search(number, if(find1System.out.println elseSystem.out.println( }稀疏矩体空间成正比，如果多数的元素没有资料，则会造成体空间的浪费，为此，必须设计稀疏矩阵的阵列方式，利用较少的体空间完整的矩000000003000000060000900000001256阵列的第二列起，记录其位置的列索引、行索引与值11233244了不少体的使用。publicclassSparseMatrix publicstaticint[][]restore(int[][]sparse) introw= intcolumn= int[][]array=new intk= for(inti=0;i<row;i++) for(intj=0;j<column;j++) if(k<=sparse[0][2]&&i==sparse[k][0]&&j==sparse[k][1]){ array[i][j]= }elsearray[i][j]= return publicstaticvoidmain(String[]args) int[][]sparse= 5,6, }, 1,1, }, 2,3, }, 3,2, }, 4,4, int[][]array= for(inti=0;i<array.length;i++) for(intj=0;j<array[i].length;j++) System.out.print(array[i][j]+" }矩阵转一维0（Ro（ColumnC/C++、Java等的体配置方式都是以列为主所以您可能会比较熟悉前（Fortran的体配置方式是以行为主）。维阵列，此时索引的对应如下所示，其中row与column是二维阵列索引，locloccolumnrow*行维阵列，此时索引的对应如下所示：locrowcolumn*列u1）、j（u2）、k（u3）分别表示三维阵列的三个索引：以列为主：loci*u2*u3j*u3以行为主：lock*u1*u2j*u1publicclassTwoDimArray publicstaticint[]toOneDimByRow(int[][]array) int[]arr=newint[array.length* for(introw=0;row<array.length;row++) for(intcolumn=0;column<array[0].length;column++) inti=column+row* arr[i]= }} return publicstaticint[]toOneDimByColumn(int[][]array) int[]arr=newint[array.length* for(introw=0;row<array.length;row++) for(intcolumn=0;column<array[0].length;column++) inti=i=row+column* arr[i]= return }上三角、下三角、对称 =0，i>j，123450678900000下三角矩阵是矩阵在对角线以上的元素均为，即Aij=0，i<j， 10 1011 1113 1214上三角或下三角矩阵也有大部份的元素不（为0我们可以将它们使一维阵列来以节省空间而对称矩阵因为对称于对角线所以可以视为上三角或下三角矩阵来。假设矩阵为nxn，为了计算方便，我们让阵列索引由1开始，上三角矩阵化为一维阵列，若以列为主，其为：loc=n*(i-1)-i*(i-1)/2+j化为以行为主，其为：loc=j*(j-1)/2+下三角矩阵化为一维阵列，若以列为主，其为：loc=i*(i-1)/2+若以行为主，其为：loc=n*(j-1)-j*(j-1)/2+publicclassTriangleArray privateint[] privateint publicTriangleArray(int[][]array) length= arr=newint[length*(1+length)/ intloc= for(inti=0;i<length;i++)forfor(intj=0;j<length;j++) if(array[i][j]!=0)arr[loc++]= publicintgetValue(inti,intj) intloc=length*i-i*(i+1)/2+ return publicstaticvoidmain(String[]args) int[][]array= 1,2,3,4, }, 0,6,7,8, }, 0,0,10,11, }, 0,0,0,13, }, 0,0,0,0, TriangleArraytriangleArray=new }奇数魔一般程式语言的阵列索引多由0开始，为了计算方便，我们利用索引1到n份，而在计算是向右(左)上或向下时，我们可以将索引值除以n值，如果得到余数为1就向下，否则就往右(左)上，原理很简单，看看是不是已经在同一列上绕publicclassMatrix publicstaticint[][]magicOdd(intn) int[][]square=newint[n+1][n+ inti= intj=(n+1)/ for(intkey=1;key<=n*n;key++) if((key%n)==1) else if(i==0)i= if(j>n)j= square[i][j]= int[][]matrix=new for(intk=0;k<matrix.length;k++) for(intl=0;l<matrix[0].length;l++) matrix[k][l]=square[k+1][l+ return publicstaticvoidmain(String[]args) int[][]magic= for(intk