c语言经典算法大全

《c语言经典算法大全》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

C语言经典算法大全�老掉牙河内塔费式数列巴斯卡三角形三色棋老鼠走迷官（一）老鼠走迷官（二）骑士走棋盘八个皇后八枚银币生命游戏字串核对双色、三色河内塔背包问题（KnapsackProblem）�数、运算蒙地卡罗法求PIEratosthenes筛选求质数超长整数运算（大数运算）长PI最大公因数、最小公倍数、因式分解完美数阿姆斯壮数最大访客数中序式转后序式（前序式）后序式的运算�关于赌博洗扑克牌（乱数排列）Craps赌博游戏约瑟夫问题（JosephusProblem）�集合问题排列组合格雷码（GrayCode）产生可能的集合 m元素集合的n个元素子集数字拆解�排序得分排行选择、插入、气泡排序Shell排序法-改良的插入排序Shaker排序法-改良的气泡排序Heap排序法-改良的选择排序快速排序法（一）快速排序法（二）快速排序法（三）合并排序法基数排序法�搜寻循序搜寻法（使用卫兵）二分搜寻法（搜寻原则的代表）插补搜寻法费氏搜寻法�矩阵稀疏矩阵多维矩阵转一维矩阵上三角、下三角、对称矩阵奇数魔方阵4N魔方阵2(2N+1)魔方阵 1.河内之塔说明河内之塔(TowersofHanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的，河内为越战时北越的首都，即现在的胡志明市；1883年法国数学家EdouardLucas曾提及这个故事，据说创世纪时Benares有一座波罗教塔，是由三支钻石棒（Pag）所支撑，开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘（Disc），并命令僧侣将所有的金盘从第一根石棒移至第三根石棒，且搬运过程中遵守大盘子在小盘子之下的原则，若每日仅搬一个盘子，则当盘子全数搬运完毕之时，此塔将毁损，而也就是世界末日来临之时。解法如果柱子标为ABC，要由A搬至C，在只有一个盘子时，就将它直接搬至C，当有两个盘子，就将B当作辅助柱。如果盘数超过2个，将第三个以下的盘子遮起来，就很简单了，每次处理两个盘子，也就是：A->B、A->C、B->C这三个步骤，而被遮住的部份，其实就是进入程式的递回处理。事实上，若有n个盘子，则移动完毕所需之次数为2^n-1，所以当盘数为64时，则64所需次数为：2-1=18446744073709551615为5.05390248594782e+16年，也就是约5000世纪，如果对这数字没什幺概念，就假设每秒钟搬一个盘子好了，也要约5850亿年左右。#includevoidhanoi(intn,charA,charB,charC){if(n==1){printf("Movesheet%dfrom%cto%c ",n,A,C);}else{hanoi(n-1,A,C,B);printf("Movesheet%dfrom%cto%c ",n,A,C);hanoi(n-1,B,A,C);}}intmain(){intn;printf("请输入盘数：");scanf("%d",&n);hanoi(n,'A','B','C');return0;} 2.AlgorithmGossip:费式数列说明Fibonacci为1200年代的欧洲数学家，在他的着作中曾经提到：「若有一只免子每个月生一只小免子，一个月后小免子也开始生产。起初只有一只免子，一个月后就有两只免子，二个月后有三只免子，三个月后有五只免子（小免子投入生产）......。如果不太理解这个例子的话，举个图就知道了，注意新生的小免子需一个月成长期才会投入生产，类似的道理也可以用于植物的生长，这就是Fibonacci数列，一般习惯称之为费氏数列，例如以下：1、1、2、3、5、8、13、21、34、55、89......解法依说明，我们可以将费氏数列定义为以下：fn=fn-1+fn-2ifn>1fn=nifn=0,1#include#include#defineN20intmain(void){intFib[N]={0};inti;Fib[0]=0;Fib[1]=1;for(i=2;i#defineN12longcombi(intn,intr){inti;longp=1;for(i=1;i<=r;i++)p=p*(n-i+1)/i;returnp;}voidpaint(){intn,r,t;for(n=0;n<=N;n++){for(r=0;r<=n;r++){inti;/*排版设定开始*/if(r==0){for(i=0;i<=(N-n);i++)printf("");}else{printf("");}/*排版设定结束*/printf("%3d",combi(n,r));}printf(" ");}} 4.AlgorithmGossip:三色棋说明三色旗的问题最早由E.W.Dijkstra所提出，他所使用的用语为DutchNationFlag(Dijkstra为荷兰人)，而多数的作者则使用Three-ColorFlag来称之。假设有一条绳子，上面有红、白、蓝三种颜色的旗子，起初绳子上的旗子颜色并没有顺序，您希望将之分类，并排列为蓝、白、红的顺序，要如何移动次数才会最少，注意您只能在绳子上进行这个动作，而且一次只能调换两个旗子。解法在一条绳子上移动，在程式中也就意味只能使用一个阵列，而不使用其它的阵列来作辅助，问题的解法很简单，您可以自己想像一下在移动旗子，从绳子开头进行，遇到蓝色往前移，遇到白色留在中间，遇到红色往后移，如下所示：只是要让移动次数最少的话，就要有些技巧：如果图中W所在的位置为白色，则W+1，表示未处理的部份移至至白色群组。如果W部份为蓝色，则B与W的元素对调，而B与W必须各+1，表示两个群组都多了一个元素。如果W所在的位置是红色，则将W与R交换，但R要减1，表示未处理的部份减1。注意B、W、R并不是三色旗的个数，它们只是一个移动的指标；什幺时候移动结束呢？一开始时未处理的R指标会是等于旗子的总数，当R的索引数减至少于W的索引数时，表示接下来的旗子就都是红色了，此时就可以结束移动，如下所示：#include#include#include#defineBLUE'b'#defineWHITE'w'#defineRED'r'#defineSWAP(x,y){chartemp;temp=color[x];color[x]=color[y];color[y]=temp;}intmain(){charcolor[]={'r','w','b','w','w', 'b','r','b','w','r',''};intwFlag=0;intbFlag=0;intrFlag=strlen(color)-1;inti;for(i=0;i#includeintvisit(int,int);intmaze[7][7]={{2,2,2,2,2,2,2},{2,0,0,0,0,0,2},{2,0,2,0,2,0,2},{2,0,0,2,0,2,2},{2,2,0,2,0,2,2},{2,0,0,0,0,0,2},{2,2,2,2,2,2,2}};intstartI=1,startJ=1;//入口intendI=5,endJ=5;//出口intsuccess=0;intmain(void){inti,j;printf("显示迷宫： ");for(i=0;i<7;i++){for(j=0;j<7;j++)if(maze[i][j]==2)printf("█");elseprintf("");printf(" ");}if(visit(startI,startJ)==0)printf(" 没有找到出口！ "); else{printf(" 显示路径： ");for(i=0;i<7;i++){for(j=0;j<7;j++){if(maze[i][j]==2)printf("█");elseif(maze[i][j]==1)printf("◇");elseprintf("");}printf(" ");}}return0;}intvisit(inti,intj){maze[i][j]=1;if(i==endI&&j==endJ)success=1;if(success!=1&&maze[i][j+1]==0)visit(i,j+1);if(success!=1&&maze[i+1][j]==0)visit(i+1,j);if(success!=1&&maze[i][j-1]==0)visit(i,j-1);if(success!=1&&maze[i-1][j]==0)visit(i-1,j);if(success!=1)maze[i][j]=0;returnsuccess;} 6.AlgorithmGossip:老鼠走迷官（二）说明由于迷宫的设计，老鼠走迷宫的入口至出口路径可能不只一条，如何求出所有的路径呢？解法求所有路径看起来复杂但其实更简单，只要在老鼠走至出口时显示经过的路径，然后退回上一格重新选择下一个位置继续递回就可以了，比求出单一路径还简单，我们的程式只要作一点修改就可以了。#include#includevoidvisit(int,int);intmaze[9][9]={{2,2,2,2,2,2,2,2,2},{2,0,0,0,0,0,0,0,2},{2,0,2,2,0,2,2,0,2},{2,0,2,0,0,2,0,0,2},{2,0,2,0,2,0,2,0,2},{2,0,0,0,0,0,2,0,2},{2,2,0,2,2,0,2,2,2},{2,0,0,0,0,0,0,0,2},{2,2,2,2,2,2,2,2,2}};intstartI=1,startJ=1;//入口intendI=7,endJ=7;//出口intmain(void){inti,j;printf("显示迷宫： ");for(i=0;i<7;i++){for(j=0;j<7;j++)if(maze[i][j]==2)printf("█");elseprintf("");printf(" ");}visit(startI,startJ); return0;}voidvisit(inti,intj){intm,n;maze[i][j]=1;if(i==endI&&j==endJ){printf(" 显示路径： ");for(m=0;m<9;m++){for(n=0;n<9;n++)if(maze[m][n]==2)printf("█");elseif(maze[m][n]==1)printf("◇");elseprintf("");printf(" ");}}if(maze[i][j+1]==0)visit(i,j+1);if(maze[i+1][j]==0)visit(i+1,j);if(maze[i][j-1]==0)visit(i,j-1);if(maze[i-1][j]==0)visit(i-1,j);maze[i][j]=0;} 7.AlgorithmGossip:骑士走棋盘说明骑士旅游（Knighttour）在十八世纪初倍受数学家与拼图迷的注意，它什么时候被提出已不可考，骑士的走法为西洋棋的走法，骑士可以由任一个位置出发，它要如何走完[所有的位置？解法骑士的走法，基本上可以使用递回来解决，但是纯綷的递回在维度大时相当没有效率，一个聪明的解法由J.C.Warnsdorff在1823年提出，简单的说，先将最难的位置走完，接下来的路就宽广了，骑士所要走的下一步，「为下一步再选择时，所能走的步数最少的一步。」，使用这个方法，在不使用递回的情况下，可以有较高的机率找出走法（找不到走法的机会也是有的）。#includeintboard[8][8]={0};intmain(void){intstartx,starty;inti,j;printf("输入起始点：");scanf("%d%d",&startx,&starty);if(travel(startx,starty)){printf("游历完成！ ");}else{printf("游历失败！ ");}for(i=0;i<8;i++){for(j=0;j<8;j++){printf("%2d",board[i][j]);}putchar(' ');}return0;}inttravel(intx,inty){//对应骑士可走的八个方向intktmove1[8]={-2,-1,1,2,2,1,-1,-2};intktmove2[8]={1,2,2,1,-1,-2,-2,-1}; //测试下一步的出路intnexti[8]={0};intnextj[8]={0};//记录出路的个数intexists[8]={0};inti,j,k,m,l;inttmpi,tmpj;intcount,min,tmp;i=x;j=y;board[i][j]=1;for(m=2;m<=64;m++){for(l=0;l<8;l++)exists[l]=0;l=0;//试探八个方向for(k=0;k<8;k++){tmpi=i+ktmove1[k];tmpj=j+ktmove2[k];//如果是边界了，不可走if(tmpi<0||tmpj<0||tmpi>7||tmpj>7)continue;//如果这个方向可走，记录下来if(board[tmpi][tmpj]==0){nexti[l]=tmpi;nextj[l]=tmpj;//可走的方向加一个l++;}}count=l;//如果可走的方向为0个，返回if(count==0){ return0;}elseif(count==1){//只有一个可走的方向//所以直接是最少出路的方向min=0;}else{//找出下一个位置的出路数for(l=0;l7||tmpj>7){continue;}if(board[tmpi][tmpj]==0)exists[l]++;}}tmp=exists[0];min=0;//从可走的方向中寻找最少出路的方向for(l=1;l#include#defineN8intcolumn[N+1];//同栏是否有皇后，1表示有intrup[2*N+1];//右上至左下是否有皇后intlup[2*N+1];//左上至右下是否有皇后intqueen[N+1]={0};intnum;//解答编号voidbacktrack(int);//递回求解intmain(void){inti;num=0;for(i=1;i<=N;i++)column[i]=1;for(i=1;i<=2*N;i++)rup[i]=lup[i]=1;backtrack(1);return0;}voidshowAnswer(){intx,y; printf(" 解答%d ",++num);for(y=1;y<=N;y++){for(x=1;x<=N;x++){if(queen[y]==x){printf("Q");}else{printf(".");}}printf(" ");}}voidbacktrack(inti){intj;if(i>N){showAnswer();}else{for(j=1;j<=N;j++){if(column[j]==1&&rup[i+j]==1&&lup[i-j+N]==1){queen[i]=j;//设定为占用column[j]=rup[i+j]=lup[i-j+N]=0;backtrack(i+1);column[j]=rup[i+j]=lup[i-j+N]=1;}}}} 9.AlgorithmGossip:八枚银币说明现有八枚银币abcdefgh，已知其中一枚是假币，其重量不同于真币，但不知是较轻或较重，如何使用天平以最少的比较次数，决定出哪枚是假币，并得知假币比真币较轻或较重。解法单就求假币的问题是不难，但问题限制使用最少的比较次数，所以我们不能以单纯的回圈比较来求解，我们可以使用决策树（decisiontree），使用分析与树状图来协助求解。一个简单的状况是这样的，我们比较a+b+c与d+e+f，如果相等，则假币必是g或h，我们先比较g或h哪个较重，如果g较重，再与a比较（a是真币），如果g等于a，则g为真币，则h为假币，由于h比g轻而g是真币，则h假币的重量比真币轻。#include#include#includevoidcompare(int[],int,int,int);voideightcoins(int[]);intmain(void){intcoins[8]={0};inti;srand(time(NULL));for(i=0;i<8;i++)coins[i]=10;printf(" 输入假币重量(比10大或小)：");scanf("%d",&i);coins[rand()%8]=i;eightcoins(coins);printf(" 列出所有钱币重量：");for(i=0;i<8;i++)printf("%d",coins[i]);printf(" ");return0; }voidcompare(intcoins[],inti,intj,intk){if(coins[i]>coins[k])printf(" 假币%d较重",i+1);elseprintf(" 假币%d较轻",j+1);}voideightcoins(intcoins[]){if(coins[0]+coins[1]+coins[2]==coins[3]+coins[4]+coins[5]){if(coins[6]>coins[7])compare(coins,6,7,0);elsecompare(coins,7,6,0);}elseif(coins[0]+coins[1]+coins[2]>coins[3]+coins[4]+coins[5]){if(coins[0]+coins[3]==coins[1]+coins[4])compare(coins,2,5,0);elseif(coins[0]+coins[3]>coins[1]+coins[4])compare(coins,0,4,1);if(coins[0]+coins[3]coins[1]+coins[4])compare(coins,3,1,0);if(coins[0]+coins[3]#include#include#defineMAXROW10#defineMAXCOL25#defineDEAD0#defineALIVE1intmap[MAXROW][MAXCOL],newmap[MAXROW][MAXCOL];voidinit();intneighbors(int,int);voidoutputMap();voidcopyMap();intmain(){introw,col;charans;init();while(1){outputMap();for(row=0;row=MAXROW||c<0||c>=MAXCOL)continue;if(map[r][c]==ALIVE)count++;}if(map[row][col]==ALIVE)count--;returncount;}voidoutputMap(){introw,col;printf(" %20cGameoflifecellstatus ");for(row=0;row#include#includevoidtable(char*);//建立前进表intsearch(int,char*,char*);//搜寻关键字voidsubstring(char*,char*,int,int);//取出子字串intskip[256];intmain(void){charstr_input[80];charstr_key[80];chartmp[80]={''};intm,n,p;printf("请输入字串：");gets(str_input);printf("请输入搜寻关键字：");gets(str_key);m=strlen(str_input);//计算字串长度n=strlen(str_key);table(str_key);p=search(n-1,str_input,str_key);while(p!=-1){substring(str_input,tmp,p,m); printf("%s ",tmp);p=search(p+n+1,str_input,str_key);}printf(" ");return0;}voidtable(char*key){intk,n;n=strlen(key);for(k=0;k<=255;k++)skip[k]=n;for(k=0;kvoidhanoi(intdisks,charsource,chartemp,chartarget){if(disks==1){printf("movediskfrom%cto%c ",source,target);printf("movediskfrom%cto%c ",source,target);}else{hanoi(disks-1,source,target,temp);hanoi(1,source,temp,target);hanoi(disks-1,temp,source,target);}}voidhanoi2colors(intdisks){charsource='A';chartemp='B';chartarget='C';inti;for(i=disks/2;i>1;i--){hanoi(i-1,source,temp,target);printf("movediskfrom%cto%c ",source,temp);printf("movediskfrom%cto%c ",source,temp);hanoi(i-1,target,temp,source);printf("movediskfrom%cto%c ",temp,target);} printf("movediskfrom%cto%c ",source,temp);printf("movediskfrom%cto%c ",source,target);}intmain(){intn;printf("请输入盘数：");scanf("%d",&n);hanoi2colors(n);return0;}三色河内塔C实作#includevoidhanoi(intdisks,charsource,chartemp,chartarget){if(disks==1){printf("movediskfrom%cto%c ",source,target);printf("movediskfrom%cto%c ",source,target);printf("movediskfrom%cto%c ",source,target);}else{hanoi(disks-1,source,target,temp);hanoi(1,source,temp,target);hanoi(disks-1,temp,source,target);}}voidhanoi3colors(intdisks){charsource='A';chartemp='B';chartarget='C';inti;if(disks==3){printf("movediskfrom%cto%c ",source,temp);printf("movediskfrom%cto%c ",source,temp);printf("movediskfrom%cto%c ",source,target);printf("movediskfrom%cto%c ",temp,target);printf("movediskfrom%cto%c ",temp,source);printf("movediskfrom%cto%c ",target,temp);; }else{hanoi(disks/3-1,source,temp,target);printf("movediskfrom%cto%c ",source,temp);printf("movediskfrom%cto%c ",source,temp);printf("movediskfrom%cto%c ",source,temp);hanoi(disks/3-1,target,temp,source);printf("movediskfrom%cto%c ",temp,target);printf("movediskfrom%cto%c ",temp,target);printf("movediskfrom%cto%c ",temp,target);hanoi(disks/3-1,source,target,temp);printf("movediskfrom%cto%c ",target,source);printf("movediskfrom%cto%c ",target,source);hanoi(disks/3-1,temp,source,target);printf("movediskfrom%cto%c ",source,temp);for(i=disks/3-1;i>0;i--){if(i>1){hanoi(i-1,target,source,temp);}printf("movediskfrom%cto%c ",target,source);printf("movediskfrom%cto%c ",target,source);if(i>1){hanoi(i-1,temp,source,target);}printf("movediskfrom%cto%c ",source,temp);}}}intmain(){intn;printf("请输入盘数：");scanf("%d",&n);hanoi3colors(n);return0;} 13.AlgorithmGossip:背包问题（KnapsackProblem）说明假设有一个背包的负重最多可达8公斤，而希望在背包中装入负重范围内可得之总价物品，假设是水果好了，水果的编号、单价与重量如下所示：0李子4KGNT$45001苹果5KGNT$57002橘子2KGNT$22503草莓1KGNT$11004甜瓜6KGNT$6700解法背包问题是关于最佳化的问题，要解最佳化问题可以使用「动态规划」（Dynamicprogramming），从空集合开始，每增加一个元素就先求出该阶段的最佳解，直到所有的元素加入至集合中，最后得到的就是最佳解。以背包问题为例，我们使用两个阵列value与item，value表示目前的最佳解所得之总价，item表示最后一个放至背包的水果，假设有负重量1～8的背包8个，并对每个背包求其最佳解。逐步将水果放入背包中，并求该阶段的最佳解：放入李子背12345678包负重valu０００450450450450900e00000item－－－０００００放入苹果背12345678包负重valu０００450570570570900e00000item－－－０111０放入橘子 背12345678包负重valu０225225450570675795900e0000000item－22０122０放入草莓背12345678包负重valu110225335450570680795905e00000000item323０1323放入甜瓜背12345678包负重valu110225335450570680795905e00000000item323０1323由最后一个表格，可以得知在背包负重8公斤时，最多可以装入9050元的水果，而最后一个装入的水果是3号，也就是草莓，装入了草莓，背包只能再放入7公斤（8-1）的水果，所以必须看背包负重7公斤时的最佳解，最后一个放入的是2号，也就是橘子，现在背包剩下负重量5公斤（7-2），所以看负重5公斤的最佳解，最后放入的是1号，也就是苹果，此时背包负重量剩下0公斤（5-5），无法再放入水果，所以求出最佳解为放入草莓、橘子与苹果，而总价为9050元。实作C#include#include#defineLIMIT8//重量限制 #defineN5//物品种类#defineMIN1//最小重量structbody{charname[20];intsize;intprice;};typedefstructbodyobject;intmain(void){intitem[LIMIT+1]={0};intvalue[LIMIT+1]={0};intnewvalue,i,s,p;objecta[]={{"李子",4,4500},{"苹果",5,5700},{"橘子",2,2250},{"草莓",1,1100},{"甜瓜",6,6700}};for(i=0;ivalue[s]){//找到阶段最佳解value[s]=newvalue;item[s]=i;}}}printf("物品t价格 ");for(i=LIMIT;i>=MIN;i=i-a[item[i]].size){printf("%st%d ",a[item[i]].name,a[item[i]].price);}printf("合计t%d ",value[LIMIT]); return0;}JavaclassFruit{privateStringname;privateintsize;privateintprice;publicFruit(Stringname,intsize,intprice){this.name=name;this.size=size;this.price=price;}publicStringgetName(){returnname;}publicintgetPrice(){returnprice;}publicintgetSize(){returnsize;}}publicclassKnapsack{publicstaticvoidmain(String[]args){finalintMAX=8;finalintMIN=1;int[]item=newint[MAX+1];int[]value=newint[MAX+1];Fruitfruits[]={newFruit("李子",4,4500),newFruit("苹果",5,5700),newFruit("橘子",2,2250),newFruit("草莓",1,1100), newFruit("甜瓜",6,6700)};for(inti=0;ivalue[s]){//找到阶段最佳解value[s]=newvalue;item[s]=i;}}}System.out.println("物品t价格");for(inti=MAX;i>=MIN;i=i-fruits[item[i]].getSize()){System.out.println(fruits[item[i]].getName()+"t"+fruits[item[i]].getPrice());}System.out.println("合计t"+value[MAX]);}} 14.AlgorithmGossip:蒙地卡罗法求PI说明蒙地卡罗为摩洛哥王国之首都，该国位于法国与义大利国境，以赌博闻名。蒙地卡罗的基本原理为以乱数配合面积公式来进行解题，这种以机率来解题的方式带有赌博的意味，虽然在精确度上有所疑虑，但其解题的思考方向却是个值得学习的方式。解法蒙地卡罗的解法适用于与面积有关的题目，例如求PI值或椭圆面积，这边介绍如何求PI值；假设有一个圆半径为1，所以四分之一圆面积就为PI，而包括此四分之一圆的正方形面积就为1，如下图所示：如果随意的在正方形中投射飞标（点）好了，则这些飞标（点）有些会落于四分之一圆内，假设所投射的飞标（点）有n点，在圆内的飞标（点）有c点，则依比例来算，就会得到上图中最后的公式。至于如何判断所产生的点落于圆内，很简单，令乱数产生X与Y两个数值，如果X^2+Y^2等于1就是落在圆内。#include#include#include#defineN50000intmain(void){inti,sum=0;doublex,y;srand(time(NULL)); for(i=1;i#include#defineN1000intmain(void){inti,j; intprime[N+1];for(i=2;i<=N;i++)prime[i]=1;for(i=2;i*i<=N;i++){//这边可以改进if(prime[i]==1){for(j=2*i;j<=N;j++){if(j%i==0)prime[j]=0;}}}for(i=2;i=0;i--){c[i]=a[i]+b[i]+carry;if(c[i]<10000)carry=0;else{//进位c[i]=c[i]-10000;carry=1;}}}voidsub(int*a,int*b,int*c){inti,borrow=0;for(i=N-1;i>=0;i--){c[i]=a[i]-b[i]-borrow;if(c[i]>=0)borrow=0;else{//借位c[i]=c[i]+10000;borrow=1;}}}voidmul(int*a,intb,int*c){//b为乘数inti,tmp,carry=0;for(i=N-1;i>=0;i--){tmp=a[i]*b+carry;c[i]=tmp%10000;carry=tmp/10000;}}voiddiv(int*a,intb,int*c){//b为除数inti,tmp,remain=0;for(i=0;i#defineL1000#defineNL/4+1//L为位数，N是array长度voidadd(int*,int*,int*);voidsub(int*,int*,int*);voiddiv(int*,int,int*);intmain(void){ints[N+3]={0};intw[N+3]={0};intv[N+3]={0};intq[N+3]={0};intn=(int)(L/1.39793+1);intk;w[0]=16*5;v[0]=4*239;for(k=1;k<=n;k++){//套用公式div(w,25,w);div(v,239,v);div(v,239,v);sub(w,v,q);div(q,2*k-1,q);if(k%2)//奇数项add(s,q,s);else//偶数项sub(s,q,s);}printf("%d.",s[0]); for(k=1;k=0;i--){c[i]=a[i]+b[i]+carry;if(c[i]<10000)carry=0;else{//进位c[i]=c[i]-10000;carry=1;}}}voidsub(int*a,int*b,int*c){inti,borrow=0;for(i=N+1;i>=0;i--){c[i]=a[i]-b[i]-borrow;if(c[i]>=0)borrow=0;else{//借位c[i]=c[i]+10000;borrow=1;}}}voiddiv(int*a,intb,int*c){//b为除数inti,tmp,remain=0;for(i=0;i<=N+1;i++){tmp=a[i]+remain;c[i]=tmp/b;remain=(tmp%b)*10000;}} 18.AlgorithmGossip:最大公因数、最小公倍数、因式分解说明最大公因数使用辗转相除法来求，最小公倍数则由这个公式来求：GCD*LCM=两数乘积解法最大公因数可以使用递回与非递回求解，因式分解基本上就是使用小于输入数的数值当作除数，去除以输入数值，如果可以整除就视为因数，要比较快的解法就是求出小于该数的所有质数，并试试看是不是可以整除，求质数的问题是另一个课题，请参考Eratosthenes筛选求质数。实作（最大公因数、最小公倍数）#include#includeintmain(void){intm,n,r;ints;printf("输入两数：");scanf("%d%d",&m,&n);s=m*n;while(n!=0){r=m%n;m=n;n=r;}printf("GCD：%d ",m);printf("LCM：%d ",s/m);return0;}实作（因式分解） C（不用质数表）#include#includeintmain(void){inti,n;printf("请输入整数：");scanf("%d",&n);printf("%d=",n);for(i=2;i*i<=n;){if(n%i==0){printf("%d*",i);n/=i;}elsei++;}printf("%d ",n);return0;}C（使用质数表）#include#include#defineN1000intprime(int*);//求质数表voidfactor(int*,int);//求factorintmain(void){intptable[N+1]={0};intcount,i,temp;count=prime(ptable); printf("请输入一数：");scanf("%d",&temp);factor(ptable,temp);printf(" ");return0;}intprime(int*pNum){inti,j;intprime[N+1];for(i=2;i<=N;i++)prime[i]=1;for(i=2;i*i<=N;i++){if(prime[i]==1){for(j=2*i;j<=N;j++){if(j%i==0)prime[j]=0;}}}for(i=2,j=0;i#include#defineN1000#defineP10000intprime(int*);//求质数表intfactor(int*,int,int*);//求factorintfsum(int*,int);//sumotproperfactorintmain(void){ intptable[N+1]={0};//储存质数表intfact[N+1]={0};//储存因式分解结果intcount1,count2,i;count1=prime(ptable);for(i=0;i<=P;i++){count2=factor(ptable,i,fact);if(i==fsum(fact,count2))printf("PerfectNumber:%d ",i);}printf(" ");return0;}intprime(int*pNum){inti,j;intprime[N+1];for(i=2;i<=N;i++)prime[i]=1;for(i=2;i*i<=N;i++){if(prime[i]==1){for(j=2*i;j<=N;j++){if(j%i==0)prime[j]=0;}}}for(i=2,j=0;i#include#includeintmain(void){inta,b,c;intinput;printf("寻找Armstrong数： ");for(input=100;input<=999;input++){a=input/100;b=(input%100)/10;c=input%10;if(a*a*a+b*b*b+c*c*c==input)printf("%d",input);}printf(" ");return0;} 21.AlgorithmGossip:最大访客数说明现将举行一个餐会，让访客事先填写到达时间与离开时间，为了掌握座位的数目，必须先估计不同时间的最大访客数。解法这个题目看似有些复杂，其实相当简单，单就计算访客数这个目的，同时考虑同一访客的来访时间与离开时间，反而会使程式变得复杂；只要将来访时间与离开时间分开处理就可以了，假设访客i的来访时间为x[i]，而离开时间为y[i]。在资料输入完毕之后，将x[i]与y[i]分别进行排序（由小到大），道理很简单，只要先计算某时之前总共来访了多少访客，然后再减去某时之前的离开访客，就可以轻易的解出这个问题。#include#include#defineMAX100#defineSWAP(x,y){intt;t=x;x=y;y=t;}intpartition(int[],int,int);voidquicksort(int[],int,int);//快速排序法intmaxguest(int[],int[],int,int);intmain(void){intx[MAX]={0};inty[MAX]={0};inttime=0;intcount=0;printf(" 输入来访与离开125;时间(0~24)：");printf(" 范例：1015");printf(" 输入-1-1结束");while(count>");scanf("%d%d",&x[count],&y[count]);if(x[count]<0)break; count++;}if(count>=MAX){printf(" 超出最大访客数(%d)",MAX);count--;}//预先排序quicksort(x,0,count);quicksort(y,0,count);while(time<25){printf(" %d时的最大访客数：%d",time,maxguest(x,y,count,time));time++;}printf(" ");return0;}intmaxguest(intx[],inty[],intcount,inttime){inti,num=0;for(i=0;i<=count;i++){if(time>x[i])num++;if(time>y[i])num--;}returnnum;}intpartition(intnumber[],intleft,intright){inti,j,s;s=number[right];i=left-1; for(j=left;j((a+(b*d))+(c/d))->bd*+cd/+如果要用程式来进行中序转后序，则必须使用堆叠，演算法很简单，直接叙述的话就是使用回圈，取出中序式的字元，遇运算元直接输出，堆叠运算子与左括号，ISP>ICP的话直接输出堆叠中的运算子，遇右括号输出堆叠中的运算子至左括号。例如(a+b)*(c+d)STACKOUTPUT这个式子，依演算法的输出过程如下：OP((-a(a+(+ab(+ab)-ab+**ab+(*(ab+c*(ab+c+*(+ab+cd*(+ab+cd)*ab+cd+--ab+cd+*如果要将中序式转为前序式，则在读取中序式时是由后往前读取，而左右括号的处理方式相反，其余不变，但输出之前必须先置入堆叠，待转换完成后再将堆叠中的值由上往下读出，如此就是前序表示式。 实作C#include#includeintpostfix(char*);//中序转后序intpriority(char);//决定运算子优先顺序intmain(void){charinput[80];printf("输入中序运算式：");scanf("%s",input);postfix(input);return0;}intpostfix(char*infix){inti=0,top=0;charstack[80]={''};charop;while(1){op=infix[i];switch(op){case'':while(top>0){printf("%c",stack[top]);top--;}printf(" ");return0;//运算子堆叠case'(':if(top<(sizeof(stack)/sizeof(char))){top++; stack[top]=op;}break;case'+':case'-':case'*':case'/':while(priority(stack[top])>=priority(op)){printf("%c",stack[top]);top--;}//存入堆叠if(top<(sizeof(stack)/sizeof(char))){top++;stack[top]=op;}break;//遇)输出至(case')':while(stack[top]!='('){printf("%c",stack[top]);top--;}top--;//不输出(break;//运算元直接输出default:printf("%c",op);break;}i++;}}intpriority(charop){intp;switch(op){case'+':case'-':p=1;break;case'*':case'/':p=2;break; default:p=0;break;}returnp;} 23.AlgorithmGossip:后序式的运算说明将中序式转换为后序式的好处是，不用处理运算子先后顺序问题，只要依序由运算式由前往后读取即可。解法运算时由后序式的前方开堆叠始读取，遇到运算元先存入堆叠，如果遇到运算子，则由堆叠中取出两个运算元进行对应的运算，然后将结果存回堆叠，如果运算式读取完毕，那么堆叠顶的值就是答案了，例如我们计算12+34+*这个运算式（也就是(1+2)*(3+4)）：读取11212+3//1+2后存回3334334+37//3+4后存回*21//3*7后存回#include#includevoidevalPf(char*);doublecal(double,char,double);intmain(void){charinput[80];printf("输入后序式：");scanf("%s",input);evalPf(input);return0;}voidevalPf(char*postfix){ doublestack[80]={0.0};chartemp[2];chartoken;inttop=0,i=0;temp[1]='';while(1){token=postfix[i];switch(token){case'':printf("ans=%f ",stack[top]);return;case'+':case'-':case'*':case'/':stack[top-1]=cal(stack[top],token,stack[top-1]);top--;break;default:if(top#include#include#defineN52intmain(void){intpoker[N+1];inti,j,tmp,remain;//初始化阵列for(i=1;i<=N;i++)poker[i]=i;srand(time(0));//洗牌for(i=1;i<=N;i++){ j=rand()%52+1;tmp=poker[i];poker[i]=poker[j];poker[j]=tmp;}for(i=1;i<=N;i++){//判断花色switch((poker[i]-1)/13){case0:printf("桃");break;case1:printf("心");break;case2:printf("砖");break;case3:printf("梅");break;}//扑克牌数字remain=poker[i]%13;switch(remain){case0:printf("K");break;case12:printf("Q");break;case11:printf("J");break;default:printf("%d",remain);break;}if(i%13==0)printf(" ");}return0;} 25.AlgorithmGossip:Craps赌博游戏说明一个简单的赌博游戏，游戏规则如下：玩家掷两个骰子，点数为1到6，如果第一次点数和为7或11，则玩家胜，如果点数和为2、3或12，则玩家输，如果和为其它点数，则记录第一次的点数和，然后继续掷骰，直至点数和等于第一次掷出的点数和，则玩家胜，如果在这之前掷出了点数和为7，则玩家输。解法规则看来有些复杂，但是其实只要使用switch配合if条件判断来撰写即可，小心不要弄错胜负顺序即可。#include#include#include#defineWON0#defineLOST1#defineCONTINUE2introllDice(){return(rand()%6)+(rand()%6)+2;}intmain(void){intfirstRoll=1;intgameStatus=CONTINUE;intdie1,die2,sumOfDice;intfirstPoint=0;charc;srand(time(0));printf("Craps赌博游戏，按Enter键开始游戏****");while(1){getchar();if(firstRoll){sumOfDice=rollDice();printf(" 玩家掷出点数和：%d ",sumOfDice);switch(sumOfDice){ case7:case11:gameStatus=WON;break;case2:case3:case12:gameStatus=LOST;break;default:firstRoll=0;gameStatus=CONTINUE;firstPoint=sumOfDice;break;}}else{sumOfDice=rollDice();printf(" 玩家掷出点数和：%d ",sumOfDice);if(sumOfDice==firstPoint)gameStatus=WON;elseif(sumOfDice==7)gameStatus=LOST;}if(gameStatus==CONTINUE)puts("未分胜负，再掷一次**** ");else{if(gameStatus==WON)puts("玩家胜");elseputs("玩家输");printf("再玩一次？");scanf("%c",&c);if(c=='n'){puts("游戏结束");break;}firstRoll=1;}}return0;} 26.AlgorithmGossip:约瑟夫问题（JosephusProblem）说明据说着名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。解法约瑟夫问题可用代数分析来求解，将这个问题扩大好了，假设现在您与m个朋友不幸参与了这个游戏，您要如何保护您与您的朋友？只要画两个圆圈就可以让自己与朋友免于死亡游戏，这两个圆圈内圈是排列顺序，而外圈是自杀顺序，如下图所示：使用程式来求解的话，只要将阵列当作环状来处理就可以了，在阵列中由计数1开始，每找到三个无资料区就填入一个计数，直而计数达41为止，然后将阵列由索引1开始列出，就可以得知每个位置的自杀顺序，这就是约瑟夫排列，41个人而报数3的约琴夫排列如下所示：1436138152243031634425175403161826737198352792032104121112839122233132923由上可知，最后一个自杀的是在第31个位置，而倒数第二个自杀的要排在第16个位置，之前的人都死光了，所以他们也就不知道约琴夫与他的朋友并没有遵守游戏规则了。 #include#include#defineN41#defineM3intmain(void){intman[N]={0};intcount=1;inti=0,pos=-1;intalive=0;while(count<=N){do{pos=(pos+1)%N;//环状处理if(man[pos]==0)i++;if(i==M){//报数为3了i=0;break;}}while(1);man[pos]=count;count++;}printf(" 约琴夫排列：");for(i=0;ialive)printf("D");elseprintf("L");if((i+1)%5==0)printf("");}printf(" ");return0;} 27.AlgorithmGossip:排列组合说明将一组数字、字母或符号进行排列，以得到不同的组合顺序，例如123这三个数的排列组合有：123、132、213、231、312、321。解法可以使用递回将问题切割为较小的单元进行排列组合，例如1234的排列可以分为1[234]、2[134]、3[124]、4[123]进行排列，这边利用旋转法，先将旋转间隔设为0，将最右边的数字旋转至最左边，并逐步增加旋转的间隔，例如：1234->旋转1->继续将右边234进行递回处理2134->旋转12变为21->继续将右边134进行递回处理3124->旋转123变为312->继续将右边124进行递回处理4123->旋转1234变为4123->继续将右边123进行递回处理#include#include#defineN4voidperm(int*,int);intmain(void){intnum[N+1],i;for(i=1;i<=N;i++)num[i]=i;perm(num,1);return0;}voidperm(int*num,inti){intj,k,tmp;if(ii;k--)num[k]=num[k-1];num[i]=tmp;perm(num,i+1);//还原 for(k=i;k#include #defineMAXBIT20#defineTRUE1#defineCHANGE_BIT(x)x=((x)=='0'?'1':'0')#defineNEXT(x)x=(1-(x))intmain(void){chardigit[MAXBIT];inti,bits,odd;printf("输入位元数：");scanf("%d",&bits);for(i=0;i=0;i--)printf("%c",digit[i]);printf(" ");NEXT(odd);}return0;} 29.AlgorithmGossip:产生可能的集合说明给定一组数字或符号，产生所有可能的集合（包括空集合），例如给定123，则可能的集合为：{}、{1}、{1,2}、{1,2,3}、{1,3}、{2}、{2,3}、{3}。解法如果不考虑字典顺序，则有个简单的方法可以产生所有的集合，思考二进位数字加法，并注意1出现的位置，如果每个位置都对应一个数字，则由1所对应的数字所产生的就是一个集合，例如：000{}001{3}010{2}011{2,3}100{1}101{1,3}110{1,2}111{1,2,3}了解这个方法之后，剩下的就是如何产生二进位数？有许多方法可以使用，您可以使用unsigned型别加上&位元运算来产生，这边则是使用阵列搜寻，首先阵列内容全为0，找第一个1，在还没找到之前将走访过的内容变为0，而第一个找到的0则变为1，如此重复直到所有的阵列元素都变为1为止，例如：000=>100=>010=>110=>001=>101=>011=>111如果要产生字典顺序，例如若有4个元素，则：{}=>{1}=>{1,2}=>{1,2,3}=>{1,2,3,4}=>{1,2,4}=>{1,3}=>{1,3,4}=>{1,4}=>{2}=>{2,3}=>{2,3,4}=>{2,4}=>{3}=>{3,4}=>{4}简单的说，如果有n个元素要产生可能的集合，当依序产生集合时，如果最后一个元素是n，而倒数第二个元素是m的话，例如：{abcden} 则下一个集合就是{abcde+1}，再依序加入后续的元素。例如有四个元素，而当产生{1234}集合时，则下一个集合就是{123+1}，也就是{124}，由于最后一个元素还是4，所以下一个集合就是{12+1}，也就是{13}，接下来再加入后续元素4，也就是{134}，由于又遇到元素4，所以下一个集合是{13+1}，也就是{14}。实作C（无字典顺序）#include#include#defineMAXSIZE20intmain(void){chardigit[MAXSIZE];inti,j;intn;printf("输入集合个数：");scanf("%d",&n);for(i=0;i#include#defineMAXSIZE20intmain(void){intset[MAXSIZE];inti,n,position=0;printf("输入集合个数：");scanf("%d",&n);printf(" {}");set[position]=1;while(1){printf(" {%d",set[0]);//印第一个数for(i=1;i<=position;i++)printf(",%d",set[i]);printf("}");if(set[position]#include#defineMAX20intmain(void){intset[MAX];intm,n,position; inti;printf("输入集合个数m：");scanf("%d",&m);printf("输入取出元素n：");scanf("%d",&n);for(i=0;i=m-n+1)break;}return0;} 31.AlgorithmGossip:数字拆解说明这个题目来自于数字拆解，我将之改为C语言的版本，并加上说明。题目是这样的：3=2+1=1+1+1所以3有三种拆法4=3+1=2+2=2+1+1=1+1+1+1共五种5=4+1=3+2=3+1+1=2+2+1=2+1+1+1=1+1+1+1+1共七种依此类推，请问一个指定数字NUM的拆解方法个数有多少个？解法我们以上例中最后一个数字5的拆解为例，假设f(n)为数字n的可拆解方式个数，而f(x,y)为使用y以下的数字来拆解x的方法个数，则观察：5=4+1=3+2=3+1+1=2+2+1=2+1+1+1=1+1+1+1+1使用函式来表示的话：f(5)=f(4,1)+f(3,2)+f(2,3)+f(1,4)+f(0,5)其中f(1,4)=f(1,3)+f(1,2)+f(1,1)，但是使用大于1的数字来拆解1没有意义，所以f(1,4)=f(1,1)，而同样的，f(0,5)会等于f(0,0)，所以：f(5)=f(4,1)+f(3,2)+f(2,3)+f(1,1)+f(0,0)依照以上的说明，使用动态程式规画（Dynamicprogramming）来进行求解，其中f(4,1)其实就是f(5-1,min(5-1,1))，f(x,y)就等于f(n-y,min(n-x,y))，其中n为要拆解的数字，而min()表示取两者中较小的数。使用一个二维阵列表格table[x][y]来表示f(x,y)，刚开始时，将每列的索引0与索引1元素值设定为1，因为任何数以0以下的数拆解必只有1种，而任何数以1以下的数拆解也必只有1种：for(i=0;i#include#defineNUM10//要拆解的数字#defineDEBUG0intmain(void){inttable[NUM][NUM/2+1]={0};//动态规画表格intcount=0;intresult=0;inti,j,k;printf("数字拆解 ");printf("3=2+1=1+1+1所以3有三种拆法 ");printf("4=3+1=2+2=2+1+1=1+1+1+1");printf("共五种 ");printf("5=4+1=3+2=3+1+1");printf("=2+2+1=2+1+1+1=1+1+1+1+1");printf("共七种 ");printf("依此类推，求%d有几种拆法？",NUM);//初始化for(i=0;iNUM)//大于NUMcontinue;count=0;for(k=1;k<=j;k++){count+=table[i-k][(i-k>=k)?k:i-k];}table[i][j]=count;}}//计算并显示结果for(k=1;k<=NUM;k++)result+=table[NUM-k][(NUM-k>=k)?k:NUM-k];printf(" result:%d ",result);if(DEBUG){printf(" 除错资讯 ");for(i=0;iscore[i])juni[i]++;}}printf("得分t排行 ");for(i=0;i#include#defineMAX100#defineMIN0intmain(void){intscore[MAX+1]={0};intjuni[MAX+2]={0};intcount=0,i;do{printf("输入分数，-1结束：");scanf("%d",&score[count++]);}while(score[count-1]!=-1);count--;for(i=0;i=MIN;i--)juni[i]=juni[i]+juni[i+1];printf("得分t排行 ");for(i=0;i#include#include#defineMAX10#defineSWAP(x,y){intt;t=x;x=y;y=t;}voidselsort(int[]);//选择排序voidinsort(int[]);//插入排序voidbubsort(int[]);//气泡排序intmain(void){intnumber[MAX]={0};inti;srand(time(NULL));printf("排序前：");for(i=0;i#include#include#defineMAX10#defineSWAP(x,y){intt;t=x;x=y;y=t;}voidshellsort(int[]);intmain(void){intnumber[MAX]={0};inti;srand(time(NULL));printf("排序前：");for(i=0;i0){for(k=0;k=k;j-=gap){if(number[j]>number[j+gap]){SWAP(number[j],number[j+gap]);}elsebreak;}}}printf(" gap=%d：",gap);for(i=0;iright时，则排序完成。实作C#include#include#include#defineMAX10#defineSWAP(x,y){intt;t=x;x=y;y=t;}voidshakersort(int[]);intmain(void){intnumber[MAX]={0};inti;srand(time(NULL)); 36.排序法-改良的选择排序说明选择排序法的概念简单，每次从未排序部份选一最小值，插入已排序部份的后端，其时间主要花费于在整个未排序部份寻找最小值，如果能让搜寻最小值的方式加快，选择排序法的速率也就可以加快，Heap排序法让搜寻的路径由树根至最后一个树叶，而不是整个未排序部份，因而称之为改良的选择排序法。解法Heap排序法使用HeapTree（堆积树），树是一种资料结构，而堆积树是一个二元树，也就是每一个父节点最多只有两个子节点（关于树的详细定义还请见资料结构书籍），堆积树的父节点若小于子节点，则称之为最小堆积（MinHeap），父节点若大于子节点，则称之为最大堆积（MaxHeap），而同一层的子节点则无需理会其大小关系，例如下面就是一个堆积树：可以使用一维阵列来储存堆积树的所有元素与其顺序，为了计算方便，使用的起始索引是1而不是0，索引1是树根位置，如果左子节点储存在阵列中的索引为s，则其父节点的索引为s/2，而右子节点为s+1，就如上图所示，将上图的堆积树转换为一维阵列之后如下所示：首先必须知道如何建立堆积树，加至堆积树的元素会先放置在最后一个树叶节点位置，然后检查父节点是否小于子节点（最小堆积），将小的元素不断与父节点交换，直到满足堆积树的条件为止，例如在上图的堆积加入一个元素12，则堆积树的调整方式如下所示： 建立好堆积树之后，树根一定是所有元素的最小值，您的目的就是：将最小值取出然后调整树为堆积树不断重复以上的步骤，就可以达到排序的效果，最小值的取出方式是将树根与最后一个树叶节点交换，然后切下树叶节点，重新调整树为堆积树，如下所示：调整完毕后，树根节点又是最小值了，于是我们可以重覆这个步骤，再取出最小值，并调整树为堆积树，如下所示：如此重覆步骤之后，由于使用一维阵列来储存堆积树，每一次将树叶与树根交换的动作就是将最小值放至后端的阵列，所以最后阵列就是变为已排序的状态。其实堆积在调整的过程中，就是一个选择的行为，每次将最小值选至树根，而选择的路径并不是所有的元素，而是由树根至树叶的路径，因而可以加快选择的过程，所以Heap排序法才会被称之为改良的选择排序法。 #include#include#include#defineMAX10#defineSWAP(x,y){intt;t=x;x=y;y=t;}voidcreateheap(int[]);voidheapsort(int[]);intmain(void){intnumber[MAX+1]={-1};inti,num;srand(time(NULL));printf("排序前：");for(i=1;i<=MAX;i++){number[i]=rand()%100;printf("%d",number[i]);}printf(" 建立堆积树：");createheap(number);for(i=1;i<=MAX;i++)printf("%d",number[i]);printf(" ");heapsort(number);printf(" ");return0;}voidcreateheap(intnumber[]){inti,s,p;intheap[MAX+1]={-1};for(i=1;i<=MAX;i++){heap[i]=number[i];s=i; p=i/2;while(s>=2&&heap[p]>heap[s]){SWAP(heap[p],heap[s]);s=p;p=s/2;}}for(i=1;i<=MAX;i++)number[i]=heap[i];}voidheapsort(intnumber[]){inti,m,p,s;m=MAX;while(m>1){SWAP(number[1],number[m]);m--;p=1;s=2*p;while(s<=m){if(s0;i--)printf("%d",number[i]);}} 37.AlgorithmGossip:快速排序法（一）说明快速排序法（quicksort）是目前所公认最快的排序方法之一（视解题的对象而定），虽然2快速排序法在最差状况下可以达O(n)，但是在多数的情况下，快速排序法的效率表现是相当不错的。快速排序法的基本精神是在数列中找出适当的轴心，然后将数列一分为二，分别对左边与右边数列进行排序，而影响快速排序法效率的正是轴心的选择。这边所介绍的第一个快速排序法版本，是在多数的教科书上所提及的版本，因为它最容易理解，也最符合轴心分割与左右进行排序的概念，适合对初学者进行讲解。解法这边所介绍的快速演算如下：将最左边的数设定为轴，并记录其值为s廻圈处理：令索引i从数列左方往右方找，直到找到大于s的数令索引j从数列左右方往左方找，直到找到小于s的数如果i>=j，则离开回圈如果i#include#include#defineMAX10#defineSWAP(x,y){intt;t=x;x=y;y=t;} voidquicksort(int[],int,int);intmain(void){intnumber[MAX]={0};inti,num;srand(time(NULL));printf("排序前：");for(i=0;i-1&&number[--j]>s);if(i>=j)break; SWAP(number[i],number[j]);}number[left]=number[j];number[j]=s;quicksort(number,left,j-1);//对左边进行递回quicksort(number,j+1,right);//对右边进行递回}} 38.AlgorithmGossip:快速排序法（二）说明在快速排序法（一）中，每次将最左边的元素设为轴，而之前曾经说过，快速排序法的加速在于轴的选择，在这个例子中，只将轴设定为中间的元素，依这个元素作基准进行比较，这可以增加快速排序法的效率。解法在这个例子中，取中间的元素s作比较，同样的先得右找比s大的索引i，然后找比s小的索引j，只要两边的索引还没有交会，就交换i与j的元素值，这次不用再进行轴的交换了，因为在寻找交换的过程中，轴位置的元素也会参与交换的动作，例如：41247611456421691936首先left为0，right为9，(left+right)/2=4（取整数的商），所以轴为索引4的位置，比较的元素是45，您往右找比45大的，往左找比45小的进行交换：412476*11[45]64216919*364124361145*64216919*76412436111964*21*694576[412436111921][64694576]完成以上之后，再初别对左边括号与右边括号的部份进行递回，如此就可以完成排序的目的。#include#include#include#defineMAX10#defineSWAP(x,y){intt;t=x;x=y;y=t;}voidquicksort(int[],int,int);intmain(void){intnumber[MAX]={0};inti,num;srand(time(NULL));printf("排序前：");for(i=0;is);//向左找if(i>=j)break;SWAP(number[i],number[j]);}quicksort(number,left,i-1);//对左边进行递回quicksort(number,j+1,right);//对右边进行递回}} 39.AlgorithmGossip:快速排序法（三）说明之前说过轴的选择是快速排序法的效率关键之一，在这边的快速排序法的轴选择方式更加快了快速排序法的效率，它是来自演算法名书IntroductiontoAlgorithms之中。解法先说明这个快速排序法的概念，它以最右边的值s作比较的标准，将整个数列分为三个部份，一个是小于s的部份，一个是大于s的部份，一个是未处理的部份，如下所示：在排序的过程中，i与j都会不断的往右进行比较与交换，最后数列会变为以下的状态：然后将s的值置于中间，接下来就以相同的步骤会左右两边的数列进行排序的动作，如下所示：整个演算的过程，直接摘录书中的虚拟码来作说明：QUICKSORT(A,p,r)ifpA[j]exchangeA[i+1]<->A[r]returni+1endPARTITION一个实际例子的演算如下所示：#include#include#include#defineMAX10#defineSWAP(x,y){intt;t=x;x=y;y=t;}intpartition(int[],int,int);voidquicksort(int[],int,int);intmain(void){intnumber[MAX]={0};inti,num;srand(time(NULL));printf("排序前：");for(i=0;i#include#include#defineMAX110#defineMAX210#defineSWAP(x,y){intt;t=x;x=y;y=t;}intpartition(int[],int,int);voidquicksort(int[],int,int); voidmergesort(int[],int,int[],int,int[]);intmain(void){intnumber1[MAX1]={0};intnumber2[MAX1]={0};intnumber3[MAX1+MAX2]={0};inti,num;srand(time(NULL));printf("排序前：");printf(" number1[]：");for(i=0;i#includeintmain(void){intdata[10]={73,22,93,43,55,14,28,65,39,81};inttemp[10][10]={0};intorder[10]={0};inti,j,k,n,lsd;k=0;n=1;printf(" 排序前:");for(i=0;i<10;i++)printf("%d",data[i]);putchar(' ');while(n<=10){for(i=0;i<10;i++){lsd=((data[i]/n)%10);temp[lsd][order[lsd]]=data[i];order[lsd]++;}printf(" 重新排列:");for(i=0;i<10;i++){if(order[i]!=0)for(j=0;j#include#include#defineMAX10#defineSWAP(x,y){intt;t=x;x=y;y=t;}intsearch(int[]);intpartition(int[],int,int);voidquicksort(int[],int,int);intmain(void){intnumber[MAX+1]={0}; inti,find;srand(time(NULL));for(i=1;i<=MAX;i++)number[i]=rand()%100;quicksort(number,1,MAX);printf("数列：");for(i=1;i<=MAX;i++)printf("%d",number[i]);printf(" 输入搜寻值：");scanf("%d",&number[0]);if(find=search(number))printf(" 找到数值于索引%d",find);elseprintf(" 找不到数值");printf(" ");return0;}intsearch(intnumber[]){inti,k;k=number[0];i=MAX;while(number[i]!=k)i--;returni;}intpartition(intnumber[],intleft,intright){inti,j,s; s=number[right];i=left-1;for(j=left;j#include#include#defineMAX10#defineSWAP(x,y){intt;t=x;x=y;y=t;}voidquicksort(int[],int,int);intbisearch(int[],int);intmain(void){intnumber[MAX]={0};inti,find;srand(time(NULL));for(i=0;i=0)printf("找到数字于索引%d",i);elseprintf(" 找不到指定数");printf(" ");return0;}intbisearch(intnumber[],intfind){intlow,mid,upper;low=0;upper=MAX-1;while(low<=upper){mid=(low+upper)/2;if(number[mid]find)upper=mid-1;elsereturnmid;}return-1;}voidquicksort(intnumber[],intleft,intright){inti,j,k,s;if(lefts);//向左找if(i>=j)break;SWAP(number[i],number[j]);}quicksort(number,left,i-1);//对左边进行递回quicksort(number,j+1,right);//对右边进行递回}} 44.AlgorithmGossip:插补搜寻法说明如果却搜寻的资料分布平均的话，可以使用插补（Interpolation）搜寻法来进行搜寻，在搜寻的对象大于500时，插补搜寻法会比二分搜寻法来的快速。解法插补搜寻法是以资料分布的近似直线来作比例运算，以求出中间的索引并进行资料比对，如果取出的值小于要寻找的值，则提高下界，如果取出的值大于要寻找的值，则降低下界，如此不断的减少搜寻的范围，所以其本原则与二分搜寻法是相同的，至于中间值的寻找是透过比例运算，如下所示，其中K是指定要寻找的对象，而m则是可能的索引值：实作C#include#include#include#defineMAX10#defineSWAP(x,y){intt;t=x;x=y;y=t;}voidquicksort(int[],int,int);intintsrch(int[],int);intmain(void){intnumber[MAX]={0}; inti,find;srand(time(NULL));for(i=0;i=0)printf("找到数字于索引%d",i);elseprintf(" 找不到指定数");printf(" ");return0;}intintsrch(intnumber[],intfind){intlow,mid,upper;low=0;upper=MAX-1;while(low<=upper){mid=(upper-low)*(find-number[low])/(number[upper]-number[low])+low;if(midupper)return-1;if(findnumber[mid])low=mid+1;elsereturnmid;}return-1;}voidquicksort(intnumber[],intleft,intright){inti,j,k,s;if(lefts);//向左找if(i>=j)break;SWAP(number[i],number[j]);}quicksort(number,left,i-1);//对左边进行递回quicksort(number,j+1,right);//对右边进行递回}} 45.AlgorithmGossip:费氏搜寻法说明二分搜寻法每次搜寻时，都会将搜寻区间分为一半，所以其搜寻时间为O(log(2)n)，log(2)表示以2为底的log值，这边要介绍的费氏搜寻，其利用费氏数列作为间隔来搜寻下一个数，所以区间收敛的速度更快，搜寻时间为O(logn)。解法费氏搜寻使用费氏数列来决定下一个数的搜寻位置，所以必须先制作费氏数列，这在之前有提过；费氏搜寻会先透过公式计算求出第一个要搜寻数的位置，以及其代表的费氏数，以搜寻对象10个数字来说，第一个费氏数经计算后一定是F5，而第一个要搜寻的位置有两个可能，例如若在下面的数列搜寻的话（为了计算方便，通常会将索引0订作无限小的数，而数列由索引1开始）：-infin;135791315171920如果要搜寻5的话，则由索引F5=5开始搜寻，接下来如果数列中的数小于指定搜寻值时，就往左找，大于时就向右，每次找的间隔是F4、F3、F2来寻找，当费氏数为0时还没找到，就表示寻找失败，如下所示：由于第一个搜寻值索引F5=5处的值小于19，所以此时必须对齐数列右方，也就是将第一个搜寻值的索引改为F5+2=7，然后如同上述的方式进行搜寻，如下所示：至于第一个搜寻值是如何找到的？我们可以由以下这个公式来求得，其中n为搜寻对象的个数：F+m=nx F<=nx也就是说Fx必须找到不大于n的费氏数，以10个搜寻对象来说：F+m=10x取F=8,m=2，所以我们可以对照费氏数列得x=6，然而第一个数的可能位置之一并不是F6，x而是第x-1的费氏数，也就是F=5。5如果数列number在索引5处的值小于指定的搜寻值，则第一个搜寻位置就是索引5的位置，如果大于指定的搜寻值，则第一个搜寻位置必须加上m，也就是F+m=5+2=7，也就是索引7的5位置，其实加上m的原因，是为了要让下一个搜寻值刚好是数列的最后一个位置。费氏搜寻看来难懂，但只要掌握F+m=n这个公式，自己找几个实例算一次，很容易就可以理x解；费氏搜寻除了收敛快速之外，由于其本身只会使用到加法与减法，在运算上也可以加快。#include#include#include#defineMAX15#defineSWAP(x,y){intt;t=x;x=y;y=t;}voidcreatefib(void);//建立费氏数列intfindx(int,int);//找x值intfibsearch(int[],int);//费氏搜寻voidquicksort(int[],int,int);//快速排序intFib[MAX]={-999};intmain(void){intnumber[MAX]={0};inti,find;srand(time(NULL));for(i=1;i<=MAX;i++){number[i]=rand()%100;} quicksort(number,1,MAX);printf("数列：");for(i=1;i<=MAX;i++)printf("%d",number[i]);printf(" 输入寻找对象：");scanf("%d",&find);if((i=fibsearch(number,find))>=0)printf("找到数字于索引%d",i);elseprintf(" 找不到指定数");printf(" ");return0;}//建立费氏数列voidcreatefib(void){inti;Fib[0]=0;Fib[1]=1;for(i=2;i0){if(number[i]find)i-=Fib[--x];elsereturni;}return-1;}voidquicksort(intnumber[],intleft,intright){inti,j,k,s;if(lefts);//向左找if(i>=j)break; SWAP(number[i],number[j]);}quicksort(number,left,i-1);//对左边进行递回quicksort(number,j+1,right);//对右边进行递回}} 46.AlgorithmGossip:稀疏矩阵说明如果在矩阵中，多数的元素并没有资料，称此矩阵为稀疏矩阵（sparsematrix），由于矩阵在程式中常使用二维阵列表示，二维阵列的大小与使用的记忆体空间成正比，如果多数的元素没有资料，则会造成记忆体空间的浪费，为此，必须设计稀疏矩阵的阵列储存方式，利用较少的记忆体空间储存完整的矩阵资讯。解法在这边所介绍的方法较为简单，阵列只储存矩阵的行数、列数与有资料的索引位置及其值，在需要使用矩阵资料时，再透过程式运算加以还原，例如若矩阵资料如下，其中0表示矩阵中该位置没有资料：0000000300000006000090000000120这个矩阵是5X6矩阵，非零元素有4个，您要使用的阵列第一列记录其列数、行数与非零元素个数：564阵列的第二列起，记录其位置的列索引、行索引与储存值：1132363294412所以原本要用30个元素储存的矩阵资讯，现在只使用了15个元素来储存，节省了不少记忆体的使用。C#include#includeintmain(void){intnum[5][3]={{5,6,4},{1,1,3}, {2,3,6},{3,2,9},{4,4,12}};inti,j,k=1;printf("sparsematrix： ");for(i=0;i<5;i++){for(j=0;j<3;j++){printf("%4d",num[i][j]);}putchar(' ');}printf(" matrix还原： ");for(i=0;i#includeintmain(void){intarr1[3][4]={{1,2,3,4},{5,6,7,8},{9,10,11,12}}; intarr2[12]={0};introw,column,i;printf("原二维资料： ");for(row=0;row<3;row++){for(column=0;column<4;column++){printf("%4d",arr1[row][column]);}printf(" ");}printf(" 以列为主：");for(row=0;row<3;row++){for(column=0;column<4;column++){i=column+row*4;arr2[i]=arr1[row][column];}}for(i=0;i<12;i++)printf("%d",arr2[i]);printf(" 以行为主：");for(row=0;row<3;row++){for(column=0;column<4;column++){i=row+column*3;arr2[i]=arr1[row][column];}}for(i=0;i<12;i++)printf("%d",arr2[i]);printf(" ");return0;} 48.AlgorithmGossip:上三角、下三角、对称矩阵说明上三角矩阵是矩阵在对角线以下的元素均为0，即A=0，i>j，例如：ij1234506789001011120001314000015下三角矩阵是矩阵在对角线以上的元素均为0，即A=0，i #include#defineN5intmain(void){intarr1[N][N]={{1,2,3,4,5},{0,6,7,8,9},{0,0,10,11,12},{0,0,0,13,14},{0,0,0,0,15}};intarr2[N*(1+N)/2]={0};inti,j,loc=0;printf("原二维资料： ");for(i=0;i#include#defineN5intmain(void){inti,j,key;intsquare[N+1][N+1]={0}; i=0;j=(N+1)/2;for(key=1;key<=N*N;key++){if((key%N)==1)i++;else{i--;j++;}if(i==0)i=N;if(j>N)j=1;square[i][j]=key;}for(i=1;i<=N;i++){for(j=1;j<=N;j++)printf("%2d",square[i][j]);}return0;} 50.AlgorithmGossip:4N魔方阵说明与奇数魔术方阵相同，在于求各行、各列与各对角线的和相等，而这次方阵的维度是4的倍数。解法先来看看4X4方阵的解法：简单的说，就是一个从左上由1依序开始填，但遇对角线不填，另一个由左上由16开始填，但只填在对角线，再将两个合起来就是解答了；如果N大于2，则以4X4为单位画对角线：至于对角线的位置该如何判断，有两个公式，有兴趣的可以画图印证看看，如下所示：左上至右下：j%4==i%4右上至左下：(j%4+i%4)==1#include#include#defineN8 intmain(void){inti,j;intsquare[N+1][N+1]={0};for(j=1;j<=N;j++){for(i=1;i<=N;i++){if(j%4==i%4||(j%4+i%4)==1)square[i][j]=(N+1-i)*N-j+1;elsesquare[i][j]=(i-1)*N+j;}}for(i=1;i<=N;i++){for(j=1;j<=N;j++)printf("%2d",square[i][j]);printf(" ");}return0;} 51.AlgorithmGossip:2(2N+1)魔方阵说明方阵的维度整体来看是偶数，但是其实是一个奇数乘以一个偶数，例如6X6，其中6=2X3，我们也称这种方阵与单偶数方阵。解法如果您会解奇数魔术方阵，要解这种方阵也就不难理解，首先我们令n=2(2m+1)，并将整个方阵看作是数个奇数方阵的组合，如下所示：首先依序将A、B、C、D四个位置，依奇数方阵的规则填入数字，填完之后，方阵中各行的和就相同了，但列与对角线则否，此时必须在A-D与C-B之间，作一些对应的调换，规则如下：将A中每一列(中间列除外)的头m个元素，与D中对应位置的元素调换。将A的中央列、中央那一格向左取m格，并与D中对应位置对调将C中每一列的倒数m-1个元素，与B中对应的元素对调举个实例来说，如何填6X6方阵，我们首先将之分解为奇数方阵，并填入数字，如下所示： 接下来进行互换的动作，互换的元素以不同颜色标示，如下：由于m-1的数为0，所以在这个例子中，C-B部份并不用进行对调。#include#include#defineN6#defineSWAP(x,y){intt;t=x;x=y;y=t;}voidmagic_o(int[][N],int);voidexchange(int[][N],int);intmain(void){intsquare[N][N]={0};inti,j;magic_o(square,N/2);exchange(square,N);for(i=0;i