搜索
1字符串匹配的KMP算法#includestdio.h#includestdlib.h#includestring.h/*功能：求模式串值*参数：ptn：模式串*nextval：保存模式串值的数组*/voidget_nextval(charconst*ptn,int*nextval){inti=0;nextval[0]=-1;intj=-1;intplen=strlen(ptn);if(ptn==NULL||nextval==NULL){return;}while(iplen){if(j==-1||ptn[i]==ptn[j]){++i;++j;if(ptn[i]!=ptn[j]){nextval[i]=j;}else{nextval[i]=nextval[j];}}else{j=nextval[j];}}}/*功能：实现KMP算法*参数：src：源串*patn：模式串*nextval：模式串值*pos：源串开始的位置*返回值：若匹配成功，则返回下标；若出错或匹配不成功，则返回-1*/intkmp_search(charconst*src,charconst*patn,intconst*nextval,intpos){inti=pos;intj=0;if(src==NULL||patn==NULL){return-1;}intslen=strlen(src);intplen=strlen(patn);if(pos0||posslen){return-1;}while(islen&&jplen){if(j==-1||src[i]==patn[j]){++i;++j;}else{j=nextval[j];//当匹配失效时，直接用p[j_next]与s[i]比较//下面阐述怎么求这个值，即匹配失效后的下一次匹配的位置}}if(j=plen){returni-plen;//返回下标，从0开始}else{return-1;}}intmain(){charsrc[]=aabcabcebafabcabceabcaefabcacdabcababce;charprn[]=abce;int*nextval=(int*)malloc(sizeof(int)*strlen(prn));get_nextval(prn,nextval);inti=0;for(i=0;istrlen(prn);i++){printf(%d,nextval[i]);}printf(\n);printf(theresultis:%d\n,kmp_search(src,prn,nextval,5));return0;}2括号匹配检测#includestdio.h#includestdlib.h#defineTRUE1#defineFALSE0#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefintStatus;typedefcharSElemType;typedefstruct{SElemType*base,*top;intstacksize;}SqStack;StatusInitStack(SqStack&S){S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)returnFALSE;S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnTRUE;}StatusPush(SqStack&S,SElemTypee){if(S.top-S.base=S.stacksize){S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base)returnFALSE;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*(S.top++)=e;returnTRUE;}StatusPop(SqStack&S,SElemType&e){if(S.top==S.base)returnFALSE;e=*(--S.top);returnTRUE;}StatusCmp(SElemTypea,SElemTypeb){if(a-b==1)returnTRUE;elseif(a-b==2)returnTRUE;elsereturnFALSE;}StatusCheck(){SqStackS;SElemTypech,e;InitStack(S);while((ch=getchar())!='\n'){if(ch=='('||ch=='['||ch=='{')Push(S,ch);elseif(ch==')'||ch==']'||ch=='}'){if(!Pop(S,e))returnFALSE;if(!Cmp(ch,e))returnFALSE;}}if(S.top==S.base)returnTRUE;returnFALSE;}voidmain(){printf(括号匹配的检验\n\n请输入括号:);if(Check())printf(正确!);elseprintf(错误!);}3求一个数组的最长递减子序列intFun(intaIn[],intpTable[],intnLen){intnMaxLen=0;for(inti=nLen-1;i=0;--i){intnMax=0;for(intj=i+1;jnLen;++j){if(aIn[j]aIn[i]){nMax=nMaxpTable[j]?pTable[j]:nMax;}}pTable[i]=1+nMax;nMaxLen=nMaxLenpTable[i]?pTable[i]:nMaxLen;}returnnMaxLen;}voidPrintMaxSubsequence(intaIn[],intpTable[],intnMaxLen,intnLen){for(inti=0,j=0;inLen;++i){if(pTable[i]==nMaxLen){coutaIn[i];nMaxLen--;}}coutendl;}4.A、B两个量杯，容量分别为M升、N升，现在要用A和B给另一个量杯C盛水K升，C量杯足够大，备用水无限。编程输出每一个步骤三个杯子中的水量。比如：输出(0,0,0),(M,0,0)等。voidShow(int&i,intA,intB,intC)//i记录操作的次数{couti.(A,B,C)endl;i++;}intGCD(intM,intN)//辗转相除法求最大公约数{if(M=N){if(M%N==0)returnN;elsereturnGCD(M%N,N);}else{if(N%M==0)returnM;elsereturnGCD(M,N%M);}}boolSolution(intM,intN,intK){//M,N,K是三个容器的容量//A,B,C是三个容器目前的水量intA=0,B=0,C=0,i=1;intK1=K%N;intL=GCD(M,N);if(K1%L!=0)//不可能实现returnfalse;while(C!=K1){//A中盛满水倒给CA=M;Show(i,A,B,C);C+=A;A=0;Show(i,A,B,C);//如果C水量超过N，就倒走Nwhile(CN){if((K-C)%M==0)//改进点break;B=N;C-=N;Show(i,A,B,C);B=0;Show(i,A,B,C);}if((K-C)%M==0)//改进点break;}if((K-C)%M==0){//给C倒上若干杯A中的水，改进点while(C!=K){A=M;Show(i,A,B,C);A=0;C+=M;Show(i,A,B,C);}}else{//给C倒上若干杯B中的水while(C!=K){B=N;Show(i,A,B,C);B=0;C+=N;Show(i,A,B,C);}}returntrue;}5.输出一个字符串的所有组合voidCombineRecursiveImpl(constchar*str,char*begin,char*end){if(*str==0){*end=0;if(begin!=end){coutbegin;}coutendl;}CombineRecursiveImpl(str+1,begin,end);*end=*str;CombineRecursiveImpl(str+1,begin,end+1);}voidCombineRecursive(constcharstr[]){if(str==NULL){return;}constintMAXLENGTH=64;charresult[MAXLENGTH];CombineRecursiveImpl(str,result,result);}6.有1分,2分,5分,10分四种硬币，每种硬币数量无限，给定n分钱，求有多少种组合可以组合成n分钱？#includestdafx.h#includevector#includeiostreamusingnamespacestd;intcount=0;intTarget=0;intcoin[4]={1,2,5,10};inttotal=0;vectorintsolution;voiddfs(intindex){if(total==Target){count++;coutcount:;for(inti=0;i(int)solution.size();i++){coutsolution[i];}coutendl;return;}if(totalTarget)return;for(inti=index;i4;i++){total+=coin[i];solution.push_back(coin[i]);dfs(i);solution.pop_back();total-=coin[i];}}int_tmain(intargc,_TCHAR*argv[]){while(1){count=0;cinTarget;dfs(0);coutcountendl;}return0;}7.马戏团里有个叠罗汉的表演，为了便于美观，下面的人身高和体重都要大于上面的人。现在知道n个演员的身高和体重，请问最多能叠多少层？#includestdafx.h#includeiostream#includefstream#includevector#includecstdlibusingnamespacestd;intN=0;double*weight;double*height;int**map;intmaxDepth=0;vectorintbestPath;intdfs(intindex,vectorint&path){intflag=0;intdepth=0;vectorintbestPath;for(inti=0;iN;i++){if(map[index][i]!=0){flag=1;vectorinttPath;intt=dfs(i,tPath);if(tdepth){path=tPath;depth=t;}}}if(flag==0){path.clear();path.push_back(index);return1;}else{//path=bestPath;path.push_back(index);returndepth+1;}}voidCreateMap(){map=newint*[N];for(inti=0;iN;i++){map[i]=newint[N];memset