2022年C程序设计经典程序举例 .pdf

《2022年C程序设计经典程序举例 .pdf》由会员分享，可在线阅读，更多相关《2022年C程序设计经典程序举例 .pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、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+;

2、 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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 7 页 - - - - - - - - - else b

3、reak; / 得到最大质因数，跳出循环 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

4、,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) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 7 页 - - - - - - - - - printf(NO)

5、; 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) vi

6、sit(i,j-1,maze); mazeij=0; / 尝试失败返回0，尝试成功返回1 return success; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7 页 - - - - - - - - - 例：全排列问题输入一个正整数n，按字典序打印其全排列#include int used16=0; / 是否使用判断int result16=0; / 打印结果void proc(int step,int n) / 按步进行数组赋值int i; if(stepn)

7、 for(i=1;i=n;i+) printf(%d ,resulti); printf(n); else for(i=1;i=n;i+) if(usedi=0) resultstep=i; usedi=1; proc(step+1,n); usedi=0; / 回溯 int main() int n; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - scanf(%d,&n); proc(1,n); return 0; 例：二分

8、查找#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(ary

9、midnum) 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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共

10、7 页 - - - - - - - - - 3、排序问题冒泡排序快排函数4、字符串处理例：判断回文#include #include #include int 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);

11、 / 寻找字符串1 for(int i=0;i(find-use);i+) changei=*(use+i); find=find+strlen(pstr1); / 直接跳过字符串1 strcat(final,change); / 将出现字符串1 之前的部分粘到最终字符串中strcat(final,pstr2); / 粘贴字符串2 到最终字符串if(strstr(find,pstr1)=NULL) / 剩余字符串中搜索不到字符串1 break; if(strcmp(find,pstr1)!=0) / 剩余的不是字符串1，直接粘贴到最终字符串中，如果是，直接返回 strcat(final,find); return final; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -