C语言常见算法.pptx

《C语言常见算法.pptx》由会员分享，可在线阅读，更多相关《C语言常见算法.pptx（41页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、(2)随机数随机数 函数函数random(int num)用于产生用于产生0,num)区区间的一个整数。间的一个整数。其包含在其包含在“stdlib.h”头文件中头文件中 为了使每一次运行都产生一组新的随机数，为了使每一次运行都产生一组新的随机数，可以使用可以使用randomize()函数函数是每次均产生不同的是每次均产生不同的随机数。其包含在头文件随机数。其包含在头文件“time.h”中中(3)最大值与最小值最大值与最小值 我们需要我们需要将最大值（或最小值）保存在一将最大值（或最小值）保存在一个变量中个变量中（假设设变量名为（假设设变量名为max和和min）,变量的变量的初值初值我们一般设

2、为我们一般设为数列中的第一个值数列中的第一个值。第1页/共41页例例2：产生：产生20个个50到到200之间的随机整数，并求之间的随机整数，并求出其中的素数、最大值和最小值。出其中的素数、最大值和最小值。#include stdlib.h#include time.hmain()int a20,b20,max,min,k,i,j=0;randomize();for(i=0;i20;i+)ai=random(151)+50;产生20个50,200区间内的随机数第2页/共41页 for(i=0;i20;i+)for(k=2;kai;k+)if(ai%k=0)break;if(k=ai)bj=ai;

3、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数组中的最大值与最小值第3页/共41页二、求累加和的算法1 循环条件 次数控制（加多少项n,20,100)用误差控制（直到某一项小于或大于一个数）使用终止标记2 循环体求和求每一项：从前一项求出后一项、单独求每一项为下一项作准备3 循环初值：设为0、设为第一项 注意双重循环设初值的位

4、置第4页/共41页4-16 有一分数序列 的前20项之和main()main()int i;int i;float float f1=1,f2=1,f3,s=0;f1=1,f2=1,f3,s=0;for(for(i=1;i=20;i+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);第8页/共41页四、数字分离四、数字分离 有些题中经常有些题中经常要求将一个数中的每一位要求将一个数中的每一位数字或者其中的某些位数字输出，数字或者其中的某些位数字输出，就需要使就需要使用到数字分离

5、技术。用到数字分离技术。如在如在求解同构数等问题求解同构数等问题时都需要使用到时都需要使用到数字分离技术数字分离技术第9页/共41页例：给出一个不多于例：给出一个不多于4位的正整数，要求：求出位的正整数，要求：求出它是几位数，并且按逆序打印出各位数字它是几位数，并且按逆序打印出各位数字 main()int i,j,k=0;scanf(%d,&i);while(i!=0)printf(%4d,i%10);i=i/10;k+;printf(nk=%dn,k);第10页/共41页四、以特殊字符做为终止标志四、以特殊字符做为终止标志例：统计从键盘输入字符的个数，以例：统计从键盘输入字符的个数，以#结束

6、。结束。#include stdio.hmain()char c;int i;c=getchar();for(i=0;c!=#;i+)c=getchar();printf(the number is:%d,i);第11页/共41页五、排序问题五、排序问题常用的排序方法有四种：常用的排序方法有四种：顺序交换法、选择法、冒泡法、插入法顺序交换法、选择法、冒泡法、插入法a.顺序排序法顺序排序法(n=10)指导思想指导思想：先设定先设定a0中存放最小值，中存放最小值，然后用然后用a0分别与其后的每一个数分别与其后的每一个数aj（j=1.9）进行比）进行比较，在比较过程中较，在比较过程中如果发现有比如果

7、发现有比a0小的数，小的数，就就将将a0与与aj互换，互换，一遍扫描之后，一遍扫描之后，a0就是就是10个数中最小的数，重复此算法，只是每次比较个数中最小的数，重复此算法，只是每次比较时，进行比较的数的范围向后移一个位置。时，进行比较的数的范围向后移一个位置。反反复执行复执行(n-1)次次上述操作上述操作第12页/共41页例例1：将数组：将数组a中的中的10个数按照由大到小的个数按照由大到小的顺序排好顺序排好(使用顺序交换法使用顺序交换法)#define N 10main()int aN,i,j,k,t;for(i=0;iN;i+)scanf(%d,&ai);for(i=0;iN-1;i+)f

8、or(j=i+1;jN;j+)if(ajai)t=aj;aj=ai;ai=t;for(i=0;iN;i+)printf(%5d,ai);第13页/共41页b.选择排序法选择排序法 指导思想：指导思想：不急于交换，不急于交换，先找出先找出a0到到a9中的最小数所在的位置中的最小数所在的位置k，一遍扫描完之后，一遍扫描完之后，在把在把a0与与ak进行交换，重复次算法进行交换，重复次算法9次。次。例例2：将数组：将数组a中的中的10个数按照由大到小的个数按照由大到小的顺序排好顺序排好(使用选择法使用选择法)第14页/共41页#define N 10main()int aN,i,j,k,t;for(i

9、=0;iN;i+)scanf(%d,&ai);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);第15页/共41页c.冒泡法冒泡法指导思想：指导思想：是是将相邻的两个数进行比较将相邻的两个数进行比较，若前，若前一个数比后一个数大，在交换两元素的内容，一个数比后一个数大，在交换两元素的内容，否则不交换。从而把最大的数放在最后位置。否则不交换。从而把最大的数放在最后位置。第16页/共41页#define N 10main()int aN,i,j,k,t;for(i

10、=0;iN;i+)scanf(%d,&ai);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);第17页/共41页例：有例：有N个数已按由小到大的顺序排好，个数已按由小到大的顺序排好，要求输入一个数，把它插入到原有序列要求输入一个数，把它插入到原有序列中，而且仍然保持有序。中，而且仍然保持有序。输入数据时，使其数据排列仍然有序输入数据时，使其数据排列仍然有序解题思想：解题思想：先找到待插入的位置，然后将从先找到待插入的位置，然后将从该位置起到数组的最后位置的所

11、有元素该位置起到数组的最后位置的所有元素均向后移一个位置。均向后移一个位置。第18页/共41页 main()int a100,i,j,n,x;scanf(%d,&n);/*确定数组元素中的个数 */for(i=0;in;i+)scanf(%d,&ai);/*给数组的每个元素赋初值*/scanf(%d,&x);/*输入待插入的数据 */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);prin

12、tf(n);第19页/共41页main()int x50,y,n,i;scanf(%d,&n);for(i=0;in;i+)scanf(%d,&xi);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)个整数按逆序重放在数组中。个整数按逆序重放在数组中。第20页/共41页main()int x100,n,m,i,j;scanf(%d,&n);for(i=0;in;i+)scanf(%d,&xi

13、);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第21页/共41页注意：求解水仙花数、完数、同构数、最大公注意：求解水仙花数、完数、同构数、最大公约数和最小公倍数以及费波拉切数列等内容约数和最小公倍数以及费波拉切数列等内容水仙花数：水仙花数：是一个三位数，其各位数字的立方是一个三位数，其各位数字的立方和等于该数本身。如：和等于该数本身。如：153=13+53+33完数：完数：一个数等于它的所有因子（不包括它本一个数等于它的所有因子（不包括它本身）之和

14、。如：身）之和。如：6=1+2+3同构数：同构数：一个数等于它的平方数的右端。如一个数等于它的平方数的右端。如5的的平方是平方是25最大公约数：最大公约数：使用辗转相除法进行求解使用辗转相除法进行求解第22页/共41页图形图形 1：（法一）（法一）main()int i,j;for(i=1;i=5;i+)for(j=1;j=5;j+)printf(“*”);printf(“n”);*六、简单图形打印六、简单图形打印第23页/共41页图形图形 1：（：（法二）法二）main()int i;for(i=1;i=5;i+)printf(“*n”);*第24页/共41页图形图形 2：（法一）：（法一）

15、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”);*第25页/共41页图形图形 2：（法二）：（法二）main()int i,j;for(i=1;i=5;i+)for(j=1;ji;j+)printf(“);printf(“*n”);*第26页/共41页图形图形 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”);*第27

16、页/共41页图形图形 4：main()int i,j;for(i=1;i=5;i+)for(j=1;j=i;j+)printf(“*”);printf(“n”);*第28页/共41页图形图形 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”);*第29页/共41页 *图形图形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(*);pr

17、intf(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);第33页/共41页练习2、编写程序，比较两个字符串的大小。(不能使用strcmp()函数)z比较规则：逐个字符进行比较，直到有两个字符不等或有一个字符串结束为止。第34页/共41页main()char s180,s280;int i,k;gets(s1);gets(s2);i=0;while(s1i!=0&s2i!=0)if(s1i!=s2i)break;e

18、lse i+;k=s1i-s2i;if(k0)printf(s1s2n);else if(k0)printf(s10)printf(s1s2n);else if(k0)printf(s1s2n);else printf(s1=s2n);第36页/共41页练习练习3、判断一字符串是否为另一个字符串的子、判断一字符串是否为另一个字符串的子串，若是则返回第一出现的起始位置，否则则串，若是则返回第一出现的起始位置，否则则返回返回0main()static char s120=I love China!;static char s220=love;int i,j,k,m=0;for(i=0;s1i!=0

19、;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);第37页/共41页八、对矩阵的操作八、对矩阵的操作注意：注意：矩阵的主对角线、副对角线的概念矩阵的主对角线、副对角线的概念 如何实现矩阵转置、求解矩阵中指定的元如何实现矩阵转置、求解矩阵中指定的元素之和等问题素之和等问题（如求解右上三角、左下三角的（如求解右上三角、左下三角的元素之和）元素之和）打印杨辉三角形（用一维和二维分别实现）打印杨辉三角形（用一维和二维分别实现）第38页/共41页习题

20、7.6:输出杨辉三角形（10行）。void main()int i,j,a1111;for(i=0;i11;i+)ai1=1;aii=1;ai1=1;aii=1;for(i=3;i11;i+)for(i=3;i11;i+)for(j=2;j=i-1;j+)for(j=2;j=i-1;j+)aij=ai-1j-1+ai-1j;aij=ai-1j-1+ai-1j;for(i=1;i11;i+)for(i=1;i11;i+)for(j=1;j=i;j+)for(j=1;j=i;j+)printf(%6d,aij);printf(%6d,aij);printf(n);printf(n);printf(

21、n);1 11 1 1 11 2 11 2 11 3 3 11 3 3 11 4 6 4 11 4 6 4 11 5 10 10 5 11 5 10 10 5 1 a111a211+a221a311+a322+a331a411+a423+a433+a441a511+a524+a536+a544+a551 aij=ai-1j+ai-1j-1aij=ai-1j+ai-1j-10 0行、行、0 0列不用列不用第一列、对第一列、对角线为角线为1 1从第三行开始计从第三行开始计算各元素值算各元素值输出各元素值输出各元素值第39页/共41页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);第40页/共41页感谢您的欣赏！第41页/共41页