当前位置:首页 >> 城乡/园林规划 >>

C语言程序设计的常用算法


C 语言程序设计的常用算法
算法(Algorithm) :计算机解题的基本思想方法和步骤。算法的描述:是对要解决一个 问题或要完成一项任务所采取的方法和步骤的描述,包括需要什么数据(输入什么数据、输 出什么结果) 、采用什么结构、使用什么语句以及如何安排这些语句等。通常使用自然语言、 结构化流程图、伪代码等来描述算法。 一、计数、求和、求阶乘等简单算法 此类问题都要使用循环,要注意根据问题确定循环变量的初值、终值或结束条件,更要注意 用来表示计数、和、阶乘的变量的初值。 例:用随机函数产生 100 个[0,99]范围内的随机整数,统计个位上的数字分别为 1,2,3, 4,5,6,7,8,9,0 的数的个数并打印出来。 本题使用数组来处理,用数组 a[100]存放产生的确 100 个随机整数,数组 x[10]来存放个位 上的数字分别为 1,2,3,4,5,6,7,8,9,0 的数的个数。即个位是 1 的个数存放在 x[1] 中,个位是 2 的个数存放在 x[2]中,……个位是 0 的个数存放在 x[10]。 程序代码如下: #include<stdio.h> /////////////////////////////////////////////////////////////////////////////// void main() { int a[101],x[11],i,p; for(i=0;i<=11;i++) x[i]=0; for(i=1;i<=100;i++) { a[i]=rand()%100; printf("%4d",a[i]); if(i%10==0) printf("\n"); } for(i=1;i<=100;i++) { p=a[i]%10; if(p==0) p=10; x[p]=x[p]+1; } for(i=1;i<=10;i++) { p=i; if(i==10) p=0; printf("%d,%d\n",p,x[i]);

} printf("\n"); } 二、求两个整数的最大公约数、最小公倍数 最大公约数的算法思想(最小公倍数=两个整数之积/最大公约数): (1)对于已知两数 m,n,使得 m>n; (2) m 除以 n 得余数 r; (3)若 r=0,则 n 为求得的最大公约数,算法结束;否则执行(4); (4)m←n,n←r,再重复执行(2)。 例:求 m=14,n=6 的最大公约数。 程序代码如下: #include<stdio.h> /////////////////////////////////////////////////////////////////////////////// void main() { int nm,r,n,m,t; printf("please input two numbers:"); scanf("%d,%d",&m,&n); nm=n*m; if(m<n) { t=n; n=m; m=t; } r=m%n; while (r!=0) { m=n; n=r; r=m%n; } printf("G.C.D:%d\n",n); printf("L.C.M:%d\n",nm/n); } 三、判断素数 只能被 1 或本身整除的数称为素数。基本思想:把 m 作为被除数,将 2-sqrt(m)作为除数, 如果都除不尽,m 就是素数,否则就不是。 程序代码如下: #include<stdio.h> #include<math.h>

/////////////////////////////////////////////////////////////////////////////// void main() { int m,i,k; printf("please input a number:"); scanf("%d",&m); k=(int)sqrt(m); for(i=2;i<=k;i++) if(m%i==0) break; if(i>k) printf("the number is a prime number!\n"); else printf("the number is not a prime number!\n"); } 四、验证哥德巴赫猜想(任意一个大于等于 6 的偶数都可以分解为两个素数之和) 基本思想:n 为大于等于 6 的任一偶数,可分解为 n1 和 n2 两个数,分别检查 n1 和 n2 是否 为素数,如都是,则为一组解。如 n1 不是素数,就不必再检查 n2 是否素数。先从 n1=2 开 始, 检验 n1 和 n2 (n2=n-n1) 是否素数。 然后使 n1+1 再检验 n1、 n2 是否素数, …直到 n1=n/2 为止。 验证哥德巴赫猜想的程序代码如下: #include<stdio.h> #include<math.h> /////////////////////////////////////////////////////////////////////////////// void main() { int x,i; int prime(int m); printf("please input a even number(>=6):"); scanf("%d",&x); if (x<6||x%2!=0) printf("data error!\n"); else for(i=2;i<=x/2;i++) if(prime(i)&&prime(x-i)) { printf("%d+%d\n",i,x-i); printf("validate success!\n"); break; } }

/////////////////////////////////////////////////////////////////////////////// int prime(int m) { int i,k; k=(int)sqrt(m); for(i=2;i<=k;i++) if(m%i==0) break; if(i>k) return 1; else return 0; } 五、排序问题 1、选择法排序(升序) 基本思想: 1)对有 n 个数的序列(存放在数组 a[n]中) ,从中选出最小的数,与第 1 个数交换位置; 2)除第 1 个数外,其余 n-1 个数中选最小的数,与第 2 个数交换位置; 3)依次类推,选择了 n-1 次后,这个数列已按升序排列。 程序代码如下: #include<stdio.h> #include<math.h> #define N 10 /////////////////////////////////////////////////////////////////////////////// void main() { int i,j,imin,s,a[N]; printf("input 10 numbers:"); for(i=0;i<N;i++) scanf("%d",&a[i]); for(i=0;i<N-1;i++) { imin=i; for(j=i+1;j<N;j++) if(a[imin]>a[j]) imin=j; if(i!=imin) { s=a[i]; a[i]=a[imin]; a[imin]=s;

} } for(i=0;i<N;i++) printf("%4d",a[i]); printf("\n"); } 2、冒泡法排序(升序) 基本思想:(将相邻两个数比较,小的调到前头) 1)有 n 个数(存放在数组 a(n)中) ,第一趟将每相邻两个数比较,小的调到前头,经 n-1 次 两两相邻比较后,最大的数已"沉底",放在最后一个位置,小数上升"浮起"; 2)第二趟对余下的 n-1 个数(最大的数已"沉底")按上法比较,经 n-2 次两两相邻比较后得 次大的数; 3)依次类推,n 个数共进行 n-1 趟比较,在第 j 趟中要进行 n-j 次两两比较。 程序代码如下: #include<stdio.h> #include<math.h> #define N 10 /////////////////////////////////////////////////////////////////////////////// void main() { int a[N]; int i,j,t; printf("input 10 numbers:"); for(i=0;i<N;i++) scanf("%d",&a[i]); for(j=0;j<N-1;j++) for(i=0;i<N-1-j;i++) if(a[i]>a[i+1]) { t=a[i]; a[i]=a[i+1]; a[i+1]=t; } printf("the sorted numbers:"); for(i=0;i<N;i++) printf("%4d",a[i]); printf("\n"); } 3、合并法排序(将两个有序数组 A、B 合并成另一个有序的数组 C,升序) 基本思想: 1)先在 A、B 数组中各取第一个元素进行比较,将小的元素放入 C 数组;

2)取小的元素所在数组的下一个元素与另一数组中上次比较后较大的元素比较,重复上述 比较过程,直到某个数组被先排完; 3)将另一个数组剩余元素抄入 C 数组,合并排序完成。 程序代码如下: #include<stdio.h> /////////////////////////////////////////////////////////////////////////////// void main() { int a[10],b[10],c[20],i,ia,ib,ic; printf("please input the first array:"); for(i=0;i<10;i++) scanf("%d",&a[i]); printf("please input the second array:"); for(i=0;i<10;i++) scanf("%d",&b[i]); ia=0; ib=0; ic=0; while(ia<10&&ib<10) { if(a[ia]<b[ib]) { c[ic]=a[ia]; ia++; } else { c[ic]=b[ib]; ib++; } ic++; } while(ia<=9) { c[ic]=a[ia]; ia++; ic++; } while(ib<=9) { c[ic]=b[ib]; ib++; ic++;

} for(i=0;i<20;i++) printf("%2d",c[i]); printf("\n"); } 六、查找问题 1、顺序查找法(在一列数中查找某数 x) 基本思想:一列数放在数组 a[1]---a[n]中,待查找的数放在 x 中,把 x 与 a 数组中的元素从 头到尾一一进行比较查找。用变量 p 表示 a 数组元素下标,p 初值为 1,使 x 与 a[p]比较, 如果 x 不等于 a[p],则使 p=p+1,不断重复这个过程;一旦 x 等于 a[p]则退出循环;另外, 如果 p 大于数组长度,循环也应该停止。 程序代码如下: void main() { int a[10],p,x,i; printf("please input the array:"); for(i=0;i<10;i++) scanf("%d",&a[i]); printf("please input the number you want find:"); scanf("%d",&x); p=0; while(x!=a[p]&&p<10) p++; if(p>=10) printf("the number is not found!\n"); else printf("the number is found the no%d!\n",p); } 思考:将上面程序改写一查找函数 Find,若找到则返回下标值,找不到返回-1。 基本思想:一列数放在数组 a[1]---a[n]中,待查找的关键值为 key,把 key 与 a 数组中的元素 从头到尾一一进行比较查找,若相同,查找成功,若找不到,则查找失败。(查找子过程如 下,index:存放找到元素的下标。) 程序代码如下: void main() { int a[10],index,x,i; printf("please input the array:"); for(i=0;i<10;i++) scanf("%d",&a[i]); printf("please input the number you want find:"); scanf("%d",&x); index=-1;

for(i=0;i<10;i++) if(x==a[i]) { index=i; break; } if(index==-1) printf("the number is not found!\n"); else printf("the number is found the no%d!\n",index); } 2、折半查找法(只能对有序数列进行查找) 基本思想:设 n 个有序数(从小到大)存放在数组 a[1]----a[n]中,要查找的数为 x。用变量 bot、top、mid 分别表示查找数据范围的底部(数组下界) 、顶部(数组的上界)和中间, mid=(top+bot)/2,折半查找的算法如下: (1)x=a[mid],则已找到退出循环,否则进行下面的判断; (2)x<a[mid],x 必定落在 bot 和 mid-1 的范围之内,即 top=mid-1; (3)x>a[mid],x 必定落在 mid+1 和 top 的范围之内,即 bot=mid+1; (4)在确定了新的查找范围后,重复进行以上比较,直到找到或者 bot<=top。 程序代码如下: void main() { int a[10],mid,bot,top,x,i,find; printf("please input the array:"); for(i=0;i<10;i++) scanf("%d",&a[i]); printf("please input the number you want find:"); scanf("%d",&x); bot=0; top=9; find=0; while(bot<=top&&find==0) { mid=(top+bot)/2; if(x==a[mid]) { find=1; break; } else if(x<a[mid]) top=mid-1; else bot=mid+1;

} if (find==1) printf("the number is found the no%d!\n",mid); else printf("the number is not found!\n"); } 七、插入法(把一个数插到有序数列中,插入后数列仍然有序) 基本思想:n 个有序数(从小到大)存放在数组 a[1]-a[n]中,要插入的数 x。首先确定 x 插 在数组中的位置 P。 程序代码如下: #include<stdio.h> #define N 10 /////////////////////////////////////////////////////////////////////////////// void insert(int a[], int x) { int p, i; p=0; while(x>a[p] && p<N) p++; for(i=N; i>p; i--) a[i]=a[i-1]; a[p]=x; } /////////////////////////////////////////////////////////////////////////////// void main() { int a[N+1]={1,3,4,7,8,11,13,18,56,78}, x, i; for(i=0; i<N; i++) printf("%d,", a[i]); printf("\nInput x:"); scanf("%d", &x); insert(a, x); for(i=0; i<=N; i++) printf("%d,", a[i]); printf("\n"); } 八、矩阵(二维数组)运算 1、矩阵的加、减运算 加法 C[i,j]=a[i,j]+b[i,j] 减法 C[i,j]=a[i,j]-b[i,j]

2、矩阵相乘 (矩阵 A 有 M*L 个元素,矩阵 B 有 L*N 个元素,则矩阵 C=A*B 有 M*N 个元素,矩阵 C 中任一元素 (i=1,2,…,m; j=1,2,…,n)) 。 程序代码如下: #include<stdio.h> #define M 2 #define L 4 #define N 3 /////////////////////////////////////////////////////////////////////////////// void mv(int a[M][L], int b[L][N], int c[M][N]) { int i, j, k; for(i=0; i<M; i++) for(j=0; j<N; j++) { c[i][j]=0; for(k=0; k<L; k++) c[i][j]+=a[i][k]*b[k][j]; } } /////////////////////////////////////////////////////////////////////////////// void main() { int a[M][L]={{1,2,3,4},{1,1,1,1}}; int b[L][N]={{1,1,1},{1,2,1},{2,2,1},{2,3,1}}, c[M][N]; int i, j; mv(a,b,c); for(i=0; i<M; i++) { for(j=0; j<N; j++) printf("%4d", c[i][j]); printf("\n"); } } 3、矩阵传置 例:有二维数组 a[5,5],要对它实现转置,可用下面两种方式,程序代码如下: #include<stdio.h> #define N 3 /////////////////////////////////////////////////////////////////////////////// void ch1(int a[N][N])

{ int i, j, t; for(i=0; i<N; i++) for(j=i+1; j<N; j++) { t=a[i][j]; a[i][j]=a[j][i]; a[j][i]=t; } } /////////////////////////////////////////////////////////////////////////////// void ch2(int a[N][N]) { int i, j, t; for(i=1; i<N; i++) for(j= 0; j<i; j++) { t=a[i][j]; a[i][j]=a[j][i]; a[j][i]=t; } } /////////////////////////////////////////////////////////////////////////////// void main() { int a[N][N]={{1,2,3},{4,5,6},{7,8,9}}, i, j; ch1(a); /*或 ch2(a);*/ for(i=0; i<N; i++) { for(j=0; j<N; j++) printf("%2d", a[i][j]); printf("\n"); } } 4、求二维数组中最小元素及其所在的行和列 基本思路同一维数组,可用下面程序段实现(以二维数组 a[3][4]为例) :变量 max 中存放最 大值,row,column 存放最大值所在行列号。 程序代码如下: #include<stdio.h> #define N 4 #define M 3

/////////////////////////////////////////////////////////////////////////////// void min(int a[M][N]) { int min, row, column, i, j; min=a[0][0]; row=0; column=0; for(i=0; i<M; i++) for(j=0; j<N; j++) if(a[i][j]<min) { min=a[i][j]; row=i; column=j; } printf("Min=%d\nAt Row%d,Column%d\n", min, row, column); } /////////////////////////////////////////////////////////////////////////////// void main() { int a[M][N]={{1,23,45,-5},{5,6,-7,6},{0,33,8,15}}; min(a); } 九、迭代法 算法思想:对于一个问题的求解 x,可由给定的一个初值 x0,根据某一迭代公式得到一个新 的值 x1,这个新值 x1 比初值 x0 更接近要求的值 x;再以新值作为初值,即:x1→x0,重新 按原来的方法求 x1,重复这一过和直到|x1-x0|<ε(某一给定的精度)。此时可将 x1 作为问题的 解。 例:用迭代法求某个数的平方根。已知求平方根的迭代公式为:xn+1=(1/2)*(xn+a/xn) 程序代码如下: #include<stdio.h> #include<math.h> /////////////////////////////////////////////////////////////////////////////// float fsqrt(float a) { float x0, x1; x1=a/2; do { x0=x1;

x1=(float)0.5*(x0+a/x0); }while(fabs(x1-x0)>0.00001); return(x1); } /////////////////////////////////////////////////////////////////////////////// void main() { float a; scanf("%f", &a); printf("genhao=%f\n", fsqrt(a)); } 十、数制转换(将一个十进制整数 m 转换成→r(2-16)进制字符串) 方法:将 m 不断除 r 取余数,直到商为零,以反序得到结果。下面写出一转换函数,参数 idec 为十进制数,ibase 为要转换成数的基(如二进制的基是 2,八进制的基是 8 等) ,函数 输出结果是字符串。 程序代码如下: char *trdec(int idec, int ibase) { char strdr[20], t; int i, idr, p=0; while(idec!=0) { idr=idec%ibase; if(idr>=10) strdr[p++]=idr-10+65; else strdr[p++]=idr+48; idec/=ibase; } for(i=0; i<p/2; i++) { t=strdr[i]; strdr[i]=strdr[p-i-1]; strdr[p-i-1]=t; } strdr[p]='\0'; return(strdr); } /////////////////////////////////////////////////////////////////////////////// void main()

{ int x, d; scanf("%d%d", &x, &d); printf("%s\n", trdec(x,d)); } 十一、字符串的一般处理 1、简单加密和解密 加密的思想是:将每个字母 C 加(或减)一序数 K,即用它后的第 K 个字母代替,变换式 公式:c=c+k。例如序数 k 为 5,这时 A→ F,a→f,B→G…当加序数后的字母超过 Z 或 z 则 c=c+k -26。 例如:You are good→ Dtz fwj ltti。 解密为加密的逆过程:将每个字母 C 减(或加)一序数 K,即 c=c-k。例如序数 k 为 5,这 时 Z→U,z→u,Y→T…当加序数后的字母小于 A 或 a 则 c=c-k +26。 程序代码如下(加密处理) : char *jiami(char stri[]) { int i=0; char strp[50], ia; while(stri[i]!='\0') { if(stri[i]>='A' && stri[i]<='Z') { ia=stri[i]+5; if (ia>'Z') ia-=26; } else if(stri[i]>='a' && stri[i]<='z') { ia=stri[i]+5; if (ia>'z') ia-=26; } else ia=stri[i]; strp[i++]=ia; } strp[i]='\0'; return(strp); } /////////////////////////////////////////////////////////////////////////////// void main() { char s[50];

gets(s); printf("%s\n", jiami(s)); } 2、统计文本单词的个数(输入一行字符,统计其中有多少个单词,单词之间用格分隔开) 算法思路: (1)从文本(字符串)的左边开始,取出一个字符,设逻辑量 word 表示所取字符是否是 单词内的字符,初值设为 0; (2)若所取字符不是"空格","逗号","分号"或"感叹号"等单词的分隔符,再判断 word 是 否为 1,若 word 不为 1 则表是新单词的开始,让单词数 num = num +1,让 word =1; (3)若所取字符是"空格","逗号","分号"或"感叹号"等单词的分隔符, 则表示字符不是 单词内字符,让 word=0; (4) 再依次取下一个字符,重得(2)(3)直到文本结束。 求字符串 string 中包含的单词数的程序代码如下: void main() { char c, string[80]; int i, num=0, word=0; gets(string); for(i=0; (c=string[i])!='\0'; i++) if(c==' ') word=0; else if(word==0) { word=1; num++; } printf("There are %d word in the line.\n",num); } 十二、穷举法 穷举法(又称"枚举法")的基本思想是:一一列举各种可能的情况,并判断哪一种可能是符 合要求的解,这是一种"在没有其它办法的情况的方法",是一种最"笨"的方法,然而对一些 无法用解析法求解的问题往往能奏效,通常采用循环来处理穷举问题。 例: 将一张面值为 100 元的人民币等值换成 100 张 5 元、1 元和 0.5 元的零钞,要求每种零 钞不少于 1 张,问有哪几种组合? 程序代码如下: void main() { int i, j, k; printf(" 5 元 1 元 5 角\n"); for(i=1; i<=20; i++) for(j=1; j<=100-i; j++) {

k=100-i-j; if(5*i+1*j+0.5*k==100) printf(" %3d %3d %3d\n", i, j, k); } } 十三、递归算法(用自身的结构来描述自身,称递归) VB 允许在一个 Sub 子过程和 Function 过程的定义内部调用自己, 即递归 Sub 子过程和递归 Function 函数。递归处理一般用栈来实现,每调用一次自身,把当前参数压栈,直到递归结 束条件;然后从栈中弹出当前参数,直到栈空。 递归条件: (1)递归结束条件及结束时的值; (2)能用递归形式表示,且递归向终止条件发展。 例:编 fac(n)=n!的递归函数。 程序代码如下: int fac(int n) { if(n==1) return(1); else return(n*fac(n-1)); } /////////////////////////////////////////////////////////////////////////////// void main() { int n; scanf("%d", &n); printf("%d!=%d\n", n, fac(n)); }


相关文章:
C语言程序设计的常用算法.pdf
C语言程序设计的常用算法 - C 语言程序设计的常用算法 算法(Algorith
C语言程序设计第3版算法与程序设计基础_图文.ppt
C语言程序设计第3版算法与程序设计基础_中职中专_职业教育_教育专区。C语言程序...共 32 页 第 25 页 1.3 几种常用算法介绍 1. 枚举法(穷举法)特点:算法...
C语言程序设计常用算法汇总.doc
C语言程序设计常用算法汇总_IT/计算机_专业资料。C程序设计的常用算法,了解基本算法的编写,对计算机二级考试有很大帮助 C 程序设计的常用算法算法(Algorithm) :计算机...
C语言常用算法程序汇总.txt
C语言常用算法程序汇总 - C程序设计的常用算法 算法(Algorithm):计
C语言程序设计第5章 算法_图文.ppt
C语言程序设计第5章 算法 - 第5讲 算法的基本概念与表示方法 程序的灵魂 教学目标 ? 算法的概念 ? 怎么样表示一个算法 ? 结构化程序设计方法的基本思想 ...
C语言常用算法设计.txt
C语言程序设计的常用算法... 16页 1下载券 几种基本的C语言算法设计...
C语言程序设计习题3.doc
C语言程序设计习题3 - 习题 3 参考解答 1.什么是算法?常用描述算法的工具有哪些? 解:所谓算法,就是计算机解决某一个问题的具体方法和步骤。常用描述算法的工具 ...
《C语言程序设计》教案(清华谭浩强).doc
C 语言程序设计思想的基本篇; 重点:①C 语言的主要特点; ②C 语言在 PC 机上的运行过程及上机操作过程; ③常用算法的应用 难点:无 一、C 语言概述 C 语言...
程序设计与算法语言 C语言(2 基础知识)_图文.pdf
程序设计算法语言 C语言(2 基础知识)_互联网_IT/计算机_专业资料。2 基础...基本格式控制符:%d, %c, %lf, %f, %s 11 2015/5/12 (2)赋值 double ...
C语言常用算法程序汇总.doc
C语言常用算法程序汇总 - C 程序设计的常用算法 算法(Algorithm)
C语言课件-算法与程序设计基础_图文.ppt
C语言课件-算法程序设计基础 - 此为大连理工大学朱鸣华教授C语言教学课件,讲
c语言程序设计 谭浩强第2章_算法_图文.ppt
c语言程序设计 谭浩强第2章_算法 - 第二章 ? 本章要点 ? 算法的概念 ? ? 算法的表示 结构化程序设计方法 ? 主要内容 2.1 算法的概念 2.2 简单算法举例...
c语言程序设计第三版谭浩强第二章算法_图文.ppt
c语言程序设计第三版谭浩强第二章算法 - c语言程序设计,谭浩强第三版 2005
C语言程序设计基础1.5 算法的表示.ppt
C语言程序设计基础1.5 算法的表示 - 能力目标: ?描述C语言语句类别和作用 ?在描述流程图符号的名称和所表示的操作 ?用流程图表示解决问题的算法 ?基本程序结构及...
C语言程序设计_图文.ppt
C语言程序设计概述 算法算法设计简介 数据描述与基本操作 选择结构程序设计 循环结构程序设计 数组与指针 函数与模块化程序设计方法 3 第一章 C语言程序设计基础 ...
C语言的六种常用算法.doc
C语言的六种常用算法_IT/计算机_专业资料。C语言的六种常用算法六...4、小结随机函数是程序设计中一道亮丽的风景。这个函数是非常有用的,她可能是...
2、C语言程序设计- 算法_图文.ppt
2、C语言程序设计- 算法 - 第二章 程序灵魂 算法 算法 张琴 C程序设计第二章 算法 主要内容 一、算法的概念 二、算法的表示 三、结构化程序设计...
数据结构各种排序算法的课程设计实验报告(c语言版).doc
数据结构各种排序算法的课程设计实验报告(c语言版) - 课程设计报告 课程名称: 设计题目: 系专组别: 业: 别: 数据结构 排序算法实现及比较 计算机信息工程学院 ...
C语言程序设计框图.ppt
3.2中的算法C语言程序设计电子教案 第3章 控制结构 3.1 程序结构框图 3.1.4 结构化程序设计结构化程序设计的基本思想是:任何程序都由顺序结构、 结构化程序...
C语言程序设计 清华大学课件 第2章 算法_图文.ppt
C程序设计(第三版) http://ccf.tsinghua.edu.cn 18 2.4 算法的表示可以用不同的方法表示算法,常用的有: 自然语言 传统流程图 结构化流程图 伪代码...