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

一一素数、随机数、最大值和最小值素数、随机数、最大值和最小值(1)判断一个数是否为素数判断一个数是否为素数素数：只能被素数：只能被1和它本身整除的数。和它本身整除的数。要判断一个正整数要判断一个正整数m是不是素数，是不是素数，需需要用大于要用大于1且小于它本身的正整数去除它，且小于它本身的正整数去除它，只要它能被其中的一个数整除只要它能被其中的一个数整除，就说明它，就说明它不是素数不是素数。若所有的数都不能被它整除，。若所有的数都不能被它整除，说明它是素数。说明它是素数。例例1：输出：输出3100之间的所有素数之间的所有素数main()inti,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(intnum)用于产生用于产生0,num)区区间的一个整数。间的一个整数。其包含在其包含在“”头文件中头文件中为了使每一次运行都产生一组新的随机数，为了使每一次运行都产生一组新的随机数，可以使用可以使用randomize()函数函数是每次均产生不同的是每次均产生不同的随机数。其包含在头文件随机数。其包含在头文件“”中中(3)最大值与最小值最大值与最小值我们需要我们需要将最大值（或最小值）保存在一将最大值（或最小值）保存在一个变量中个变量中（假设设变量名为（假设设变量名为max和和min）,变量变量的初值的初值我们一般设为我们一般设为数列中的第一个值数列中的第一个值。例例2：产生：产生20个个50到到200之间的随机整数，并求之间的随机整数，并求出其中的素数、最大值和最小值。出其中的素数、最大值和最小值。#include#includetime.hmain()inta20,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数组中的数组中的最大值与最小值最大值与最小值二、求累加和的算法二、求累加和的算法二、求累加和的算法二、求累加和的算法l1循环条件循环条件次数控制（加多少项次数控制（加多少项n,20,100)用误差控制（直到某一项小于或大于一个数）用误差控制（直到某一项小于或大于一个数）使用终止标记使用终止标记l2循环体循环体求和求和求每一项：从前一项求出后一项、单独求每一求每一项：从前一项求出后一项、单独求每一项项为下一项作准备为下一项作准备l3循环初值：循环初值：设为设为0、设为第一项、设为第一项注意双重循环设初值的位置注意双重循环设初值的位置4-16 4-16 有一分数序列有一分数序列有一分数序列有一分数序列 的前的前的前的前2020项项项项之和之和之和之和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.8fn,x);四、数字分离四、数字分离 有些题中经常有些题中经常要求将一个数中的每一位要求将一个数中的每一位数字或者其中的某些位数字输出，数字或者其中的某些位数字输出，就需要使就需要使用到数字分离技术。用到数字分离技术。如在如在求解同构数等问题求解同构数等问题时都需要使用到时都需要使用到数字分离技术数字分离技术例：给出一个不多于例：给出一个不多于4位的正整数，要求：求出位的正整数，要求：求出它是几位数，并且按逆序打印出各位数字它是几位数，并且按逆序打印出各位数字main()inti,j,k=0;scanf(%d,&i);while(i!=0)printf(%4d,i%10);i=i/10;k+;printf(nk=%dn,k);四、以特殊字符做为终止标志四、以特殊字符做为终止标志例：统计从键盘输入字符的个数，以例：统计从键盘输入字符的个数，以#结束。结束。#includemain()charc;inti;c=getchar();for(i=0;c!=#;i+)c=getchar();printf(thenumberis:%d,i);五、排序问题五、排序问题常用的排序方法有四种：常用的排序方法有四种：顺序交换法、选择法、冒泡法、插入法顺序交换法、选择法、冒泡法、插入法a.顺序排序法顺序排序法(n=10)指导思想指导思想：先设定先设定a0中存放最小值，中存放最小值，然后用然后用a0分别与其后的每一个数分别与其后的每一个数aj（j=1.9）进行比）进行比较，在比较过程中较，在比较过程中如果发现有比如果发现有比a0小的数，小的数，就就将将a0与与aj互换，互换，一遍扫描之后，一遍扫描之后，a0就是就是10个数中最小的数，重复此算法，只是每次比较个数中最小的数，重复此算法，只是每次比较时，进行比较的数的范围向后移一个位置。时，进行比较的数的范围向后移一个位置。反反复执行复执行(n-1)次次上述操作上述操作例例1：将数组：将数组a中的中的10个数按照由大到小的个数按照由大到小的顺序排好顺序排好(使用顺序交换法使用顺序交换法)#defineN10main()intaN,i,j,k,t;for(i=0;iN;i+)scanf(%d,&ai);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个数按照由大到小的个数按照由大到小的顺序排好顺序排好(使用选择法使用选择法)#defineN10main()intaN,i,j,k,t;for(i=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);c.冒泡法冒泡法指导思想：指导思想：是是将相邻的两个数进行比较将相邻的两个数进行比较，若前，若前一个数比后一个数大，在交换两元素的内容，一个数比后一个数大，在交换两元素的内容，否则不交换。从而把最大的数放在最后位置。否则不交换。从而把最大的数放在最后位置。#defineN10main()intaN,i,j,k,t;for(i=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);例：有例：有N个数已按由小到大的顺序排好，个数已按由小到大的顺序排好，要求输入一个数，把它插入到原有序列要求输入一个数，把它插入到原有序列中，而且仍然保持有序。中，而且仍然保持有序。输入数据时，使其数据排列仍然有序输入数据时，使其数据排列仍然有序解题思想：解题思想：先找到待插入的位置，然后将从先找到待插入的位置，然后将从该位置起到数组的最后位置的所有元素该位置起到数组的最后位置的所有元素均向后移一个位置。均向后移一个位置。main()inta100,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);printf(n);main()intx50,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)个整数按逆序重放在数组中。个整数按逆序重放在数组中。main()intx100,n,m,i,j;scanf(%d,&n);for(i=0;in;i+)scanf(%d,&xi);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=13+53+33完数：完数：一个数等于它的所有因子（不包括它本一个数等于它的所有因子（不包括它本身）之和。如：身）之和。如：6=1+2+3同构数：同构数：一个数等于它的平方数的右端。如一个数等于它的平方数的右端。如5的的平方是平方是25最大公约数：最大公约数：使用辗转相除法进行求解使用辗转相除法进行求解图形图形1：（法一）（法一）main()inti,j;for(i=1;i=5;i+)for(j=1;j=5;j+)printf(“*”);printf(“n”);*六、简单图形打印六、简单图形打印图形图形1：（法二）：（法二）main()inti;for(i=1;i=5;i+)printf(“*n”);*图形图形2：（法一）：（法一）main()inti,j;for(i=1;i=5;i+)for(j=1;ji;j+)printf(“);for(j=1;j=5;j+)printf(“*”);printf(“n”);*图形图形2：（法二）：（法二）main()inti,j;for(i=1;i=5;i+)for(j=1;ji;j+)printf(“);printf(“*n”);*图形图形3：main()inti,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()inti,j;for(i=1;i=5;i+)for(j=1;j=i;j+)printf(“*”);printf(“n”);*图形图形5：main()inti,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()inti,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()函数函数)z比较规则：逐个字符进行比较，直到有比较规则：逐个字符进行比较，直到有两个字符不等或有一个字符串结束为止。两个字符不等或有一个字符串结束为止。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、判断一字符串是否为另一个字符串的子、判断一字符串是否为另一个字符串的子串，若是则返回第一出现的起始位置，否则则串，若是则返回第一出现的起始位置，否则则返回返回0main()staticchars120=IloveChina!;staticchars220=love;inti,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(stationis%dn,m);八、对矩阵的操作八、对矩阵的操作注意：注意：矩阵的主对角线、副对角线的概念矩阵的主对角线、副对角线的概念如何实现矩阵转置、求解矩阵中指定的元如何实现矩阵转置、求解矩阵中指定的元素之和等问题素之和等问题（如求解右上三角、左下三角的（如求解右上三角、左下三角的元素之和）元素之和）打印杨辉三角形（用一维和二维分别实现）打印杨辉三角形（用一维和二维分别实现）习题习题习题习题7.6:7.6:输出杨辉三角形（输出杨辉三角形（输出杨辉三角形（输出杨辉三角形（1010行）。行）。行）。行）。voidmain()inti,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(n);1 111111211211331133114641146411510105115101051a111a211+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从第三行开始计从第三行开始计从第三行开始计从第三行开始计算各元素值算各元素值算各元素值算各元素值输出各元素值输出各元素值输出各元素值输出各元素值main()inta1010;inti,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);