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+)if(sm

2、all%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; elsebreak;/ 得到最大质因数，跳出循环printf("%d %lld",small,big);return 0

3、;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);int i,j;int n,m

4、;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;/ 安全性判断

5、已经经过的路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，尝试成功返回1retu

6、rn 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(usedi=0)resultstep=i;usedi=1;proc(step+1,n);

7、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>right)return -1;/ 未找到需查找的点mid=(left+right)/2

8、;if(arymid=num)return mid;else/ 与二分点进行大小比较后进入递归if(arymid>num)bisearch(ary, left, mid-1, num);elseif(arymid<num)bisearch(ary, mid+1,right,num);int main() int n, array10000, i, num;scanf("%d", &n);scanf("%d", &num); for (i=0;i<n; i + ) scanf("%d",&arr

9、ayi);/ 数组需有序，若无序数组先进行排序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 change256="0"gets(s);int len=strlen(s);int i;for(i=0;i&l

10、t;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;/ 如果原字符串与字符串1 相同直接替换elseif(strstr(stence,pstr1)=NULL)r

11、eturn stence;/ 找不到字符串1elsechar *find=stence;char final400="0" ；while(strlen(find)>strlen(pstr1)&&find!=NULL)/ 循环在剩余字符串中能寻找到字符串1 时继续进行char change400="0"char *use=find;find=strstr(find,pstr1);/ 寻找字符串1for(int i=0;i<(find-use);i+)changei=*(use+i);find=find+strlen(pstr1);/ 直接跳过字符串1strcat(final,change);/ 将出现字符串1 之前的部分粘到最终字符