C程序设计经典程序举例

《C程序设计经典程序举例》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、small==2)small++;elsesmall+=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++;elsesmall+=2;continue;}else{break;//得到最大质因数，跳出循环}}}printf("%d%lld",small,big);return0;}1、递归与回溯算法（解决尝试性问题，每一级都对下一级有影响）

3、例：1085：0/1迷宫问题给定一个由0（表示墙壁）和1（表示道路）的迷宫，请你判断进入迷宫后，仅通过横向和纵向的行走是否能从迷宫中走出来，即能否从坐标（1，1）走到（n，m）。#include#includeintstarti,startj;intendi,endj;//定义迷宫起止点intsuccess=0;//用于判断是否成功通路intmain(){intvisit(inti,intj,intmaze[][10]);inti,j;intn,m;intmaze[10][10];scanf("%d%d",&n,&m);for(i=1;i<=n

4、;i++)for(j=1;j<=m;j++){scanf("%d",&maze[i][j]);}starti=1,startj=1,endi=n,endj=m;if(visit(starti,startj,maze)==0){printf("NO");}else{printf("YES");}return0;}intvisit(inti,intj,intmaze[][10]){maze[i][j]=-1;//安全性判断已经经过的路if(i==endi&&j==endj){success=1;//成功到达终点}//进行四个方向的尝试if(success!=1&&maze[i][j+1

5、]==1){visit(i,j+1,maze);}if(success!=1&&maze[i+1][j]==1){visit(i+1,j,maze);}if(success!=1&&maze[i-1][j]==1){visit(i-1,j,maze);}if(success!=1&&maze[i][j-1]==1){visit(i,j-1,maze);}maze[i][j]=0;//尝试失败返回0，尝试成功返回1returnsuccess;}例：全排列问题输入一个正整数n，按字典序打印其全排列#includeintused[16]={0};//是否使用判断intr

6、esult[16]={0};//打印结果voidproc(intstep,intn){//按步进行数组赋值inti;if(step>n){for(i=1;i<=n;i++){printf("%d",result[i]);}printf("");}else{for(i=1;i<=n;i++){if(used[i]==0){result[step]=i;used[i]=1;proc(step+1,n);used[i]=0;//回溯}}}}intmain(){intn;scanf("%d",&n);proc(1,n);return0;}例：二分查找#includei

7、ntbisearch(intary[],intleft,intright,intnum){printf("search%dfrom%dto%d",num,left,right);intmid;//设置二分点进行比较if(left>right)return-1;//未找到需查找的点mid=(left+right)/2;if(ary[mid]==num)returnmid;else//与二分点进行大小比较后进入递归if(ary[mid]>num)bisearch(ar