C程序设计经典程序举例

1、C程序设计经典程序举例1、 判断素数（循环、利用算法减少运算次数）例：1159：质因数分解正整数n是两个不同质数的乘积，试求出其中较大的。#include<stdio.h> #include<math.h> 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+

2、) 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",sma

3、ll,big); return 0; 2、 递归与回溯算法（解决尝试性问题，每一级都对下一级有影响）例：1085：0/1迷宫问题给定一个由0（表示墙壁）和1（表示道路）的迷宫，请你判断进入迷宫后，仅通过横向和纵向的行走是否能从迷宫中走出来，即能否从坐标（1，1）走到（n，m）。#include<stdio.h> #include<stdlib.h> int starti,startj; int endi,endj;/定义迷宫起止点 int success=0; /用于判断是否成功通路 int main() int visit(int i,int j,int maze10

4、); 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

5、,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,

6、j-1,maze); mazeij=0;/尝试失败返回0，尝试成功返回1 return success; 例：全排列问题输入一个正整数n，按字典序打印其全排列#include<stdio.h>int used16=0;/是否使用判断 int result16=0;/打印结果 void proc(int step,int n)/按步进行数组赋值 int i;if(step>n)for(i=1;i<=n;i+)printf("%d ",resulti);printf("n"); elsefor(i=1;i<=n;i+)if(us

7、edi=0)resultstep=i;usedi=1;proc(step+1,n);usedi=0;/回溯 int main()int n;scanf("%d",&n);proc(1,n);return 0;例：二分查找#include <stdio.h>int bisearch( int ary, int left, int right, int num ) printf("search %d from %d to %dn", num, left, right ); int mid;/设置二分点进行比较 if(left>rig

8、ht) return -1; /未找到需查找的点 mid=(left+right)/2; if(arymid=num) return mid; else /与二分点进行大小比较后进入递归 if(arymid>num) bisearch(ary, left, mid-1, num); else if(arymid<num) bisearch(ary, mid+1,right,num);int main() int n, array10000, i, num; scanf("%d", &n); scanf("%d", &num);

9、 for (i=0;i<n; i + ) scanf("%d",&arrayi); /数组需有序，若无序数组先进行排序 printf( "%d",bisearch(array,0,n-1,num); return 0;3、 排序问题 冒泡排序快排函数4、 字符串处理例：判断回文#include<stdio.h>#include<string.h>#include<stdlib.h>int main()char *s=(char*)malloc(sizeof(char)*256);char change25

10、6="0"gets(s);int len=strlen(s);int i;for(i=0;i<len;i+)changelen-1-i=*(s+i);if(strcmp(change,s)=0)printf("是"); elseprintf("否");return 0;例：将原字符串中的字符串1替换为字符串2，替换后新出现的字符串不包括在内，仅保留子函数。char* replace(char *stence,char pstr1,char pstr2) if(strcmp(stence,pstr1)=0)return pstr2

11、;/如果原字符串与字符串1相同直接替换elseif(strstr(stence,pstr1)=NULL)return stence;/找不到字符串1else char *find=stence; char final400="0"； while(strlen(find)>strlen(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之前的部分