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

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;名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 7 页 -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)名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 7 页 -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;名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 7 页 -例：全排列问题输入一个正整数n，按字典序打印其全排列#include int 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);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;例：二分查找#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;名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 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);/寻找字符串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 页 -