《C语言常见算法》PPT课件.ppt

一 素数、随机数、最大值和最小值 (1) 判断一个数是否为素数 素数：只能被1和它本身整除的数。 要判断一个正整数m是不是素数，需 要用大于1且小于它本身的正整数去除它 ，只要它能被其中的一个数整除，就说明 它不是素数。若所有的数都不能被它整除 ，说明它是素数。 例1：输出3100之间的所有素数 main() int i,n,k=0; for(n=3;nmax) max=ai; if(ai=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=19）进行比 较，在比较过程中如果发现有比a0小的数，就 将a0与aj互换，一遍扫描之后，a0就是10 个数中最小的数，重复此算法，只是每次比较 时，进行比较的数的范围向后移一个位置。反 复执行(n-1)次上述操作 例1：将数组a中的10个数按照由大到小的 顺序排好(使用顺序交换法) #define N 10 main( ) int aN,i,j,k,t; 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=0;i -) if(stri=c) for(k=i;strk!=0;k+) strk=strk+1; strk=0; puts(str); 练习2、编写程序，比较两个字符串的 大小。(不能使用strcmp()函数) z比较规则：逐个字符进行比较，直到有 两个字符不等或有一个字符串结束为止 。 main() char s180,s280; int i,k; gets(s1); gets(s2); i=0; while(s1i!=0 else i+; k=s1i-s2i; if(k0) printf(“s1s2n“); else if(k0) 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;ai1=1;aii=1; for(ifor(i=3;i11;i+)=3;i11;i+) for(jfor(j=2;j=i-1;j+)=2;j=i-1;j+) aijaij=ai-1j-1+ai-1j;=ai-1j-1+ai-1j; for(ifor(i=1;i11;i+)=1;i11;i+) for(jfor(j=1;j=1;j=i;ji;j+)+) printf(“%6d “, printf(“%6d “,aijaij);); printf(“nprintf(“n“); “); printf(“n“); 1 1 1 11 1 1 2 11 2 1 1 3 3 11 3 3 1 1 4 6 4 11 4 6 4 1 1 5 10 10 5 11 5 10 10 5 1 a111 a211+a221 a311+a322+a331 a411+a423+a433+a441 a511+a524+a536+a544+a55 1 aijaij=ai-1j+ai-1j-1=ai-1j+ai-1j-1 0 0行、行、0 0列不用列不用 第一列、对第一列、对 角线为角线为1 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+) prin