C语言常见算法

单击此处编辑母版样式,单击此处编辑幻灯片母版样式,第二层,第三层,第四层,第五层,*,一 素数、随机数、最大值和最小值,(1) 判断一个数是否为素数,素数：只能被1和它本身整除的数。,要判断一个正整数m是不是素数，,需要用大于1且小于它本身的正整数去除它，只要它能被其中的一个数整除,，就说明它,不是素数,。若所有的数都不能被它整除，说明它是素数。,例1：输出3100之间的所有素数,main(), int i,n,k=0;,for(n=3;n100;n+), for(i=2;in;i+),if(n%i= =0) break;,if(i= =n),printf(“%4d”,n);,k+;,if(k%10= =0) printf(“n”); ,(2) 随机数,函数,random(int num),用于产生0,num)区间的一个整数。,其包含在,“stdlib.h”,头文件中,为了使每一次运行都产生一组新的随机数，可以使用,randomize()函数,是每次均产生不同的随机数。其包含在头文件,“time.h”,中,(3) 最大值与最小值,我们需要,将最大值（或最小值）保存在一个变量中,（假设设变量名为max和min）,变量的初值,我们一般设为,数列中的第一个值,。,例2：产生20个50到200之间的随机整数，并求出其中的素数、最大值和最小值。,#include stdlib.h,#include time.h,main(), int a20,b20,max,min,k,i,j=0;,randomize();,for(i=0;i20;i+),ai=random(151)+50;,产生20个50,200,区间内的随机数,for(i=0;i20;i+),for(k=2;kai;k+),if(ai%k=0) break;,if(k=ai), bj=ai; j+; ,for(i=0;ij;i+),printf(%4d,bi);,printf(n);,从a数组中找出其中,的素数放在b数组中,输出b数组中的各个元素,max=a0; min=a0;,for(i=1;imax) max=ai;,if(aimin) min=ai; ,printf(max=%4d,min=%4dn,max,min);,求出a数组中的,最大值与最小值,二、求累加和的算法,1 循环条件,次数控制（加多少项n,20,100),用误差控制（直到某一项小于或大于一个数）,使用终止标记,2 循环体,求和,求每一项：从前一项求出后一项、单独求每一项,为下一项作准备,3 循环初值：,设为0、设为第一项,注意双重循环设初值的位置,4-16 有一分数序列,的前20项之和,main(), int i;,float,f1=1,f2=1,f3,s=0;,for (,i=1;i=1e-5,),x0=x;,f=(2*x0-4)*x0+3)*x0-6;,f1=(6*x0-8)*x0+3;,x=x0-f/f1;,printf(%10.8f n,x);,四、数字分离,有些题中经常,要求将一个数中的每一位数字或者其中的某些位数字输出，,就需要使用到数字分离技术。,如在,求解同构数等问题,时都需要使用到数字分离技术,例：给出一个不多于4位的正整数，要求：求出它是几位数，并且按逆序打印出各位数字,main(), int i,j,k=0;,scanf(%d,while(,i!=0,),printf(%4d,i%10,);,i=i/10;,k+;,printf(nk=%dn,k);,四、以特殊字符做为终止标志,例：统计从键盘输入字符的个数，以#结束。,#include stdio.h,main(), char c; int i;,c=getchar();,for(i=0; c!=#; i+),c=getchar();,printf(the number is:%d,i);,五、排序问题,常用的排序方法有四种：,顺序交换法、选择法、冒泡法、插入法,a.顺序排序法(n=10),指导思想,：,先设定a0中存放最小值，,然后用a0分别与其后的每一个数aj（j=1.9）进行比较，在比较过程中,如果发现有比a0小的数，,就将,a0与aj互换，,一遍扫描之后，a0就是10个数中最小的数，重复此算法，只是每次比较时，进行比较的数的范围向后移一个位置。,反复执行(n-1)次,上述操作,例1：将数组a中的10个数按照由大到小的顺序排好,(使用顺序交换法),#define N 10,main( ), int aN,i,j,k,t;,for(i=0;iN;i+),scanf(%d,for (i=0;iN-1;i+),for (j=i+1;jN;j+),if (ajai) t=aj; aj=ai; ai=t; ,for(i=0;iN;i+) printf(%5d,ai);,b.选择排序法,指导思想：,不急于交换，,先找出a0到a9中的最小数所在的位置k，,一遍扫描完之后，在把a0与ak进行交换，重复次算法9次。,例2：将数组a中的10个数按照由大到小的顺序排好,(使用选择法),#define N 10,main( ), int aN,i,j,k,t;,for(i=0;iN;i+),scanf(%d,for (i=0;iN-1;i+), k=i;,for(j=i+1;jN;j+),if(ajak) k=j;,t=ai; ai=ak; ak=t; ,for(i=0;iN;i+) printf(%5d,ai);,c.冒泡法,指导思想：,是,将相邻的两个数进行比较,，若前一个数比后一个数大，在交换两元素的内容，否则不交换。从而把最大的数放在最后位置。,#define N 10,main( ), int aN,i,j,k,t;,for(i=0;iN;i+),scanf(%d,for (i=0;iN-1;i+),for(j=0;jN-i-1;j+),if(aj+1aj) t=aj; aj=aj+1; aj+1=t; ,for(i=0;iN;i+) printf(%5d,ai);,例：有N个数已按由小到大的顺序排好，要求输入一个数，把它插入到原有序列中，而且仍然保持有序。,输入数据时，使其数据排列仍然有序,解题思想：,先找到待插入的位置，然后将从该位置起到数组的最后位置的所有元素均向后移一个位置。,main(), int a100,i,j,n,x;,scanf(%d,/* 确定数组元素中的个数 */,for (i=0;in;i+),scanf(%d,/* 给数组的每个元素赋初值 */,scanf(%d,/* 输入待插入的数据 */,for (i=0;ix) break;,/* 找到待插入的位置i */,for (j=n-1;j=i;j-),aj+1=aj;,/* 从ai到an-1之间的数组军后移一位*/,ai=x;,/*把数据x放到ai位置处*/,for (i=0;i=n;i+),printf(%5d,ai);,printf(n);,main( ), int x50,y,n,i;,scanf(%d,for(i=0;in;i+), scanf(%d,printf(%5d,xi);,printf(n);,for(i=0;i=(n-1)/2;i+), y=xi;,xi=xn-1-i;,xn-1-i=y; ,for(i=0;in;i+),printf(%5d,xi);,printf(n);,方法1：,例6将n(n=50)个整数按逆序重放在数组中。,main( ),int x100,n,m,i,j;,scanf(%d,for(i=0;in;i+) scanf(%d,for(j=1;j=n;j+),m=x0;,for(i=0;in-j;i+),xi=xi+1;,xn-j=m;,for(i=0;in;i+) printf(%5d,xi);,printf(n);,方法,2,注意：求解水仙花数、完数、同构数、最大公约数和最小公倍数以及费波拉切数列等内容,水仙花数：,是一个三位数，其各位数字的立方和等于该数本身。如：153=1,3,+5,3,+3,3,完数：,一个数等于它的所有因子（不包括它本身）之和。如：6=1+2+3,同构数：,一个数等于它的平方数的右端。如5的平方是25,最大公约数：,使用辗转相除法进行求解,图形 1： （法一）,main(), int i,j;,for (i=1;i=5;i+), for (j=1;j=5;j+),printf (“ *”);,printf(“n”);,* * * * *,* * * * *,* * * * *,* * * * *,* * * * *,六、简单图形打印,图形 1：（法二）,main(), int i;,for (i=1;i=5;i+),printf (“ * * * * *n”);,* * * * *,* * * * *,* * * * *,* * * * *,* * * * *,图形 2：（法一）,main(), int i,j;,for (i=1;i=5;i+), for ( j=1;ji;j+),printf ( “ “);,for ( j=1;j=5;j+),printf (“ *”);,printf(“n”);,* * * * *,* * * * *,* * * * *,* * * * *,* * * * *,图形 2：（法二）,main(), int i,j;,for (i=1;i=5;i+), for ( j=1;ji;j+),printf ( “ “);,printf (“ * * * * *n”);,* * * * *,* * * * *,* * * * *,* * * * *,* * * * *,图形 3：,main(), int i,j;,for (i=1;i=5;i+), for (j=1;j=5-i:j+),printf ( “ “);,for (j=1;j=5;j+),printf (“ *”);,printf(“n”);,* * * * *,* * * * *,* * * * *,* * * * *,* * * * *,图形 4 ：,main(), int i,j;,for (i=1;i=5;i+), for (j=1;j=i;j+),printf (“ *”);,printf(“n”);,*,* *,* * *,* * * *,* * * * *,图形 5：,main(), int i,j;,for (i=1;i=5;i+), for (j=1;j=5-i;j+),printf (“ “);,for (j=1;j=i;j+),printf (“*”);,printf(“n”);,*,* *,* * *,* * * *,* * * * *,*,* * *,* * * * *,* * * * * * *,* * * * *,* * *,*,图形6,：,main(), int i,j,k;,for(i=1;i=4;i+), for(j=1;,j=4-i,;j+),printf( );,for(k=1;,k=2*i-1,;k+),printf(*);,printf(n);,for(i=1;i=3;i+), for(j=1;,j=i;,j+),printf( );,for(k=1;,k=0;i-),if(stri=c), for(k=i;strk!=0;k+),strk=strk+1;,strk=0; ,puts(str);,练习2、编写程序，比较两个字符串的大小。(不能使用strcmp()函数),比较规则：逐个字符进行比较，直到有两个字符不等或有一个字符串结束为止。,main(),char s180,s280;,int i,k;,gets(s1); gets(s2); i=0;,while(s1i!=0&s2i!=0),if(s1i!=s2i) break;,else i+;,k=s1i-s2i;,if(k0) printf(s1s2n);,else if(k0) printf(s10) printf(s1s2n);,else if(k0) printf(s1s2n);,else printf(s1=s2n);,练习3、判断一字符串是否为另一个字符串的子串，若是则返回第一出现的起始位置，否则则返回0,main(), static char s120=I love China!;,static char s220=love;,int i,j,k,m=0;,for(i=0;,s1i!=0;,i+),if(s1i= =s20),for(j=1,k=i+1;s2j!=0;j+,k+),if(s1k!=s2j) break;,if(s2j=0),m=i; break;,printf(station is %dn,m);,八、对矩阵的操作,注意：,矩阵的主对角线、副对角线的概念,如何实现矩阵转置、求解矩阵中指定的元素之和等问题,（如求解右上三角、左下三角的元素之和）,打印杨辉三角形（用一维和二维分别实现）,习题7.6:输出杨辉三角形（10行）。,void,main(), int i,j,a1111;,for(i=0;i11;i+),ai1=1;aii=1;,for(i=3;i11;i+),for(j=2;j=i-1;j+),aij=ai-1j-1+ai-1j;,for(i=1;i11;i+),for(j=1;j=i;j+),printf(%6d ,aij);,printf(n); ,printf(n);,1,1 1,1 2 1,1 3 3 1,1 4 6 4 1,1 5 10 10 5 1,a11,1,a21,1+,a22,1,a31,1+,a32,2+,a33,1,a41,1+,a42,3+,a43,3+,a44,1,a51,1+,a52,4+,a53,6+,a54,4+,a55,1,aij=ai-1j+ai-1j-1,0行、0列不用,第一列、对角线为1,从第三行开始计算各元素值,输出各元素值,main(), int a1010;,int i,j;,for (i=0;i10;i+), ai0=1;aii=1;,for (j=1;ji;j+),aij=ai-1j-1+ai-1j;,for(i=0;i10;i+), for(j=0;j=i;j+),printf(%6d,aij);,printf(n);,for (i=0;i10;i+),for (j=0;j35-3*i;j+),printf( );,for (j=0;j=i;j+),printf(%6d,aij); printf(n);,