数组
1.可以存放多个数据的数据类型，我们称为数组。
2.案例
$hens[0]=3; //数组的下标是从0开始的。
$hens[1]=5;
$hens[2]=6;
$hens[3]=4;
$hens[4]=8;
$hens[5]=5;
$allweight=0;
//遍历整个数组
//为了知道某个数组共有多少个元素，可以使用系统函数count
for($i=o;$i echo ‘第’($i+1)’只鸡的体重’=$hens[$i]; $allweight+=$hens[$i]; } echo’ ?> 3.数组创建 在php中，数组就是关键字和值的集合。 ①创建数组 $arr[0]=23; $arr[1]=34; $arr[2]=26; [0] →下标又叫关键字（从0开始计数） $arr →该数组的名称 $arr[0] →数组的一个元素 23 →赋给元素的值。当值为null（空值）时，它也要占用一个空间 ②直接赋值创建数组 $arr=array(值…) ③第3种方式创建数组（在默认情况下，我们的元素的下标，是从0开始编号的，但是实际上，也是可以自己指定的） 基本语法： $arr[‘logo’]=”北京”； $arr[‘hsp’]=123; 或者 $arr=arry(“logo”=>”北京”，”hsp”=123,…) 其对应的遍历方法为 foreach ($arr as $key=>$val){ //key、val 可以是任意取名字echo $key.”=”.$val.” } foreach 遍历方法运用更加广泛。 4.数组问题 4.1在我们创建一个数组时，如果没有给某个元素指定下标，php就会自动的用目前最大的那个下标（索引：整数），加上1 作为该元素的下标（关键字） 案例 <%php $arr=array(5=>”logo”,345,53); echo $arr[5]; echo “ %> 案例2 <%php $arr=array(5=>”logo”,345,53); $arr[5]=”yes”//体现了元素的替换规则 echo $arr[5]; //此时输出yes 这个值 echo “ %> 4.2特殊键名 ①我们用true作为键名，等同于用integer 1 作为键名；用flase作为键名，等同于 用integer0 作为键名。 ②用null 做键名时等同于”” ③使用小数key(关键字：键名)；自动截断小数部分，使用整数部分。 4.3输出显示数组 ①print_r($arr); ②var_dump($arr); 这个输出更详细 4.4数组越界 $arr=array(56,34,453); echo $arr[3]; //数组越界 ?> 4.5 $a=array(2,23) $a[3]=56; echo $a[3]; //当然此处你不能去访问一个不存在的键值，如$a[2].以免越界。 ?> 结果可以输出56 说明php的数组是可以动态增长的。 5.一维数组的引用 基本语法 $数组名[键值] 如果你引用的键值不存在，则会报错。 6.一维数组中，使用自定义的键值（此处当然非正数了）时，注意使用单引号。 7.php数组中的重要函数 ⑴使用count 函数统计数组条数，count($arr); ⑵使用is_array函数判断数组是否存在is_array($arr); ⑶print_r()和var_dump() 可以显示数组信息 ⑷explode(“拆分方式”，拆分变量) $str=”北京天津上海深圳” $arr=explode(“”,$str); //实际开发中，涉及到的数组拆分，很重要 print_r($arr); 输出显示数组 ?> ⑸使用unset 删除数组中数值（变量） $arr[0]=34; $arr[1]=56; $arr[2]=98; unset($arr[1]); //数组某个元素删除后，数组不会被重新编写 echo print_r($arr) ?> 8.我们定义了一个数组，但是没有给数组赋值，那么这个数组值的个数为0. 9.数组遍历的4个方法：for、while、do…while、foreach 前3个方法是有要求的：该数组的下标是从0开始顺序排放。 第四种语法： foreach($arr as $k=>$v ){ echo “ } 10.数组运算符 数组加法(把右边的数组元素【除去相同键值以及与左边数组元素相同的那些元素】附加到左边数组后边)： $a=array(“a”=>”appale”,”b”=>”banana”); $b=array(“a”=>”pear”,”b”=>”starwberry”,”c”=>”cherry”); $c=$a+$b; echo”\$a+\$b result var_dump($c); //“a”=>”appale”,”b”=>”banana” ,”c”=>”cherry” echo” $c=$b+Sa; echo”\$b+\$a result var_dump($c); //“a”=>”pear”,”b”=>”starwberry”,”c”=>”cherry” ?> 11.数组小结 ⑴数组可以存放任意类型的数据 ⑵数组大小不必事先指定，可以动态增长。 ⑶数组名可以理解为指向数组首地址的引用 ⑷数组中的元素以$key=>$value 的形式存在 ⑸如果没有给数组指定key ,则取当前最大的整数索引值，而新的键名将是该值加1. 实验一分治法 一、实验目的 1．理解分治法的方法； 2. 掌握使用分治法解决一般问题的步骤； 3. 掌握分治算法求解数组的最大值和最小值的方法。 二、实验原理 在一个给定数组中查找最大值和最小值是一类常见的问题，也是解决其他一些算法的基础。 假设给定数组为a，数组中含有n个元素，一般的算法是在数组中进行直接查找，算法伪代码如下： 1. x←a[0]; y←a[0] 2. for i←2 to n 3. if a[i] 精选微软等公司数据结构 精选微软等公司数据结构++算法面试100题 -----[第1题-60题总] 资源说明： 此份，是为微软等公司数据结构+算法面试100题，之前60题的汇总。 总结整理了前第1题-第60题。特此并作此一份上传。以飨各位。:)。 -------------------------------- 相关资源，包括答案，下载地址： [答案V0.2版]精选微软数据结构+算法面试100题[前20题]--答案修正 https://www.doczj.com/doc/9411951652.html,/source/2813890 //此份答案是针对最初的V0.1版本，进行的校正与修正。 [答案V0.1版]精选微软数据结构+算法面试100题[前25题] https://www.doczj.com/doc/9411951652.html,/source/2796735 [第二部分]精选微软等公司结构+算法面试100题[前41-60题]： https://www.doczj.com/doc/9411951652.html,/source/2811703 [第一部分]精选微软等公司数据结构+算法经典面试100题[1-40题] https://www.doczj.com/doc/9411951652.html,/source/2778852 更多资源，下载地址： http://v_july_https://www.doczj.com/doc/9411951652.html,/ 很快，我将公布第21-40题的答案，敬请期待。:).. 如果你对以下的前第1-60题，有好的思路，和算法，欢迎跟帖回复， 或者，联系我，发至我的邮箱， zhoulei0907@https://www.doczj.com/doc/9411951652.html,。 My CSDN Blog：https://www.doczj.com/doc/9411951652.html,/v_JULY_v My sina Blog：https://www.doczj.com/doc/9411951652.html,/shitou009 帖子维护地址： [整理]算法面试：精选微软经典的算法面试100题[前1-60题] https://www.doczj.com/doc/9411951652.html,/u/20101023/20/5652ccd7-d510-4c10-9671-307a56006e6d.html -------------------------------------- July、2010、/11.12.请享用。:)。 1 一、实验目的 1．理解分治法的方法； 2. 掌握使用分治法解决一般问题的步骤； 3. 掌握分治算法求解数组的最大值和最小值的方法。 二、实验原理 在一个给定数组中查找最大值和最小值是一类常见的问题，也是解决其他一些算法的基础。 假设给定数组为a，数组中含有n个元素，一般的算法是在数组中进行直接 循环的次数在算法第2行给出，为(n-2)+1=n-1次，因此，算法元素比较总次数为2(n-1)次。 现在采用分治的思想，假设数组的长度为2的整数幂，将数组分割成两半，分别为a[0…(n/2)-1]和a[n/2…n-1]，在每一半中分别查找最大值和最小值，并返回这两个最小值中的最小值以及两个最大值中的最大值。 假设给定数组为a，数组的下标上界和下界分别为low和high，则其算法伪 接比较数组的两个元素，选出最大值和最小值，此为函数的递归终止条件；代码第7行和第8行是两个递归调用，分别在数组的下标范围[low,mid]和 [mid+1,high]查找最小值和最大值，第9行比较两个最大值取其中较大者，第10行比较两个最小值取较大者。 代码的第2、9和10行涉及到元素的比较，第7、8行由于递归也产生元素比较，因此令算法总的元素比较次数为C(n)，则有 ???>+==2 2)2/(221)(n n C n n C 若若 对递推式进行求解 2 2/3 2 2)2/( 2)2(2 2 2...22)2/(2 ... 2 48)8/(824)2)8/(2(4 2 4)4/(42)2)4/(2(22)2/(2)(1 1122111-=-+=+=+++++==+++=+++=++=++=+=∑-=-----n n C n C n C n C n C n C n C n C k k j j k k k k k 得到minmax 算法的元素比较总次数为3n/2-2，优于直接比较的性能。 三、实验内容及要求 1. 编写程序使用分治算法MINMAX 求解数组的最小值和最大值，并用实际数组对算法进行测试。 2. 要求算法中元素比较的次数为3n/2-2，在程序中元素比较的地方进行记录，并在程序末尾输出数组最大值和最小值以及元素比较次数。 四、实验步骤 1. 定义结构体类型或类，用以在函数的返回值同时返回数组的最大值和最小值。 Python高频算法题100例（2019） 1.二维数组中的查找 题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数 2.替换空格 题目：请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。 3.从尾到头打印链表 题目：输入一个链表，从尾到头打印链表每个节点的值。 4.重建二叉树 题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。 5.两个栈实现队列 题目：用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。 6.旋转数组的最小数字 题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0 7.斐波那契数列 题目：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n 项。 8.跳台阶 题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 9.变态跳台阶 题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 10.矩形覆盖 题目：我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？ 11.二进制中1的个数 题目：输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。 12.数值中的整数次方 题目：给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。 13.调整数组顺序使奇数位于偶数前面 题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。 14.链表中倒数第k个节点 题目：输入一个链表，输出该链表中倒数第k个结点。 15.反转链表 数据结构+算法面试100题~~~摘自CSDN，作者July 1.把二元查找树转变成排序的双向链表（树） 题目： 输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点，只调整指针的指向。 10 / / 6 14 / / / / 4 8 12 16 转换成双向链表 4=6=8=10=12=14=16。 首先我们定义的二元查找树节点的数据结构如下： struct BSTreeNode { int m_nValue; // value of node BSTreeNode *m_pLeft; // left child of node BSTreeNode *m_pRight; // right child of node }; 2.设计包含min函数的栈（栈） 定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。 要求函数min、push以及pop的时间复杂度都是O(1)。 参见C:\Users\Administrator\Desktop\demo\Stack 分析：min时间复杂度要达到O(1)，需要我们在栈中存储最小元素 3.求子数组的最大和（数组） 题目： 输入一个整形数组，数组里有正数也有负数。 数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。 分析：根据dp思想 #include 算法分析与设计复习提纲 第一章算法引论 1、算法的定义以及五个特征 算法是完成特定任务的有限指令集，所有的算法都必须满足以下5个特征： 即，输入、输出、确定性、有限性、能行性或可行性。 2、算法与程序的主要区别 算法必须满足定义中的5个特征，而程序不需要满足5个特征中的（C） A.输入 B.确定性 C.有限性 D.能行性 3、算法的空间复杂度 算法的空间复杂度是指其运行所需的存储空间。程序运行所需的存储空间主要由两部分组成，即固定空间需求和可变空间需求。 4、算法的时间复杂度 算法的时间复杂度是指算法运行所需的时间，时间复杂度通常包括最好、最坏和平均时间复杂度。 5、在算法的时间复杂度分析中，其中比较容易分析和计算且最有实际价值的是（A） A.最坏时间复杂度 B.最好时间复杂度 C.平均时间复杂度 D.最好时间复杂度和最坏时间复杂度 6、程序步 一个程序步是指在语法上或语义上有意义的程序段，该程序段的执行时间必须与问题实例的规模无关。 7、给定的一个m次多项式，f(n)=a m n m+ a m-1n m-1+......+a1n+a0是m次多项式，且a m>0，则有 f(n)=O(n m)。 例如：若f(n)=3.6n3+2.5n2+3.8，则有f(n)=O(n3)。 8、多项式时间算法 凡可用多项式函数来对其计算时间限界的算法称为多项式时间算法。常用的多项式时间算法的时间复杂度可能为O(1)，O(log2n)，O(nlog2n)，O(n3)，O(n2)，O(n)则给定的这六种多项时间算法的时间复杂度的大小关系为 O(1) 第一章 1. 算法分析题 算法分析题1－1 求下列函数的渐进表达式 (1). 3n^2 + 10n < 3n^2 + 10n^2 = 13n^2 = O(n^2) (2). n^2 / 10 + 2^n 当n>5是，n^2 < 2 ^n 所以，当n >= 1时，n^2/10 < 2 ^n 故: n^2/10 + 2^n < 2 ^n + 2^n = 2*2^n = O(2^n) (3). 21 + 1/n < 21 + 1 = 22 = O(1) (4). log(n^3)=3log(n)=O(log(n)) (5). 10log(3^n) = (10log3)n = O(n) 算法分析题1-6 (1)因为：f(n)=log(n^2) = 2log(n); g(n) = log(n) + 5 所以：f(n)=Θ(log(n)+5) =Θ(g(n)) (2)因为：log(n) < √n; f(n) = 2log(n); g(n)=√n 所以：f(n) = O(g(n)) (3)因为：log(n) < n; f(n) = n; g(n) = log(n^2) = 2log(n) 所以；f(n) = Ω(g(n)) (4)因为：f(n) = nlogn +n; g(n) = logn 所以：f(n) =Ω(g(n)) (5)因为: f(n) = 10; g(n) = log(10) 所以:f(n) =Θ(g(n)) (6)因为: f(n)=log^2(n); g(n) = log(n) 所以: f(n) ==Ω(g(n)) (7)因为: f(n) = 2^n < 100*2^n; g(n)=100n^2; 2^n > n ^2 所以: f(n) = Ω(g(n)) (8)因为：f(n) = 2^n; g(n) = 3 ^n; 2 ^n < 3 ^n 所以: f(n) = O(g(n)) 习题1－9 证明：如果一个算法在平均情况下的计算时间复杂性为Θ(f(n)),该算法在最坏情况下所需的计算时间为Ω(f(n)). 分析与解答： 因此，Tmax(N) = Ω(Tavg(N)) = Ω(Θ(f(n)))=Ω(f(n)). 第二章 算法分析题 第六讲 枚举算法和数组变量的应用 本讲任务： 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 操作系统是算法吗？请说说算法和程序的区别。 答：不是。 算法是满足下述性质的指令序列： （1）输入：有零个或多个外部量作为算法的输入。 （2）输出：算法产生至少一个量作为输出。 （3）确定性：组成算法的每条指令清晰、无歧义。 （4）有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限 程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)即有限性。 2 关于描述时间复杂度的符号O Ωθ,请简要描述它们的含义。 答：O的定义：如果存在正的常数C和自然数N0，使得当N≥N0时有f(N)≤Cg(N)，则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N))。即f(N)的阶不高于g(N)的阶。 Ω的定义：如果存在正的常数C和自然数N0，使得当N≥N0时有f(N)≥Cg(N)，则称函数f(N)当N充分大时下有界，且g(N)是它的一个下界，记为f(N)=Ω(g(N))。即f(N)的阶不低于g(N)的阶。 θ的定义：定义f(N)= θ(g(N))当且仅当f(N)=O(g(N))且f(N)= Ω(g(N))。此时称f(N)与g(N)同阶。 3 算法A的运行时间至少是O（n2），这种说法正确吗？为什么？ 答：不正确。因为时间复杂度的符号O描述的是函数具有上界，即最多的运行时间是O（n2）。 6、插入排序、合并排序和快速排序这三种算法，哪几种使用了分治策略？请简述之。答：合并排序和快速排序使用了分治的策略。 合并排序：对要排序的数组A[low…high]，令mid=[(low+high)/2]，用A[mid]把原数组A[low…high]分成两个子数组，然后对两个子数组进行排序，在合并两个已牌子徐的子数组，产生排序数组。 快速排序：对要排序的数组A[low…high]，先使用算法SPLIT重新排列元素，使得原先在A[low]中的祝愿占据其正确的位置A[w]，并且所有小于或等于A[w]的元素所处的位置为A[low…w-1]，而所有大于A[w]的元素所处的位置是A[w+1…high]。在对子数组A[low…w-1]和A[w+1…high]递归地排序，产生整个排序数组。 归并排序要好于插入排序，插入排序要好于冒泡排序。 7、分治法适合求解的问题一般具有那些特征？分治法可分为哪三个主要步骤？ 答：适合分治法求解的问题一般具有以下特征： （1）问题的规模缩小到一定程度就可以容易地解决 （2）问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质 （3）基于子问题的解可以合并为原问题的解 （4）问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 分治法可分为以下三个步骤： 分解（Divide）：将原问题分解为子问题 解决（Conquer）：求解子问题 合并（Combine）：组合子问题的解得到原问题的解。 分治法的基本思想： 分治法的基本思想是将规模较大的问题分解为规模较小的子问题，子问题之间相互独立且与原问题同类。求解子问题，然后将子问题的解合并为原问题的解。 分治法的求解实例： 1.把二元查找树转变成排序的双向链表 题目： 输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点，只调整指针的指向。 10 / \ 6 14 / \ / \ 4 8 12 16 转换成双向链表 4=6=8=10=12=14=16。 首先我们定义的二元查找树节点的数据结构如下： struct BSTreeNode { int m_nValue; // value of node BSTreeNode *m_pLeft; // left child of node BSTreeNode *m_pRight; // right child of node }; 2.设计包含min函数的栈。 定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。 3.求子数组的最大和 题目： 输入一个整形数组，数组里有正数也有负数。 数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2， 因此输出为该子数组的和18。 4.在二元树中找出和为某一值的所有路径 题目：输入一个整数和一棵二元树。 从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。 打印出和与输入整数相等的所有路径。 例如输入整数22和如下二元树 10 / \ 5 12 / \ 4 7 则打印出两条路径：10, 12和10, 5, 7。 二元树节点的数据结构定义为： struct BinaryTreeNode // a node in the binary tree { int m_nValue; // value of node BinaryTreeNode *m_pLeft; // left child of node BinaryTreeNode *m_pRight; // right child of node }; 5.查找最小的k个元素 题目：输入n个整数，输出其中最小的k个。 例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。 算法分析与设计实验报告第一次实验 附录： 完整代码（分治法） #include } else//有一个元素 min=A[start]; return min; } //分治法处理整个数组，求最大值与最小值 void merge(int a[],int left,int right,int &Max,int &Min) //Max,Min用来保存最大值与最小值 //之所以使用&引用，是由于如果只是简单的使用变量，并不会改变Max与Min的值，使用指针也可以 { int max1=0,min1=0,max2=0,min2=0; if(right-left>2) //当数组中元素个数大于等于3时，进行分治 { int mid=(right+left)/2; merge(a,left,mid,max1,min1); //左半边递归调用自身，求出最大值最小值，分别保存在max1,min1中 merge(a,mid+1,right,max2,min2); //右半边递归调用自身，求出最大值最小值，分别保存在max2,min2中 if(max1>=max2) //子序列两两合并，求出最大值与最小值，保存在Max与Min中 Max=max1; else Max=max2; if(min1<=min2) Min=min1; else Min=min2; } else//数组中元素个数小于3时的情况，直接赋值 { Max=compmax(a,left,right); Min=compmin(a,left,right); } } void ran(int *input,int n) //随机生成数组元素函数 { int i; srand(time(0)); for(i=0;i 一维数组： 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语言中，数组元素的个数可以不确 定，允许随机变动 算法分析与设计实验报告 拓展实验1 } 算法1结果： 算法2结果： 附录：完整代码 #include intDivideAndconquer(int[],int,int); constint Max=20; int MaxQSum4(int[],int&,int&,int&); intmain(){ inti,x,m,n,Maxsum,a[Max]; cout<<"请输入序列元素个数："< 第2章 1、大整数乘法的O(nm log(3/2))算法 给定2个大整数u和v，它们分别有m位和n位数字，且mn。用通常的乘法求uv的值需要O(mn)时间。可以u和v均看作是有n 位数字的大整数，用教材第2章介绍的分治法，在O(n l og3)时间内计算uv的值。当m比n小得多时，用这种方法就显得效率不够高。试设计一个算法，在上述情况下用O(nm l og(3/2))时间求出uv的值。 2、O(1)空间子数组换位算法 设a[0:n-1]是一个有n个元素的数组，k(1kn-1)是一个非负整数。试设计一个算法将子数组a[0:k-1]与a[k+1:n-1]换位。要求算法在最坏情况下耗时O(n)，且只用到O(1)的辅助空间。 3、段合并排序算法 如果在合并排序算法的分割步骤中，将数组a[0:n-1]划分为个子数组，每个子数组中有O()个元素。然后递归地对分割后的子数组进行排序，最后将所得到的个排好序的子数组合并成所要的排好序的数组a[0:n-1]。设计一个实现上述策略的合并排序算法，并分析算法的计算复杂性。 4、合并排序算法 对拨给元素存储于数组和存储于链表中的2种情形，写出合并排序算法。 5、非增序快速排序算法 如何修改QuickSort才能使其将输入元素按非增序排序？ 第三章 1、整数线性规划问题 考虑下面的整数线性规划问题 试设计一个解此问题的动态规划算法，并分析算法的计算复杂性。2、Ackermann函数 Ackermann函数A(m,n)可递归地定义如下： A（m，n）= 试设计一个计算A(m,n)的动态规划算法，该算法只占用O(m)空间。 3、独立任务最优调试问题 问题描述：用2台机A和B处理n个作业。设第i个作业交给机器A 处理时需要时间a i，若由机器B来处理，则需要时间b i。由于各作业的选战和机器的性能关系，很可能对于某些i，有ai≥bi，而对于某些j，j≠i，有a i 第七讲数组 数组是可以同时储存多个同类型数据的单个数据类型，其中所有的数据可以通过数组的下标来访问，并且这些数据在内存中占用的是一块连续的存储空间。数组可以是一维、二维或者三维的。 ●掌握数组的基本概念 ●掌握定义和初始化数组的方法 ●掌握访问数组元素的方法 ●熟练使用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;
总体重=’.$allweight.’平均体重=’.$allweight/count($hens)
”
”.$arr[6]; //输出345 这个值
”.$arr[6]; //输出345 这个值
as $k=>$v”
”
”;
”_实验1分治法
[第1题-60题汇总]微软数据结构+算法面试100题
-实验1分治法
Python高频算法题100例-2019最新
数据结构算法面试100题
算法复习题-2015
算法设计与分析课后习题
第六讲 枚举算法和数组变量的应用
第6讲数组
算法试题
Java数据结构经典题
分治算法实验(用分治法查找数组元素的最大值和最小值)
第六章：数组
第一讲数组习题
最大子列和
算法设计题目教案资料
第七讲 数组
相关主题
文本预览