C程序设计经典程序举例.doc

C程序设计经典程序举例1、 判断素数（循环、利用算法减少运算次数）例：1159：质因数分解正整数n是两个不同质数的乘积，试求出其中较大的。#include #include int main() long long n,big; int small; int root,i,j; scanf(%lld,&n); for(small=2;small=(int)sqrt(n);) /素数判断过程，从最小素数开始 root=(int)sqrt(small); for(i=2;i=root+1;i+) if(small%i=0)break; if(i=root) if(small=2)small+;else small+=2;/只判断2和奇数，减少运算次数 continue; if(n%small=0) big=n/small; root=(int)sqrt(big); for(i=2;i=root+1;i+) if(big%i=0)break; if(i=root) if(small=2)small+;else small+=2; continue; else break; /得到最大质因数，跳出循环 printf(%d %lld,small,big); return 0; 2、 递归与回溯算法（解决尝试性问题，每一级都对下一级有影响）例：1085：0/1迷宫问题给定一个由0（表示墙壁）和1（表示道路）的迷宫，请你判断进入迷宫后，仅通过横向和纵向的行走是否能从迷宫中走出来，即能否从坐标（1，1）走到（n，m）。#include #include int starti,startj; int endi,endj;/定义迷宫起止点 int success=0; /用于判断是否成功通路 int main() int visit(int i,int j,int maze10); int i,j; int n,m; int maze1010; scanf(%d %d,&n,&m); for(i=1;i=n;i+) for(j=1;j=m;j+) scanf(%d,&mazeij); starti=1,startj=1,endi=n,endj=m; if(visit(starti,startj,maze)=0) printf(NO); else printf(YES); return 0; int visit(int i,int j,int maze10) mazeij=-1; /安全性判断已经经过的路 if(i=endi&j=endj) success=1; /成功到达终点 /进行 四个方向的尝试 if(success!=1&mazeij+1=1) visit(i,j+1,maze); if(success!=1&mazei+1j=1) visit(i+1,j,maze); if(success!=1&mazei-1j=1) visit(i-1,j,maze); if(success!=1&mazeij-1=1) visit(i,j-1,maze); mazeij=0;/尝试失败返回0，尝试成功返回1 return success; 例：全排列问题输入一个正整数n，按字典序打印其全排列#includeint used16=0;/是否使用判断 int result16=0;/打印结果 void proc(int step,int n)/按步进行数组赋值 int i;if(stepn)for(i=1;i=n;i+)printf(%d ,resulti);printf(n); elsefor(i=1;i=n;i+)if(usedi=0)resultstep=i;usedi=1;proc(step+1,n);usedi=0;/回溯 int main()int n;scanf(%d,&n);proc(1,n);return 0;例：二分查找#include int bisearch( int ary, int left, int right, int num ) printf(search %d from %d to %dn, num, left, right ); int mid;/设置二分点进行比较 if(leftright) return -1; /未找到需查找的点 mid=(left+right)/2; if(arymid=num) return mid; else /与二分点进行大小比较后进入递归 if(arymidnum) bisearch(ary, left, mid-1, num); else if(arymidnum) bisearch(ary, mid+1,right,num);int main() int n, array10000, i, num; scanf(%d, &n); scanf(%d, &num); for (i=0;in; i + ) scanf(%d,&arrayi); /数组需有序，若无序数组先进行排序 printf( %d,bisearch(array,0,n-1,num); return 0;3、 排序问题 冒泡排序快排函数4、 字符串处理例：判断回文#include#include#includeint main()char *s=(char*)malloc(sizeof(char)*256);char change256=0;gets(s);int len=strlen(s);int i;for(i=0;istrlen(pstr1)&find!=NULL)/循环在剩余字符串中能寻找到字符串1时继续进行 char change400=0; char *use=find; find=strstr(find,pstr1);/寻找字符串1 for(int i=0;i(find-use);i+) changei=*(use+i);find=find+strlen(pstr1);/直接跳过字符串1strcat(final,change);/将出现字符串1之前的部分粘到最终字符串中strcat(final,pstr2);/粘贴字符串2到最终字符串if