IT公司算法笔试试题

部分IT公司笔试算法题1、将一整数逆序后放入一数组中（要求递归实现）voidconvert(int*result,intn){if(n=10)convert(result+1,n/10);*result=n%10;}intmain(intargc,char*argv[]){intn=123456789,result[20]={};convert(result,n);printf(%d:,n);for(inti=0;i9;i++)printf(%d,result[i]);}2、求高于平均分的学生学号及成绩（学号和成绩人工输入）doublefind(inttotal,intn){intnumber,score,average;scanf(%d,&number);if(number!=0){scanf(%d,&score);average=find(total+score,n+1);if(score=average)printf(%d:%d\n,number,score);returnaverage;}else{printf(Average=%d\n,total/n);returntotal/n;}}intmain(intargc,char*argv[]){find(0,0);}3、递归实现回文判断（如：acbdedbca就是回文，判断一个面试者对递归理解的简单程序）intfind(char*str,intn){if(n=1)return1;elseif(str[0]==str[n-1])returnfind(str+1,n-2);elsereturn0;}intmain(intargc,char*argv[]){char*str=abcdedcba;printf(%s:%s\n,str,find(str,strlen(str))?Yes:No);}4、组合问题（从M个不同字符中任取N个字符的所有组合）voidfind(char*source,char*result,intn){if(n==1){while(*source)printf(%s%c\n,result,*source++);}else{inti,j;for(i=0;source[i]!=0;i++);for(j=0;result[j]!=0;j++);for(;i=n;i--){result[j]=*source++;result[j+1]='\0';find(source,result,n-1);}}}intmain(intargc,char*argv[]){intconstn=3;char*source=ABCDE,result[n+1]={0};if(n0&&strlen(source)0&&n=strlen(source))find(source,result,3);}5、分解成质因数(如435234=251*17*17*3*2，据说是华为笔试题)voidprim(intm,intn){if(mn){while(m%n!=0)n++;m/=n;prim(m,n);printf(%d*,n);}}intmain(intargc,char*argv[]){intn=435234;printf(%d=,n);prim(n,2);}6、寻找迷宫的一条出路，o：通路；X：障碍。（大家经常谈到的一个小算法题）#defineMAX_SIZE8intH[4]={0,1,0,-1};intV[4]={-1,0,1,0};charMaze[MAX_SIZE][MAX_SIZE]={{'X','X','X','X','X','X','X','X'},{'o','o','o','o','o','X','X','X'},{'X','o','X','X','o','o','o','X'},{'X','o','X','X','o','X','X','o'},{'X','o','X','X','X','X','X','X'},{'X','o','X','X','o','o','o','X'},{'X','o','o','o','o','X','o','o'},{'X','X','X','X','X','X','X','X'}};voidFindPath(intX,intY){if(X==MAX_SIZE||Y==MAX_SIZE){for(inti=0;iMAX_SIZE;i++)for(intj=0;jMAX_SIZE;j++)printf(%c%c,Maze[i][j],jMAX_SIZE-1?'':'\n');}elsefor(intk=0;k4;k++)if(X=0&&Y=0&&YMAX_SIZE&&XMAX_SIZE&&'o'==Maze[X][Y]){Maze[X][Y]='';FindPath(X+V[k],Y+H[k]);Maze[X][Y]='o';}}intmain(intargc,char*argv[]){FindPath(1,0);}7、随机分配座位，共50个学生，使学号相邻的同学座位不能相邻(早些时候用C#写的，没有用C改写）。staticvoidMain(string[]args){intTmp=0,Count=50;int[]Seats=newint[Count];bool[]Students=newbool[Count];System.RandomRandStudent=newSystem.Random();Students[Seats[0]=RandStudent.Next(0,Count)]=true;for(inti=1;iCount;){Tmp=(int)RandStudent.Next(0,Count);if((!Students[Tmp])&&(Seats[i-1]-Tmp!=1)&&(Seats[i-1]-Tmp)!=-1){Seats[i++]=Tmp;Students[Tmp]=true;}}foreach(intStudentinSeats)System.Console.Write(Student+);System.Console.Read();}8、求网格中的黑点分布。现有6*7的网格，在某些格子中有黑点，已知各行与各列中有黑点的点数之和，请在这张网格中画出黑点的位置。（这是一网友提出的题目，说是他笔试时遇到算法题）#defineROWS6#defineCOLS7intiPointsR[ROWS]={2,0,4,3,4,0};//各行黑点数和的情况intiPointsC[COLS]={4,1,2,2,1,2,1};//各列黑点数和的情况intiCount,iFound;intiSumR[ROWS],iSumC[COLS],Grid[ROWS][COLS];intSet(intiRowNo){if(iRowNo==ROWS){for(intiColNo=0;iColNoCOLS&&iSumC[iColNo]==iPointsC[iColNo];iColNo++)if(iColNo==COLS-1){printf(\nNo.%d:\n,++iCount);for(inti=0;iROWS;i++)for(intj=0;jCOLS;j++)printf(%d%c,Grid[i][j],(j+1)%COLS?'':'\n');iFound=1;//iFound=1，有解}}else{for(intiColNo=0;iColNoCOLS;iColNo++){if(iPointsR[iRowNo]==0){Set(iRowNo+1);}elseif(Grid[iRowNo][iColNo]==0){Grid[iRowNo][iColNo]=1;iSumR[iRowNo]++;iSumC[iColNo]++;if(iSumR[iRowNo]iPointsR[iRowNo]&&iSumC[iColNo]=iPointsC[iColNo])Set(iRowNo);elseif(iSumR[iRowNo]==iPointsR[iRowNo]&&iRowNoROWS)Set(iRowNo+1);Grid[iRowNo][iColNo]=0;iSumR[iRowNo]--;iSumC[iColNo]--;}}}returniFound;//用于判断是否有解}intmain(intargc,char*argv[]){if(!Set(0))printf(Failure!);}9、有4种面值的邮票很多枚，这4种邮票面值分别1,4,12,21，现从多张中最多任取5张进行组合，求取出这些邮票的最大连续组合值。（据说是华为2003年校园招聘笔试题）#defineN5#defineM5intk,Found,Flag[N];intStamp[M]={0,1,4,12,21};//在剩余张数n中组合出面值和ValueintCombine(intn,intValue){if(n=0&&Value==0){Found=1;intSum=0;for(inti=0;iN&&Flag[i]!=0;i++){Sum+=Stamp[Flag[i]];printf(%d,Stamp[Flag[i]]);}printf(\tSum=%d\n\n,Sum);}elsefor(inti=1;iM&&!Found&&n0;i++)if(Value-Stamp[i]=0){Flag[k++]=i;Combine(n-1,Value-Stamp[i]);Flag[--k]=0;}returnFound;}intmain(intargc,char*argv[]){for(inti=1;Combine(N,i);i++,Found=0);}10、大整数数相乘的问题。（这是2002年在一考研班上遇到的算法题）voidMultiple(charA[],charB[],charC[]){intTMP,In=0,LenA=-1,LenB=-1;while(A[++LenA]!='\0');while(B[++LenB]!='\0');intIndex,Start=LenA+LenB-1;for(inti=LenB-1;i=0;i--){Index=Start--;if(B[i]!='0'){for(intIn=0,j=LenA-1;j=0;j--){TMP=(C[Index]-'0')+(A[j]-'0')*(B[i]-'0')+In;C[Index--]=TMP%10+'0';In=TMP/10;}C[Index]=In+'0';}}}intmain(intargc,char*argv[]){charA[]=21839244444444448880088888889;charB[]=38888888888899999999999999988;charC[sizeof(A)+sizeof(B)-1];for(intk=0;ksizeof(C);k++)C[k]='0';C[sizeof(C)-1]='\0';Multiple(A,B,C);for(inti=0;C[i]!='\0';i++)printf(%c,C[i]);}11、求最大连续递增数字串（如“ads3sl456789DF3456ld345AA”中的“456789”）intGetSubString(char*strSource,char*strResult){intiTmp=0,iHead=0,iMax=0;for(intIndex=0,iLen=0;strSource[Index];Index++){if(strSource[Index]='0'&&strSource[Index]='9'&&strSource[Index-1]'0'&&strSource[Index]==strSource[Index-1]+1){iLen++;//连续数字的长度增1}else{//出