C++编程数据组织1-数组-1.ppt

,6数据的组织与处理（一）数组,1,递推的解题思路数组的概念、定义和初始化字符数组、字符串处理筛法的解题思路数组元素的查找（线性查找与二分查找）数组排序的思路（冒泡排序法）多维数组（维以上）,学习目标,2,【任务一】A、B、C、D、E五人合伙夜间捕鱼，凌晨时都疲惫不堪，各自在湖边的树丛中找地方睡着了。日上三竿，A第一个醒来，他将鱼平分作五份，把多余的一条扔回湖中，拿自己的一份回家去了。B第二个醒来，也将鱼平分为五份，扔掉多余的一条，只拿走自己的一份。接着C、D、E依次醒来，也都按同样的办法分鱼。问五人至少合伙捕到多少条鱼？每个人醒来后看到的鱼数是多少条？,3,为了解决上面这种类型的问题，需要学习和运用“递推”的思想，以及如何使用“数组”这种数据组织的形式来实现递推的过程。下面先来介绍“递推”的算法思想。,4,递推是计算机数值计算中的一个重要算法，可以将复杂的运算化为若干重复的简单运算，以便充分发挥计算机长于重复处理的特点。通常，使用循环结构来实现重复处理。解决此类问题的关键是：分析简单情况，归纳总结出前后项的关系（通项公式）。,递推,5,【任务A】求自然数n的阶乘。任务分析：令fact(n)表示n的阶乘，依据后项与前项的关系，可以写出下面的“递推”公式：fact(1)=1-起始条件（边界条件）fact(n)=n*fact(n-1)-通项公式算法实现：根据前后项的关系，显然，用循环结构来实现这种递推关系是非常自然的。请看下面的代码实现。,6,#includeusingnamespacestd;intmain()intN;coutN;intfact;for(intn=1;n=N;n+)if(n=1)fact=1;elsefact=n*fact;/fact_n=n*fact_n_1coutfact(N)=factendl;return0;,7,【任务B】王小二自夸刀功不错，有人放一张饼在砧板上，问他：“饼不许离开砧板，如果切刀，你最多能将饼分成多少块？”,刀,刀,刀,刀,8,在编程之前要找到规律分析：令q(n)表示切n刀能分成的块数。从前面的图中可以找出下列关系：q(1)=1+1=2q(2)=1+1+2=4q(3)=1+1+2+3=7q(4)=1+1+2+3+4=11由于要求最多的块数，所以每刀都是让每两条线都有交点。用归纳法不难得到：q(0)=1-初始条件（边界条件）q(n)=q(n-1)+n-通项公式,9,#includeusingnamespacestd;intmain()intq;for(intn=0;n=100;n+)if(n=0)q=1;elseq=n+q;/q_n=n+q_n_1coutq(100)=qendl;return0;,10,11,数组是计算机语言提供的组织多个数据的一种重要方式：提供了多个同类型的数据（值）在内存中连续存放的工具提供了对无限量内存单元进行高效“命名”的途径提供了在程序运行过程中动态改变“变量名称”的手段是一些重要算法思想的实现基础,数组,12,类型说明符数组名常量表达式;TYPEarray_nameconst_expr;例：floatsheep_weight10;int_a20011000;charstudent_name20;说明1.数组变量的名称，必须符合语言对变量命名的要求；2.用方括号将常量表达式括起；3.常量表达式定义了数组元素的个数；,数组的定义,13,注意：在使用VC+6.0进行编程时，数组元素的数目，要使用常量表达式，其中不能包含变量例如intn;n=5;intan;不合法！因为n是变量，不是常量,VC+6.0:errorC2057:expectedconstantexpression,14,数组中每个元素所在的内存单元，可以通过“数组名位置下标”来访问（赋值、读取）。数组元素的位置下标从0开始计数。例如，inta5；定义了一个含有5个整数的数组，各元素的“变量名称”分别为：a0,a1,a2,a3,a4是5个带下标的变量，它们的类型是相同的。该数组的效果与下面的变量定义相同：inta0,a1,a2,a3,a4;,数组中元素的“名称”,15,数组元素的位置关系与内存地址,aa0a1a2a3a4说明：a0元素的内存地址，即其中，v1,v2等表示常量表达式。例如：inta5=3,5,4,1,2;charb5=c,h,i,n,a;如果是由字符（char）组成的数组，则还可以使用：chararray_nameN=各种字符;例如：chara5=china;其初始化结果为：a0=c;a1=h;a4=a;,数组变量的初始化,17,#includeusingnamespacestd;intmain()/在定义时设定值，被称为“变量初始化”charA10=B,e,i,J,i,n,g;/一共只给出了7个字符for(inti=0;i10;i+)coutAiint(Ai)endl;/强制类型转换，将字符值转换成整数值，即其ASCII码/语法格式：dst_type(src_value)return0;/char_test.cpp,阅读示例代码1，注意总结,18,19,#includeusingnamespacestd;intmain()/在定义时设定值，被称为“变量初始化”charA10=BeiJing;/一共只给出了7个字符for(inti=0;i10;i+)coutAiint(Ai)endl;/强制类型转换，将字符值转换成整数值，即其ASCII码/语法格式：dst_type(src_value)return0;/char_test_2.cpp,阅读示例代码2，注意总结,20,21,#includeusingnamespacestd;intmain()/在定义时设定值，被称为“变量初始化”charA=BeiJing;/一共给出了7个字符intB=1,2,3,4,5;/一共给出了5个整数for(inti=0;i10;i+)coutAiint(Ai);coutBiendl;return0;/char_test_3.cpp,阅读示例代码3，注意总结,22,23,#includeusingnamespacestd;intmain()/在定义时设定值，被称为“变量初始化”charA1=BeiJing;/一共给出了7个字符intB1=1,2,3,4,5;/一共给出了5个整数coutsizeof(A1)sizeof(A1)endl;coutsizeof(B1)sizeof(B1)endl;charA210=BeiJing;/一共给出了7个字符intB210=1,2,3,4,5;/一共给出了5个整数coutsizeof(A2)sizeof(A2)endl;coutsizeof(B2)sizeof(B2)endl;return0;/char_test_4.cpp,阅读示例代码4，猜猜输出,24,A1,25,总结说明,数组变量在“初始化”时（即至少提供了一个初始值），如果提供的初始值数目少于数组元素的个数，则依下标大小顺序，从下标为0的元素开始，逐一设定初始值，缺少初始值的数组元素，将被编译器自动设置成0。以字符串常量方式对字符数组进行“初始化”时，也同样遵循上述规则。如果初始化时不设定数组大小（元素数目），则编译器自动根据初始值的数目来设定数组的大小。如果是字符数组，则编译器设定的数组大小是：“字符串常量长度+1”，即不遵循上述规则！,26,数组变量的赋值,27,28,这是一个伪命题！,数组变量的赋值,29,所有类型的数组变量均不可以直接赋值,数组变量的赋值,30,inta5;charb5;a=1,2,3,4,5;b=CHINA;,数组变量的赋值,31,单独一个一个进行赋值inta5;a0=1;a3=23;使用for语句，连续赋值chara5;for(inti=0;i5;i+)ai=A+i;,数组中各元素的赋值,32,使用一些特殊的库函数（）使用memset函数，格式为memset(起始地址,初始值,空间大小)；举例：memset(sheep,0,sizeof(sheep);将名为sheep的数组中的全部元素均初始化为0。调用此库函数需要加入头文件。（）使用字符串处理函数，例如：strcpy(字符数组名，字符串常量或变量);举例：charschool_name20;strcpy(school_name,Tsinghua);,数组中各元素的赋值,33,#includeusingnamespacestd;intmain()charh=123456;h=abcdef;couthendl;return0;程序会出什么问题？,Line6:error:ISOC+forbidsassignmentofarrays,34,#includeusingnamespacestd;intmain()charh=123456;h=“abcef”;couthh;/设键入的是abcdefcouthendl;/则程序输出abcdefreturn0;如果键入的是123456789012345则程序会输出什么？,36,如果是字符数组（变量），则cout会将数组的所有元素一齐输出出来，字符之间无空格。如果是其他类型的元素组成的数组（变量），则cout只会输出该数组变量的地址，也即数组第一个元素所在内存单元的地址。cout是如何根据数据类型来决定输出方式的呢？这个问题，将在下学期面向对象程序设计中予以解答。,数组变量的“cout输出”,37,#includeusingnamespacestd;intmain()charh=tsinghua;h0=a;h1=b;h2=4;h3=7;h4=c;couthendl;inta=1,2,3,4,5;a0=79;a1=88;a2=34;a3=64;a4=99;coutaendl;cout,38,上述结果说明：数组a的第一个元素的地址，与a的值相等。即couta;与cout等效。,39,字符数组（字符串）的应用示例“老张开车去东北，撞了！肇事司机耍流氓，跑了！”目击者对交警说：肇事汽车的号码为4位完全平方数，且数字从左到右一个比一个大。请帮交警算出肇事车的号码。,40,#include#includeusingnamespacestd;voidfind_it()/.intmain()find_it();return0;,41,思路I：令n为车号n为4位数n=i*i,i=32,33,99(31*31=961)对i进行枚举，得不同的n,对每个n，检查n的各位，从高位到低位,是否一个比一个大？即，低位的数值最大。nn3n2n1n0n3n2n1n0,42,voidfind_it()for(inti=32;i100;i+)intn=i*i;if(n/1000)(n/100%10),四位数的千位数字n3=n/1000,百位数字n2=n/100%10,十位数字n1=n/10%10,个位数字n0=n%10,43,现在，车号升级啦！变成了五位！闯祸的车号居然还是一个完全平方数!依然还是从高位到低位一个比一个大！（越来越大）这时，程序该怎么编（或修改）呢？,44,思路II（还是以四位数的车号为例说明）：令n为车号n为4位数，n=i*ii=32,33,99(31*31=961)枚举i到n,查n从高位到低位,是否一个比一个小将n分解为4个数字字符:char*itoa(intvalue,char*string,intradix)value:待转换整数string:存放转换结果的字符串指针radix:2-16进制整数,45,n=i*ii33n1089itoa(n,buf,10);buf1089001234,46,#include#includeusingnamespacestd;intmain()charbuf5;/定义数组inti=0,n=0;/定义整数变量,47,for(i=32;i100;i+)/计数循环n=i*i;/构造4位数nitoa(n,buf,10);/把10进制数n转换为字符串放入buf数组if(buf0buf1),能把程序改得更简洁清晰吗？,48,for(i=32;i=bufj+1)break;/若n符合要求，则FOR循环会全部执行完！if(j=3)cout肇事汽车号码为nendl;/_for_return0;,修改后的程序，是不是更简洁清晰了？,49,for(i=32;i=bufj+1)break;/若n符合要求，则FOR循环会全部执行完！if(j=3)cout肇事汽车号码为nendl;/_for_return0;,想一想：如何把程序改成能解决五位数（或更多）的车号呢？,50,for(i=32;i=bufj+1)break;/若n符合要求，则FOR循环会全部执行完！if(j=3)cout肇事汽车号码为n=1),定义数组并初始化,输出计算结果,57,上图的说明：,该图可分为三部分(1)是说明部分：包含定义数组fish6，并初始化为1和定义循环控制变量i，并初始化为0。(2)是do.while直到型循环，其循环体又含两块：(2.1)是枚举过程中的fish5的初值设置，一开始fish5=1+5;以后每次增5。(2.2)是一个for循环，i的初值为4，终值为1，步长为-1，该循环的循环体是一个分支语句，如果fishi+1不能被4整除，则跳出for循环（使用break语句;）否则，从fishi+1算出fishi。,58,当break语句让程序退出循环时，意味着某人看到的鱼数不是整数，当然不是所求，必须令fish5加5后再试，即重新进入直到型循环dowhile的循环体。当正常退出for循环时，一定是控制变量i从初值4，一步一步执行到终值1，每一步的鱼数均为整数，最后i=0，表示计算完毕，且也达到了退出直到型循环的条件。(3)输出计算结果,59,#includeusingnamespacestd;intmain()intfish6=1,1,1,1,1,1;/记录每人醒来后看到的鱼数inti=0;dofish5=fish5+5;/让E看到的鱼数增5。for(i=4;i=1;i-)if(fishi+1%4!=0)break;/跳出for循环elsefishi=fishi+1*5/4+1;/计算第i人看到的鱼数while(i=1);/当i=1继续做do循环/输出计算结果for(i=1;i=5;i+)coutfishi=1);,62,初始化E=1E=E+5breakyes递EE%4!=0D=(E*5/4)+1no推yesDD%4!=0方C=(D*5/4)+1noyes向CC%4!=0B=(C*5/4)+1noyesBB%4!=0A=(B*5/4)+1noA,63,31212496199615961276,输出结果,64,#includeusingnamespacestd;intmain()intfisher6;/五个人看到的鱼数for(intnum=6;num+=5)/对各种可能性进行枚举intn;for(n=5;n=1;n-)/对五个人看到的鱼数进行递推if(n=5)fishern=num;else/fishern+1=(fishern-1)/5*4;if(fishern+1%4!=0)break;/鱼数num不满足条件，要尝试下一个num，停止递推else/下式所得fishern必然满足fishern%5=1fishern=fishern+1*5/4+1;if(n=0)/说明鱼数num满足所有人的条件break;/找到最小鱼数了，停止枚举/输出各个人看到的鱼数for(intn=1;n=5;n+)coutfishern=fishernendl;return0;,第种算法实现,65,#includeusingnamespacestd;intmain()intfisher6;/五个人看到的鱼数for(intnum=6;num+=5)/对各种可能性进行枚举intn;for(n=1;n=5;n+)/对五个人看到的鱼数进行递推if(n=1)fishern=num;else/下式所得fishern必然是整数fishern=(fishern-1-1)/5*4;if(fishern%5!=1)break;/鱼数num不满足条件，要尝试下一个num，停止递推if(n=6)/说明鱼数num满足所有人的条件break;/找到最小鱼数了，停止枚举/输出各个人看到的鱼数for(intn=1;n=5;n+)coutfishern=fishernendl;return0;,第种算法实现,66,#includeusingnamespacestd;boolIsOK(intnum,intfisher6)for(intn=1;n=5;n+)/对五个人看到的鱼数进行递推if(n=1)fishern=num;else/下式所得fishern必然是整数fishern=(fishern-1-1)/5*4;if(fishern%5!=1)returnfalse;/鱼数num不满足条件，停止递推returntrue;intmain()intfisher6;/五个人看到的鱼数for(intnum=6;num+=5)/对各种可能性进行枚举if(IsOK(num,fisher)break;/found/输出各个人看到的鱼数for(intn=1;n=5;n+)coutfishern=fishernendl;return0;,第种算法实现,67,任务二、求100以内的所有素数,6.2筛法,68,什么是“筛法”？想象将100个数看作沙子和小石头子，让小石头子权称素数；让沙子当作非素数。弄一个筛子，只要将沙子筛走，剩下的就是素数了。非素数一定是2、3、4的倍数。使用数组，让下标就是100以内的数，让数组元素的值作为筛去与否的标志。比如筛去以后让元素值为1。,69,方法的依据：1至100这些自然数可以分为三类：单位数：仅有一个数1。素数：是这样一个数，它大于1，且只有1和它自身这样两个正因数。合数：除了1和自身以外，还有其他正因数。,1不是素数，除1以外的自然数，当然只有素数与合数。筛法实际上是筛去合数，留下素数。,70,为了提高筛法效率，注意到：令n为合数（这里是100），c为n的最小正因数，据初等数论，只要找到c就可以确认n为合数，将其筛去。,一定注意：要进行“筛”的1100的数字是与数组prime101的下标相对应的，而每个数组元素的取值只有2个：是0或1，分别代表（标志）与下标相对应的数字是素数或不是素数。,71,0010101010101012345678910111213141516。0010101110101112345678910111213141516。寻找2的倍数寻找3的倍数寻找4的倍数,72,程序框图如下：,请分析左边程序的结构从而了解算法的设计思路为程序代码的实现创造条件,73,上述框图很清晰地描述了筛法的思路：STEP1.将prime数组清零，使用了一个计数型的循环语句。STEP2.将正因数d初始化为d=2。STEP3.循环筛数。这里用了一个dowhile语句，也称为“直到型循环”。STEP4.输出“筛”过后的数组，即剩下的所有素数，这里使用了标识数组。,74,补充说明,在dowhile语句中，检测primek是否为零。若是零，则说明k是质数。这是因为sqrt(k)k，所以，当检测到k时，2sqrt(k)必然已全部测试过了。如果在sqrt(k)中有整除k的数，则primek必会被设为。因此，若此时primek是零，则说明2sqrt(k)中没有遇到整除k的数。于是，按初等数论知识，k应是质数无疑。,75,#include/cout#include/sqrt()usingnamespacestd