第六讲 枚举算法和数组变量的应用 本讲任务： 1．知道枚举算法的结构特点、设计步骤和优缺点。 2．不同类型的枚举算法应用举例和上机编程。 3、数组变量的引入，数组组成的要素以及数组的功能和特点。 4、用数组处理批量数据的基本方法。 一、枚举算法相关内容 (1)枚举算法的结构特点 ①枚举法的关键就是列举和检验这两个操作，如图3—1所示。 图3-1列举和检验 ②为了保证对所有可能的情况逐一列举和检验，势必要重复地进行这两个操作，直到所有情况都检验完为止。因此一般用循环结构来实现，如图3—2所示。 图3—2循环检验 ③检验就是对某一给定的条件进行判断，根据判断的不同结果执行不同的操作，所以上图中的“检验”部分可以用分支结构来实现，如图3—3所示。 图3-3用分支实现检验 操作 1
由此可以看出，枚举算法的一般结构是循环结构中嵌套分支结构。其中循环结构用于实现逐一列举，分支结构用于实现检验，列举和检验是循环体中的一部分，当然具体的判断条件和列举内容等应根据实际问题来进行设置。另外一些比较复杂的枚举问题，可能会涉及到循环结构的嵌套。 (2)枚举算法的一般设计步骤 ①确定列举的范围：确定列举的对象的范围，不能随意扩大和缩小列举范围，否则可能会造成多解或漏解后果。 ②明确检验的条件：分析题目，明确检验的对象、检验的条件以及检验后需执行的相关操作；检验的对象可能是循环变量，也可能是其他变量。 ③确定循环控制方式和列举的方式：根据列举的范围，选择合适的方法控制循环；列举的方式是不唯一的，很多时候，可以借助循环变量的变化来进行列举，而有时可能需要通过其他方法来进行列举，如输入等。具体见应用示例中的示例l(求1~2008中，能被37整除的数)。 (3)枚举法的优缺点 枚举法充分利用了计算机快速高效的特点，让计算机进行重复运算，以求得问题的解。由于枚举法是将所有可能的解无一例外地进行检验，因此只要列举正确，枚举法具有非常高的准确性和全面性，然而也正是这个特点决定了枚举法的局限性——效率不高。它的准确性和全面性是以消耗时间为代价获得的。 当然，有些比较复杂的问题可能一时无法找到直接的求解公式，建立有效的数学模型。枚举法的优越性又得以体现。因此，枚举法既有其优越性，又有其局限性。只有认清了这点，我们才能在设计算法时灵活运用，设计出有效、高效的算法。 当然，并不是所有的问题都可以使用枚举算法来寻找答案，仅当问题的所有可能解的个数不太多时，才有可能使用枚举算法，在设计枚举算法时应特别注意时间的消耗问题，当问题可能解的个数较多，所需花费的时间较长时(如需几个月甚至几年乃至更长)，这样的枚举算法是没有实际意义的，换言之枚举法适用于可能解的个数不太多的情况，在可以接受的时间内得到问题的所有解。 (4)几种不同类型的枚举算法 按列举方式可分为以下两种枚举算法。 ①列举的变量和循环变量相关的枚举算法 某些问题中，列举的对象和循环次数之间存在着某种内在的联 系，此时可以直接用循环变量表示，或者由循环变量参与运算得到。 例如求自然数中前25个偶数中所有能被3整除的数，则流程图如 图3—4所示。 其中n是循环变量，用于控制循环，x则用于列举可能的解。 每次循环列举一个可能解，列举的x由循环变量运算得到。当然此 题的列举方式并不唯一，这里只是以此来说明列举的不同方式。 ②列举的变量和循环变量无关的枚举算法 某些问题中，需列举的对象和循环变量间无内在的联系，此时 需使用另外的变量，循环变量则单纯地用于控制循环的次数即列举 的个数。例如，将输入的100个数中的所有正数输出，列举的方式 为输入一个数，循环变量则控制100次循环。图3—4枚举算法流程图 按算法结构可分为以下两种枚举算法。 ①单重循环结构的枚举算法
第6讲数组 数组是具有相同类型的一组数据。数组按照数组名、数据元素的类型和维数来进行描述。当访问数组中的数据时，可以通过下标来指明。数组具有以下属性。 （1）数组可以是一维、多维或交错的。 （2）数值数组元素的默认值设置为0或空。 （3）数组的索引从0开始：具有n个元素的数组的索引是0～n-1。 （4）数组元素可以是任何类型，包括数组类型。 一、一维数组 1．数组的声明 数据类型[] 数组名 如： int[] myArray; 数组的大小不是其类型的一部分，声明一个数组时，不用管数组长度如何。 2．数组对象的创建 声明数组并不实际创建它们。在C＃中，使用new关键字创建数组的对象。 数组名=new 数据类型[数组大小表达式]; 如： myArray=new int[5]; 此数组包含myArray[0]～myArray[4] new运算符用于创建数组并将数组元素初始化它们的默认值。此例初始化为0。 如： String[] myStringArray=new string[6] 此数组包含myStringArray[0]～myStringArray[5]，数组元素初始化为空。 3．一维数组的初始化 数据类型[] 数组名=new 数据类型[] {初值表}; 例： int[] myArray = new int[]{1,3,5,7,9}; 或 int[] myArray; myArray = new int[]{1,3,5,7,9}; 或 int[] myArray= {1,3,5,7,9}; 4．一维数组元素的访问 数组名[下标] （1）用foreach遍历数组： int[] myArray= {1,3,5,7,9}; foreach (int i in myArray)
一维数组： 1、定义一个10个元素的整数数组，赋值为1-10，按如下格式输出数组中的全部数据。 a[0]=1 a[1]=2 ………… 2、打印出Fibonacci数列：从第3个数开始的每个数的值为前两个数之和。 1 1 2 3 5 8 …… 3、输入10个学生的成绩到一个数组中，查找出最低分数及最高分数，计算出总分以及平 均分，计算出及格人数以及成绩在平均分以上的人数。 4、有一个数组，内放10个整数。要求找出最小的数和它的下标，然后把它和数组中最前 面的元素对换位置，找出最大的数和它的下标，然后把它和数组中最后面的元素对换位置。 5、利用随机函数产生10个1-100随机数，并存入数组中。 注解：产生随机数的方法 1）包含库文件#include "Stdlib.h" 使用用randomize()随机种子函数及随机数生产函数random(101)，参数表示范围2）使用用randomize()随机种子函数 随机数生产函数rand ()，无参数，产生int数据类型范围内的随机数 6、将数组中所有元素的值向后移动一位，最后一个元素的值移动到第一个元素中；（将数 组中所有元素的值向前移动一位，第一个元素的值移动到最后一个元素中） 7、将数组中元素的值先按原序输出，逆置（第一个与最后一个交换，第二个与倒数第二个 交换，依次类推）后再输出一次； 8、将一个数组中的元素反向复制到另一个数组中，输出这两个数组。 9、编程输入一个小写字母，以该字母为第一个字母按字母表逆序输出字母表中所有小写字 母。（例：输入m ，则输出：mlkjihgfedcbazyxwvutsrqpon）（利用数组或不利用数组两种方式编程） 10、输入一个数，在数组中找到第一个比它大的数，将输入的数据插入到这个数的前面。 11、将两个数组中的元素交叉复制到一个新的数组中。 12、定义一个整数数组，求出奇数和偶数个数 13、有30个0-9之间的数字，分别统计0-9出现的次数 14、用筛选法求100之内的素数 筛选法又称筛法，是求不超过自然数N（N>1）的所有质数的一种方法。据说是古希腊的埃拉托斯特尼（Eratosthenes，约公元前274～194年）发明的，又称埃拉托斯特尼筛子。具体做法是：先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。 15、下面的程序从键盘接收任意5个数放入数组A中，假设这5个数为：8 1 4 2 5，则要输 出一个具有如下内容的方阵。 16、十五个猴子围成一圈选大王，依次1-7 循环报数，报到7 的猴子被淘汰，直到最后一
第一讲数组习题 第一讲数组 一、选择题 1.在C语言中，引用数组元素时，其数组下标的数据类型允许是。 A）整型常量 B）整型常量或整型表达式C）整型表达式 D）任何类型的表达式 2.以下对一维整型数组a的正确说明是。 A）int a(10); B）int n=10,a[n]; C）int n; scanf(“%d”,&n); int a[n]; D ) #define SIZ E 10 int a[SIZE];以下能对一维数组a 进行正确初始化的语句 是。 A）int a[10]=(0,0,0,0,0); B）int a[10]={ }; C）int a[ ]={0}; D）int a[10]={10*1}; 4.不是给数组的第一个元素赋值的语句是。 A）int a[2]={1}; B) int a[2]={1*2}; C） int a[2];scanf (“%d”,a); D）a[1]=1; 5．下面程序的运行结果是。* main() {int a[6],i; for(i=1;i3))%5; printf(\} }
A)-4 0 4 0 4 B)-4 0 4 0 3 C)-4 0 4 4 3 D)- 4 0 4 4 0 6．下列定义正确的是。* A） static int a[]={1,2,3,4,5} B) int b[]={2,5} C) int a(10) D) int 4e[4] 7．若有说明int a[][4]={0,0};则下列叙述不正确的 是。 A) 数组a的每个元素都可以得到初值0 B) 二维数 组a的第一维的大小为1 C) 因为对二维数组a的第二维大小的值除以初值个数的商为 1，故数组a的行数 为1 D) 只有元素a[0][0]和a[0][1]可得到初值0，其余元素均得 不到初值 8．设有char str[10]，下列语句正确的是。* A) scanf(\ B) printf(\ C) printf(\ D) printf(\ 9．下列说法正确的是。 A) 在C语言中，可以使用动态内存分配技术定义元素个数可 变的数组 B) 在C语言中，数组元素的个数可以不确 定，允许随机变动
第七讲数组 数组是可以同时储存多个同类型数据的单个数据类型，其中所有的数据可以通过数组的下标来访问，并且这些数据在内存中占用的是一块连续的存储空间。数组可以是一维、二维或者三维的。 ●掌握数组的基本概念 ●掌握定义和初始化数组的方法 ●掌握访问数组元素的方法 ●熟练使用System.Array 类的属性和方法 一、一维数组 一维数组的定义 ： 数组必须“先定义，后使用”。定义一维数组的格式如下： 数据类型[] 数组名; 如int[] x; 注意：数据类型可以是任意数据类型，包括数值类型和引用类型； 数组名命名遵循C#变量命名规则； int[] arry;//定义了一个名为arry的数组，这个数字可以存放多个整数，但是此时并没有为存储变量在内存中分配空间。 定义数组和C语言的区别： C语言中：数据类型数组名[数组长度];在定义中包含了数组元素个数，这种定义意味着内存事先按数组长度分配空间，而C# 事先并不为数组元素分配空间，而是在使用数组的过程中动态的分配数组元素的个数，控制数组占用的内存的大小。 一维数组的初始化： 在C#语言中，定义数组后必须对其初始化（为数组分配空间）才能使用。初始化有两种方法：静态初始化和动态初始化。 1.静态初始化 如果数组包含元素不多，且初始数组元素已知，则可以采用静态初始化方法。 数据类型[] 数组名={元素1,元素2，元素3，。。。。。。。，元素n}； 无需说明数组个数，系统自动计算分配数组所需的内存空间。 Int[] arry={1,2,3,4}; String[] str={“china”,”American”,”Korea”};
2.动态初始化 需要使用new 关键字将数组实例化一个对象，再为该数组对象分配内存空间，并为数组元素赋初值。 格式：数据类型[] 数组名；// 数组定义 数组名=new 数据类型[表达式]; //数组动态初始化 或者 数据类型[] 数组名= new 数据类型[表达式]; “表达式”代表数组长度，为整型表达式。 New 运算符用来为数组对象在内存中分配一定的空间。数据占据的内存空间由数组的数据类型和表达式的数值共同决定。 int[] arry;//定义一个名为arry的数组。 arry=new int[10];//为arry数组在内存中分配4*10=40个字节的存储空间，元素值为0. 或 int[] arry=new int[10];//定义一个名为arry的整型数组，并为其分配40个字节的空间。 也可以在初始化得同时赋其他初始值。 Int[] arry=new int[] {1,2,3,4}; 注意：在数组初始化语句中，如大括号中已经明确列出了数组中的元素值，即确定了数组元素个数，则数组元素的个数（方括号中的数值）必须为常量，并且与数组元素个数一致。 Int i=4; Int[] x=new int[4]{1,2,3,4} Int[] y=new int[4] {1,2,3} Int[] z=new int[i]{1,2,3,4} 利用动态初始化的方法，可以动态的修改数组的长度： int[] x=new int[5]; int n=10; x=new int[n]; 一维数组元素的引用： 格式：数组名[下标]； 例：给定10个数字：3，5，34，65，15，74，28，59，122，42，将它们存放在一个数组中，并将其按从小到大的顺序输出。 选择法：先找出10个数中最小数的数组元素位置，将此最小数与数组中的第一个元素对调；再从第2个数到第10个数中找出最小数，按同样的办法，将次最小数与第2个位置上的数对调。 using System; using System.Collections.Generic; using System.Text;
第5章数组 学习目标 ◆掌握数组的概念 ◆掌握一维数组的使用 ◆掌握二维数组的使用 在前面所学的章节中，所使用的数据都属于基本数据类型，除此之外，C语言还提供了构造类型的数据，构造类型的数据包括数组类型、结构体类型和共用体类型。本章就针对其中的数组类型进行讲解。 5.1 什么是数组 在程序中，经常需要对一批数据进行操作，例如，统计某个公司100个员工的平均工资。如果使用变量来存放这些数据，就需要定义100个变量，显然这样做很麻烦，而且很容易出错。这时，可以使用x[0]、x[1]、x[2]……x[99]表示这100个变量，并通过方括号中的数字来对这100个变量进行区分。 在程序设计中，使用x[0]、x[1]、x[2]……x[n]表示的一组具有相同数据类型的变量集合称为数组x，数组中的每一项称为数组的元素，每个元素都有对应的下标（n），用于表示元素在数组中的位置序号，该下标是从0开始的。 为了大家更好地理解数组，接下来，通过一张图来描述数组x[10]的元素分配情况，如图5-1所示。 图5-1数组x[10] 从图5-1中可以看出，数组x包含10个元素，并且这些元素是按照下标的顺序进行排列的。由于数组元素的下标是从0开始的，因此，数组x的最后一个元素为x[9]。 需要注意的是，根据数据的复杂度，数组下标的个数是不确定的。通常情况下，数组元素下标的个数也称为维数，根据维数的不同，可将数组分为一维数组、二维数组、三维数组、四维数组等。通常情况下，我们将二维及以上的数组称为多维数组。 5.2 一维数组 5.2.1一维数组的定义与初始化 一维数组指的是只有一个下标的数组，它用来表示一组具有相同类型的数据。在C语言中，一维数组的定义方式如下所示： 类型说明符数组名[常量表达式]; 在上述语法格式中，类型说明符表示数组中所有元素的类型，常量表达式指的是数组的长度，也就是 1