算法语言与数据结构第4章.pptx

算法算法语言言与数与数据据结构构信息信息与与物流管理系物流管理系王健王健西安财经学院管理学院西安财经学院管理学院西安财经学院管理学院西安财经学院管理学院信息信息与与物流管理系物流管理系第四章选择、排队问题的解题思路 与 数据组织信息信息与与物流管理系物流管理系中秋佳节，有贵客来到草原，主人要从羊群中选一只肥羊宴中秋佳节，有贵客来到草原，主人要从羊群中选一只肥羊宴请宾客，当然要选最重者。这样就要记录每只羊的重量，如果有成千请宾客，当然要选最重者。这样就要记录每只羊的重量，如果有成千上万只羊，不可能用一般变量来记录。可以用带有下标的变量，也就上万只羊，不可能用一般变量来记录。可以用带有下标的变量，也就是这里要讲的是这里要讲的数组数组。问题：哪只羊最重？问题：哪只羊最重？我们先看例子：用键盘输入我们先看例子：用键盘输入10只羊的重量存放到只羊的重量存放到一个名为一个名为sheep的数组中的数组中信息信息与与物流管理系物流管理系/*/*/*/*程序名：程序名：程序名：程序名：4_1.c4_1.c（数组示例）（数组示例）（数组示例）（数组示例）*/*/*作作作作 者：者：者：者：wuwh *wuwh */*/*编制时间：编制时间：编制时间：编制时间：20022002年年年年9 9月月月月2020日日日日 */*/*主要功能：找出最重的羊主要功能：找出最重的羊主要功能：找出最重的羊主要功能：找出最重的羊 */*/*#include#include/预编译命令预编译命令预编译命令预编译命令void main()void main()/主函数主函数主函数主函数 float sheep10;float sheep10;/数组，有数组，有数组，有数组，有1010个浮点类型元素，个浮点类型元素，个浮点类型元素，个浮点类型元素，/用于存用于存用于存用于存1010只羊每一只的重量只羊每一只的重量只羊每一只的重量只羊每一只的重量 for(i=0;i10;1+)sheepi=0;/for(i=0;i10;1+)sheepi=0;/初始化数组元素为初始化数组元素为初始化数组元素为初始化数组元素为0 0float bigsheep=0.0f;float bigsheep=0.0f;/浮点类型变量，存放最肥羊的重量浮点类型变量，存放最肥羊的重量浮点类型变量，存放最肥羊的重量浮点类型变量，存放最肥羊的重量int bigsheepNo=0;int bigsheepNo=0;/整型变量，整型变量，整型变量，整型变量，i i 用于计数循环，用于计数循环，用于计数循环，用于计数循环，/bigsheepNo/bigsheepNo用于记录最肥羊的号用于记录最肥羊的号用于记录最肥羊的号用于记录最肥羊的号 信息信息与与物流管理系物流管理系for(i=0;i10;i=i+1)for(i=0;i10;i=i+1)/计数循环计数循环计数循环计数循环 /循环，开始循环，开始循环，开始循环，开始printf(printf(请输入羊的重量请输入羊的重量请输入羊的重量请输入羊的重量);/);/提示用提示用提示用提示用scanf(“%f”,&sheepi);scanf(“%f”,&sheepi);/输入第输入第输入第输入第i i只羊的重量只羊的重量只羊的重量只羊的重量if(bigsheep sheepi)if(bigsheep sheepi)/如果第如果第如果第如果第i i只羊比当前最肥羊大只羊比当前最肥羊大只羊比当前最肥羊大只羊比当前最肥羊大 bigsheep=sheepi;bigsheep=sheepi;/让第让第让第让第i i只羊为当前最肥羊只羊为当前最肥羊只羊为当前最肥羊只羊为当前最肥羊bigsheepNo=i;bigsheepNo=i;/纪录第纪录第纪录第纪录第i i只羊的编号只羊的编号只羊的编号只羊的编号 /循环结束循环结束循环结束循环结束/输出最肥羊的重量输出最肥羊的重量输出最肥羊的重量输出最肥羊的重量 printfprintf(“最肥羊的重量为最肥羊的重量为最肥羊的重量为最肥羊的重量为%ft“,bigsheep);%ft“,bigsheep);/输出该羊的编号输出该羊的编号输出该羊的编号输出该羊的编号 printfprintf(“最肥羊的编号为最肥羊的编号为最肥羊的编号为最肥羊的编号为%dn“,bigsheep%dn“,bigsheepNoNo););信息信息与与物流管理系物流管理系程程 序序 框框 图图信息信息与与物流管理系物流管理系第4章 目录 4.14.1数组的概念数组的概念数组的概念数组的概念1 1 4.24.2 一维数组一维数组2 2 4.34.3 二维及多维数组二维及多维数组二维及多维数组二维及多维数组3 3 4.44.4 字符数组字符数组字符数组字符数组4 4 综合举例综合举例综合举例综合举例5 5信息信息与与物流管理系物流管理系数组是具有一定顺序关系的若干相同类型变量的集合体，组数组是具有一定顺序关系的若干相同类型变量的集合体，组数组是具有一定顺序关系的若干相同类型变量的集合体，组数组是具有一定顺序关系的若干相同类型变量的集合体，组成数组的变量称为该数组的元素成数组的变量称为该数组的元素成数组的变量称为该数组的元素成数组的变量称为该数组的元素 数组元素在内存中顺次存放，它们的地址是连续的数组元素在内存中顺次存放，它们的地址是连续的数组元素在内存中顺次存放，它们的地址是连续的数组元素在内存中顺次存放，它们的地址是连续的数组名字是数组首元素的内存地址数组名字是数组首元素的内存地址数组名字是数组首元素的内存地址数组名字是数组首元素的内存地址数组名是一个常量，不能被赋值数组名是一个常量，不能被赋值数组名是一个常量，不能被赋值数组名是一个常量，不能被赋值4.1.1数组的概念数组的概念4.1 数数组的概念的概念信息信息与与物流管理系物流管理系4.1.2数组的应用领域数组的应用领域数组的应用领域很广数组的应用领域很广 数组有一维，二维至更多维的数组，但对于大容量的计算，多维数组是数组有一维，二维至更多维的数组，但对于大容量的计算，多维数组是必需的，如力学计算，地基计算，空气动力学计算等，均要用到多维数组必需的，如力学计算，地基计算，空气动力学计算等，均要用到多维数组。4.1 数组的概念数组的概念信息信息与与物流管理系物流管理系 4.2.1 一维数组的定义与引用一维数组的定义与引用一维数组的定义一维数组的定义一维数组的定义一维数组的定义类类型型型型说说明符明符明符明符 数数数数组组名名名名 常量表达式常量表达式常量表达式常量表达式 ；可以是常量和符号常量，不能用可以是常量和符号常量，不能用可以是常量和符号常量，不能用可以是常量和符号常量，不能用变变量。量。量。量。例如：例如：例如：例如：int a10 int a10 表示表示表示表示 a a 为为整型数整型数整型数整型数组组，有，有，有，有1010个元素：个元素：个元素：个元素：a0.a9a0.a9引用引用引用引用 必必必必须须先定先定先定先定义义，后使用。，后使用。，后使用。，后使用。只能逐个引用数只能逐个引用数只能逐个引用数只能逐个引用数组组元素，而不能一次引用整个数元素，而不能一次引用整个数元素，而不能一次引用整个数元素，而不能一次引用整个数组组例如：例如：例如：例如：a0=a5+a7-a2*3a0=a5+a7-a2*34.2 一维数组一维数组信息信息与与物流管理系物流管理系4.2.2 定定义数数组的注意事的注意事项 不能用变量定义数组大小不能用变量定义数组大小不能用变量定义数组大小不能用变量定义数组大小如如如如 int n;int n;scanf(“%d”,&n);n scanf(“%d”,&n);n是变量是变量是变量是变量 int an;int an;数组中的数组中的数组中的数组中的n n是变量是变量是变量是变量4.2 一维数组一维数组信息信息与与物流管理系物流管理系 4.2.3 一一维数数组的初始化的初始化可以在编译阶段使数组得到初值：可以在编译阶段使数组得到初值：可以在编译阶段使数组得到初值：可以在编译阶段使数组得到初值：在定在定在定在定义义数数数数组时对组时对数数数数组组元素元素元素元素赋赋以初以初以初以初值值。例如：例如：例如：例如：static int a10=0,1,2,3,4,5,6,7,8,9;static int a10=0,1,2,3,4,5,6,7,8,9;可以只可以只可以只可以只给给一部分元素一部分元素一部分元素一部分元素赋赋初初初初值值例如：例如：例如：例如：static int a10=0,1,2,3,4;static int a10=0,1,2,3,4;后后后后5 5个数个数个数个数为为0 static int 0 static int b10=,1,3,5;b10=,1,3,5;不能不能不能不能给给数数数数组组整体整体整体整体赋赋初初初初值值 例如：例如：例如：例如：static int a10=0,0,0,0,0,0,0,0,0,0 static int a10=0,0,0,0,0,0,0,0,0,0 合法合法合法合法 static int q10=0*10 static int q10=0*10 非法定非法定非法定非法定义义 在在在在对对全部数全部数全部数全部数组组元素元素元素元素赋赋初初初初值时值时，可以不指定数，可以不指定数，可以不指定数，可以不指定数组长组长度度度度例如：例如：例如：例如：static int a=1,2,3,4,5static int a=1,2,3,4,5 如果不如果不如果不如果不赋值赋值，则则全部自全部自全部自全部自动赋动赋0 04.2 一维数组一维数组信息信息与与物流管理系物流管理系例例4-1 用数组来处理求用数组来处理求Fibonacci数列的问题，程序如下数列的问题，程序如下：main()int i;static int f20=1,1;for(i=2;i20;i+)fi=fi-2+fi-1;for(i=0;i1 0 0 0 03 0 0 0 05 0 0 0 0a35=1,0,0,3,0,2,5=1 0 0 0 00 0 3 0 00 2 5 0 0a35=1,2,3=1 0 0 0 02 3 0 0 00 0 0 0 0 a35=1,2,3=1 0 0 0 00 0 0 0 02 3 0 0 0第三行没赋第三行没赋值，均为值，均为0第二行为空第二行为空括号，为括号，为04.3 二维数组二维数组信息信息与与物流管理系物流管理系也可以对部分元素赋值，同时省略第一维的长度也可以对部分元素赋值，同时省略第一维的长度也可以对部分元素赋值，同时省略第一维的长度也可以对部分元素赋值，同时省略第一维的长度例如：a 3=0,0,3,10=0 0 30 0 010 0 0已指明是已指明是3列列注明是注明是3行行4.3 二维数组二维数组信息信息与与物流管理系物流管理系/*/*例例4-2 4-2 矩阵相加减矩阵相加减*/main()main()int i,j,c34,d34;int i,j,c34,d34;int a34=1,2,3,4,5,6,7,8,9,10,11,12;int a34=1,2,3,4,5,6,7,8,9,10,11,12;int b34=13,14,15,16,17,18,19,20,21,22,23,24;int b34=13,14,15,16,17,18,19,20,21,22,23,24;for(i=0;i3;i+)for(i=0;i3;i+)for(j=0;j4;j+)for(j=0;j4;j+)cij=aij+bij;cij=aij+bij;dij=aij-bij;dij=aij-bij;4.3 二维数组二维数组信息信息与与物流管理系物流管理系 printf(Array c isn);printf(Array c isn);for(i=0;i3;i+)for(i=0;i3;i+)for(j=0;j4;j+)for(j=0;j4;j+)printf(%5d,cij);printf(%5d,cij);printf(n);printf(n);printf(Array d isn);printf(Array d isn);for(i=0;i3;i+)for(i=0;i3;i+)for(j=0;j4;j+)for(j=0;j4;j+)printf(%5d,dij);printf(%5d,dij);printf(n);printf(n);输出数组输出数组C输出数组输出数组D4.3 二维数组二维数组信息信息与与物流管理系物流管理系/*/*例例 4-3 4-3 将二维数组中的行和列的元素互换将二维数组中的行和列的元素互换*/*/*存到另一个二维数组中去存到另一个二维数组中去*/main()main()static int a23=1,2,3,4,5,6;b32,i,j;static int a23=1,2,3,4,5,6;b32,i,j;printf(array a:n);printf(array a:n);for(i=0;i=1;i+)for(i=0;i=1;i+)for(j=0;j=2;j+)for(j=0;j=2;j+)printf(%5d,aij);printf(%5d,aij);bji=aij;bji=aij;printf(n);printf(n);printf(array b:n);printf(array b:n);for(i=0;i=2;i+)for(i=0;i=2;i+)for(j=0;j=1;j+)for(j=0;j=1;j+)printf(%5d,bij);printf(%5d,bij);printf(n);printf(n);元素互换元素互换4.3 二维数组二维数组信息信息与与物流管理系物流管理系4.4.14.4.1定义和引用定义和引用定义和引用定义和引用 (随后举例）随后举例）随后举例）随后举例）字符串字符串字符串字符串 字符串常量，例如：字符串常量，例如：字符串常量，例如：字符串常量，例如：chinachina 没有字符串没有字符串没有字符串没有字符串变变量，用字符数量，用字符数量，用字符数量，用字符数组组来存放字符串来存放字符串来存放字符串来存放字符串 字符串以字符串以字符串以字符串以00为结为结束束束束标标志志志志字符数组初始化字符数组初始化字符数组初始化字符数组初始化(数组中一个元素存放一个字符数组中一个元素存放一个字符数组中一个元素存放一个字符数组中一个元素存放一个字符)例：例：例：例：static char tr8=12,14,11,13,14,97,19,0;static char tr8=12,14,11,13,14,97,19,0;static char str8=p,r,o,g,r,a,m,0;static char str8=p,r,o,g,r,a,m,0;static char str8=program;static char str8=program;static char str =program;static char str =program;4.4 字符数组字符数组信息信息与与物流管理系物流管理系字符个数少于定义的数组元素个数，其余元素自动为空字符个数等于定义的数组元字符个数少于定义的数组元素个数，其余元素自动为空字符个数等于定义的数组元素个数，可以省略数组长度字符个数大于定义的数组元素个数，发生越界素个数，可以省略数组长度字符个数大于定义的数组元素个数，发生越界在在C语言中，如果字符数组长度很大，但实际有效字符却很小，如何测实际长度呢语言中，如果字符数组长度很大，但实际有效字符却很小，如何测实际长度呢？在？在C语言中，以语言中，以 0来作字符结束标志来作字符结束标志 0在在ASCII码中是值等于码中是值等于0的字符，的字符，特点：特点：(1)不显示；不显示；(2)作为空操作符，什么都不干；作为空操作符，什么都不干；因此不产生附加操作。因此不产生附加操作。4.4 字符数组字符数组信息信息与与物流管理系物流管理系/*/*例例4-4*4-4*输出一个字符串输出一个字符串*/main()main()int i;int i;static char c10=I,a,m,G,o,d;static char c10=I,a,m,G,o,d;for(i=0;i10;i+)for(i=0;i10;i+)printf(%c,ci);printf(%c,ci);printf(n);printf(n);4.4 字符数组字符数组信息信息与与物流管理系物流管理系/*/*例例 4-5*4-5*从键盘输入两个字符串，并将其相接后输出从键盘输入两个字符串，并将其相接后输出*/main()main()char str150,str220;char str150,str220;int i,j;int i,j;printf(Enter string No.1:n);printf(Enter string No.1:n);scanf(%s,str1);scanf(%s,str1);printf(Enter string No.2:n);printf(Enter string No.2:n);scanf(%s,str2);scanf(%s,str2);i=j=0;i=j=0;while(str1i!=0)while(str1i!=0)i+;i+;printf(i=%dn,i);printf(i=%dn,i);while(str1i+=str2j+)!=0);while(str1i+=str2j+)!=0);printf(string No.1-%sn,str1);printf(string No.1-%sn,str1);4.4 字符数组字符数组信息信息与与物流管理系物流管理系/*/*例例 4-6*4-6*统计键盘输入文本文件的行数，统计键盘输入文本文件的行数，*/*/*测出是否到文件尾部，有几个回车符测出是否到文件尾部，有几个回车符*/#include#include main()main()int c,nl;int c,nl;nl=0;nl=0;while(c=getchar()!=EOF)while(c=getchar()!=EOF)if(c=n)if(c=n)+nl;+nl;printf(%dn,nl);printf(%dn,nl);4.4 字符数组字符数组信息信息与与物流管理系物流管理系/*/*例例 4-7*4-7*把输入的字符串逆序排列，如输入把输入的字符串逆序排列，如输入ABCDEABCDE，*/*/*输出为输出为EDCBA*/EDCBA*/main()main()char str80;char str80;int c,i,j;int c,i,j;printf(Enter a string:n);printf(Enter a string:n);scanf(%s,str);scanf(%s,str);for(i=0,j=strlen(str)-1;ij;i+,j-)for(i=0,j=strlen(str)-1;ij;i+,j-)c=stri;c=stri;stri=strj;stri=strj;strj=c;strj=c;printf(nReversed string:n%sn,str);printf(nReversed string:n%sn,str);位置互换位置互换互换算法互换算法4.4 字符数组字符数组信息信息与与物流管理系物流管理系/*/*例例 4-8*4-8*统计输入的数字、空格符和其他字符统计输入的数字、空格符和其他字符*/#include#include main()main()int c,i,nwhite=0,nother=0;ndigit10;int c,i,nwhite=0,nother=0;ndigit10;for(i=0;i10;i+)for(i=0;i=0&c=0&c=9)+ndigitc-0;+ndigitc-0;else if(c=|c=n|c=t)else if(c=|c=n|c=t)+nwhite;+nwhite;else else +nother;+nother;for(i=0;i10;i+)for(i=0;i=a&ai=a&ai=z)?ai-a+A:ai;while(ai+!=0);while(ai+!=0);printf(Copied string:n%sn,b);printf(Copied string:n%sn,b);小写改大小写改大写的算法写的算法4.4 字符数组字符数组信息信息与与物流管理系物流管理系/*/*例例4-10*4-10*字符及字符串数组的应用字符及字符串数组的应用*/main()main()char a20=T,s,i,n,g,h,u,a,0;char a20=T,s,i,n,g,h,u,a,0;char b20=University;char b20=University;char c20=Computer;char c20=Computer;char d20=T,h,i,s,0,i,s,0,a;char d20=T,h,i,s,0,i,s,0,a;char str110,str210,str310,char str430;char str110,str210,str310,char str430;int i;int i;for(i=0;i20;i+)for(i=0;iprintf(copy the str3 to str7,in which str7 is empty=%sn,strcpy(str7,str3);%sn,strcpy(str7,str3);printf(str3=%sn,str3);printf(str3=%sn,str3);printf(str7=%sn,str7);printf(str7=%sn,str7);printf(n);printf(n);/*copy the str3 to str2,where str2 isnt empty*/*copy the str3 to str2,where str2 isnt empty*/printf(copy the str3 to str2,in which str2 isnt empty=printf(copy the str3 to str2,in which str2 isnt empty=%sn,strcpy(str2,str3);%sn,strcpy(str2,str3);printf(str2=%sn,str2);printf(str2=%sn,str2);printf(n);printf(n);4.4 字符数组字符数组信息信息与与物流管理系物流管理系/*compare the two strings*/*compare the two strings*/printf(Coprare atr3 and str4=%dn,strcmp(str3,str4);printf(Coprare atr3 and str4=%dn,strcmp(str3,str4);printf(Coprare atr4 and str3=%dn,strcmp(str4,str3);printf(Coprare atr4 and str3=%dn,strcmp(str4,str3);printf(str3=%s,str4=%sn,str3,str4);printf(str3=%s,str4=%sn,str3,str4);/*test the length of the str3*/*test the length of the str3*/printf(length of str3=%dn,strlen(str3);printf(length of str3=%dn,strlen(str3);printf(n);printf(n);/*change the letter from uppercase to lowercase,*/*change the letter from uppercase to lowercase,*/*and lower to upper,Be carefully,AAA and bbb/*and lower to upper,Be carefully,AAA and bbb/*are strings,not characters*/*are strings,not characters*/printf(upper to lower=%sn,strlwr(AAA);printf(upper to lower=%sn,strlwr(AAA);printf(lower to upper=%sn,strupr(bbb);printf(lower to upper=%sn,strupr(bbb);4.4 字符数组字符数组信息信息与与物流管理系物流管理系课堂堂练习在一个旅馆里住着在一个旅馆里住着在一个旅馆里住着在一个旅馆里住着6 6个不同国籍的人，他们分别来自美国，德国，英个不同国籍的人，他们分别来自美国，德国，英个不同国籍的人，他们分别来自美国，德国，英个不同国籍的人，他们分别来自美国，德国，英国，法国，俄罗斯和意大利，他们的名字分别是国，法国，俄罗斯和意大利，他们的名字分别是国，法国，俄罗斯和意大利，他们的名字分别是国，法国，俄罗斯和意大利，他们的名字分别是AA，BB，C C，DD，E E，F F，现已知现已知现已知现已知：(1)A(1)A和美国人是医生；和美国人是医生；和美国人是医生；和美国人是医生；(2)E(2)E和俄和俄和俄和俄罗罗斯人是教斯人是教斯人是教斯人是教师师；(3)C(3)C和德国人是技和德国人是技和德国人是技和德国人是技师师；(4)B(4)B和和和和F F曾曾曾曾经经当当当当过过医生，而德国人从未参医生，而德国人从未参医生，而德国人从未参医生，而德国人从未参军军；(5)(5)法国人比法国人比法国人比法国人比AA年年年年龄龄大，意大利人比大，意大利人比大，意大利人比大，意大利人比C C年年年年龄龄大；大；大；大；(6)B(6)B同美国人下周要去西安，而同美国人下周要去西安，而同美国人下周要去西安，而同美国人下周要去西安，而C C同法国人下周要去杭州；同法国人下周要去杭州；同法国人下周要去杭州；同法国人下周要去杭州；请问请问：A,B,C,D,E,FA,B,C,D,E,F各是哪国人？各是哪国人？各是哪国人？各是哪国人？提示：采用数提示：采用数提示：采用数提示：采用数组组及循及循及循及循环环判断判断判断判断语语句。句。句。句。（A:A:意，意，意，意，B:B:俄俄俄俄 C:C:英英英英 D:D:德德德德 E:E:法法法法 F;F;美美美美)信息信息与与物流管理系物流管理系使用筛法求使用筛法求使用筛法求使用筛法求100100100100以内的所有素数以内的所有素数以内的所有素数以内的所有素数思路思路思路思路想象将想象将想象将想象将100100个数看作沙子和小石头子，让小石头子权称素数；让沙子当个数看作沙子和小石头子，让小石头子权称素数；让沙子当个数看作沙子和小石头子，让小石头子权称素数；让沙子当个数看作沙子和小石头子，让小石头子权称素数；让沙子当作非素数。弄一个筛子，只要将沙子筛走，剩下的就是素数了。作非素数。弄一个筛子，只要将沙子筛走，剩下的就是素数了。作非素数。弄一个筛子，只要将沙子筛走，剩下的就是素数了。作非素数。弄一个筛子，只要将沙子筛走，剩下的就是素数了。非素数一定是非素数一定是非素数一定是非素数一定是 2 2、3 3、4 4 的倍数。的倍数。的倍数。的倍数。使用数组，让下标就是使用数组，让下标就是使用数组，让下标就是使用数组，让下标就是100100以内的数，让数组元素的值作为筛去与否的以内的数，让数组元素的值作为筛去与否的以内的数，让数组元素的值作为筛去与否的以内的数，让数组元素的值作为筛去与否的标志。比如筛去以后让元素值为标志。比如筛去以后让元素值为标志。比如筛去以后让元素值为标志。比如筛去以后让元素值为1 1。综合举例综合举例信息信息与与物流管理系物流管理系方法的依据：方法的依据：方法的依据：方法的依据：1 1 1 1至至至至100100100100这些自然数可以分为三类：这些自然数可以分为三类：这些自然数可以分为三类：这些自然数可以分为三类：单位数：仅有一个数单位数：仅有一个数单位数：仅有一个数单位数：仅有一个数1 1 1 1。素数：素数：素数：素数：是这样一个数，它大于是这样一个数，它大于是这样一个数，它大于是这样一个数，它大于1 1 1 1，且只有，且只有，且只有，且只有1 1 1 1和它自身这样两和它自身这样两和它自身这样两和它自身这样两个正个正个正个正因数。因数。因数。因数。合数：合数：合数：合数：除了除了除了除了1 1 1 1和自身以外，还有其他正因数。和自身以外，还有其他正因数。和自身以外，还有其他正因数。和自身以外，还有其他正因数。1 1 1 1 不是素数，除不是素数，除不是素数，除不是素数，除 1 1 1 1 以外的自然数，当然只有素数与合数。筛法实际上是筛去合数，以外的自然数，当然只有素数与合数。筛法实际上是筛去合数，以外的自然数，当然只有素数与合数。筛法实际上是筛去合数，以外的自然数，当然只有素数与合数。筛法实际上是筛去合数，留下素数。留下素数。留下素数。留下素数。综合举例综合举例信息信息与与物流管理系物流管理系为了提高筛法效率，注意到：为了提高筛法效率，注意到：为了提高筛法效率，注意到：为了提高筛法效率，注意到：令令令令 n n n n 为合数（这里是为合数（这里是为合数（这里是为合数（这里是100100100100），），），），c c c c 为为为为 n n n n 的最小正因数，的最小正因数，的最小正因数，的最小正因数，据初等数论，只要找到据初等数论，只要找到据初等数论，只要找到据初等数论，只要找到 c c c c 就可以确认就可以确认就可以确认就可以确认 n n n n 为合数，将其筛去。为合数，将其筛去。为合数，将其筛去。为合数，将其筛去。综合举例综合举例信息信息与与物流管理系物流管理系程序框图如下：程序框图如下：综合举例综合举例信息信息与与物流管理系物流管理系上述框图很清晰地描述了筛法的思路：上述框图很清晰地描述了筛法的思路：上述框图很清晰地描述了筛法的思路：上述框图很清晰地描述了筛法的思路：1.1.1.1.第一块是一个计数型的循环语句，功能是将第一块是一个计数型的循环语句，功能是将第一块是一个计数型的循环语句，功能是将第一块是一个计数型的循环语句，功能是将primeprime数组清零。数组清零。数组清零。数组清零。primec=0;primec=0;c=2,3,100c=2,3,1002.2.2.2.第二块是正因数第二块是正因数第二块是正因数第二块是正因数d d初始化为初始化为初始化为初始化为 d=2d=2。3.3.3.3.第三块是循环筛数。这里用了一个第三块是循环筛数。这里用了一个第三块是循环筛数。这里用了一个第三块是循环筛数。这里用了一个 do whiledo while 语句，属于一种直到型循环，其一般语句，属于一种直到型循环，其一般语句，属于一种直到型循环，其一般语句，属于一种直到型循环，其一般形式为：形式为：形式为：形式为：dodo 循环体语句块循环体语句块循环体语句块循环体语句块 while(while(表达式表达式表达式表达式)综合举例综合举例信息信息与与物流管理系物流管理系求两个整数的最小公倍数求两个整数的最小公倍数综合举例综合举例分析：假定有分析：假定有分析：假定有分析：假定有x,y x,y 且且且且 x yx y，设最小公倍数为设最小公倍数为设最小公倍数为设最小公倍数为 z z1.z 1.z 一定会一定会一定会一定会=x x2.z=k x,k=1,2,2.z=k x,k=1,2,3.z 3.z 一定会被一定会被一定会被一定会被 y y 整除整除整除整除用两个最简单的数试一下就可以找到算法用两个最简单的数试一下就可以找到算法用两个最简单的数试一下就可以找到算法用两个最简单的数试一下就可以找到算法.比如比如比如比如 x=5,y=3.x=5,y=3.信息信息与与物流管理系物流管理系第一步第一步第一步第一步 z z=x=5x=5 5%3!=0 5%3!=0 /z%y /z%y 不能整除不能整除不能整除不能整除第二步第二步第二步第二步 z=z+x=10z=z+x=10 10%3!=0 10%3!=0 /z%y/z%y 不能整除不能整除不能整除不能整除第三步第三步第三步第三步 z=z+x=15z=z+x=15 15%3=0 15%3=0 /z%y /z%y 能整除能整除能整除能整除 找到了找到了找到了找到了 z z，1515就是就是就是就是5 5和和和和3 3的最小公倍数的最小公倍数的最小公倍数的最小公倍数综合举例综合举例信息信息与与物流管理系物流管理系/*/*/*/*程程程程 序序序序 名：名：名：名：4_12.c *4_12.c */*/*作作作作 者：者：者：者：wuwh *wuwh */*/*编制时间：编制时间：编制时间：编制时间：20022002年年年年9 9月月月月2020日日日日 */*/*主要功能：求两个数的最小共倍数主要功能：求两个数的最小共倍数主要功能：求两个数的最小共倍数主要功能：求两个数的最小共倍数 */*/*#include#include#include#include void main()void main()/主函数主函数主函数主函数 int x=0,y=0,z=0,w=0;/int x=0,y=0,z=0,w=0;/整型变量整型变量整型变量整型变量printf(“printf(“请输入两个整数，用空格隔开：请输入两个整数，用空格隔开：请输入两个整数，用空格隔开：请输入两个整数，用空格隔开：”);/”);/提示信息提示信息提示信息提示信息scanf(%d%d,&x,&y);scanf(%d%d,&x,&y);/键盘输入整数键盘输入整数键盘输入整数键盘输入整数 x x y yif(x y)if(x=ai+1ai=ai+1，位置不动；位置不动；如果如果 ai ai+1ai ai+1，位置交换，位置交换，步骤步骤3 3结束后结束后 an-j+1an-j+1中的数为最小的数中的数为最小的数步骤步骤4 4：让：让 j=j+1,j=j+1,只要只要 j!=n j!=n 就返回步骤就返回步骤3 3 当当j=n j=n 时执行步骤时执行步骤5 5步骤步骤5 5：输出排序结果：输出排序结果综合举例综合举例信息信息与与物流管理系物流管理系/*/*/*/*程程程程 序序序序 名：名：名：名：4_13.c 4_13.c */*/*作作作作 者：者：者：者：wuwh *wuwh */*/*编制时间：编制时间：编制时间：编制时间：20022002年年年年9 9月月月月2222日日日日 */*/*主要功能：冒泡排序主要功能：冒泡排序主要功能：冒泡排序主要功能：冒泡排序 */*/*#include#include/预编译命令预编译命令预编译命令预编译命令void main()void main()/主函数主函数主函数主函数 int i=0,j=0,p=0,a7;int i=0,j=0,p=0,a7;/整型变量整型变量整型变量整型变量for(i=1;i=6;i+)for(i=1;i=6;i+)/键入键入键入键入6 6个数，放入个数，放入个数，放入个数，放入a a数组中数组中数组中数组中 printf(printf(请输入待排序的数请输入待排序的数请输入待排序的数请输入待排序的数a i =“);a i =“);/提示提示提示提示scanf(“%d”,&ai);scanf(“%d”,&ai);/用键盘输入整数赋给用键盘输入整数赋给用键盘输入整数赋给用键盘输入整数赋给aiai for(j=1;j=5;j+)for(j