第5章 减治法资料课件.ppt

《第5章 减治法资料课件.ppt》由会员分享，可在线阅读，更多相关《第5章 减治法资料课件.ppt（83页珍藏版）》请在三一办公上搜索。

1、第5章 减治法Reduce and Conquer Method,算法设计与分析本科生课程Design and Analysis of Algorithm,海南大学信息科学技术学院College of Information Science and Technology, Hainan University,2022/12/20,Reduce and Conquer Method,2,学习目标,2022/12/20,Reduce and Conquer Method,3,第5章 减治法,5.1 概述,5.2 查找问题中的减治法,5.3 排序问题中的减治法,5.4 组合问题中的减治法,阅读材料

2、假币问题的复杂版本,2022/12/20,Reduce and Conquer Method,4,5.1 概述,分治法：把一个大问题划分为若干个子问题，分别求解各个子问题，然后将子问题的解合并得到原问题的解。减治法：同样把一个大问题划分为若干个子问题，但无须分别求解这些子问题，只需求解其中的一个子问题，因而无需对子问题的解进行合并。退化了的分治法。,2022/12/20,Reduce and Conquer Method,5,减治法的设计思想,减治法将问题划分为若干子问题，并且规模为n的原问题的解与较小规模（通常是n/2）的子问题的解之间具有某种确定的关系：（1）原问题的解只存在于其中一个较小

3、规模的子问题中；（2）原问题的解与其中一个较小规模的解之间有某种对应关系。 由于原问题的解与较小规模的子问题的解之间存在这种关系，所以，只需求解其中一个较小规模的子问题就可以得到原问题的解。,2022/12/20,Reduce and Conquer Method,6,减治法的设计思想,2022/12/20,Reduce and Conquer Method,7,例：计算an的值，应用减治技术得到如下计算方法：,应用分治法得到an的计算方法是：,O (log2n),O (n log2n),减治法的设计思想,2022/12/20,Reduce and Conquer Method,8,所以，通常

4、来说，应用减治法处理问题的效率是很高的，一般是O(log2n)数量级。,减治法只对一个子问题求解，并且不需要解的合并。应用减治法（例如减半法）得到的算法通常具有如下递推式：,减治法的设计思想,对比分治法：,2022/12/20,第5章 减治法,Page 9,减治法的设计思想,一个简单的例子两个序列的中位数,问题描述：一个长度为n（n1）的升序序列S，处在第n/2个位置的数称为序列S的中位数 。两个序列的中位数是他们所有元素的升序序列的中位数。现有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列的中位数。,A=11, 13, 15, 17, 19, B=2,

5、4, 10, 15, 20，则中位数为13,2022/12/20,第5章 减治法,Page 10,减治法的设计思想,想法 分别求出两个序列的中位数，记为a和b；比较a和b，有下列三种情况： a = b：则a即为两个序列的中位数； a b：则中位数只能出现在b和a之间，在序列A中舍弃a之后的元素得到序列A1，在序列B中舍弃b之前的元素得到序列B1；在A1和B1中分别求出中位数，重复上述过程，直到两个序列中只有一个元素，则较小者即为所求。,2022/12/20,第5章 减治法,Page 11,减治法的设计思想,对于两个给定的序列A=11, 13, 15, 17, 19, B=2, 4, 10, 1

6、5, 20，求序列A和B的中位数的过程。,2022/12/20,第5章 减治法,Page 12,减治法的设计思想,算法5.1：两个序列中位数SearchMid输入：两个长度为n的有序序列A和B输出：序列A和B的中位数1. 循环直到序列A和序列B均只有一个元素 1.1 a = 序列A的中位数； 1.2 b = 序列B的中位数； 1.3 比较a和b，执行下面三种情况之一： 1.3.1 若a=b，则返回a，算法结束； 1.3.2 若ab，则在序列A中舍弃a之后的元素，在序列B中舍弃b之前的元素，转步骤1； 2. 序列A和序列B均只有一个元素，返回较小者；,2022/12/20,第5章 减治法,Pag

7、e 13,减治法的设计思想,算法分析 由于每次求两个序列的中位数后，得到的两个子序列的长度都是上一个序列的一半，故循环共执行log2n次，时间复杂性为O( log2n)。算法除简单变量外没有额外开辟临时空间，故空间复杂性为O(1)。,2022/12/20,Reduce and Conquer Method,14,第5章 减治法,5.1 概述,5.2 查找问题中的减治法,5.3 排序问题中的减治法,5.4 组合问题中的减治法,阅读材料 假币问题的复杂版本,2022/12/20,Reduce and Conquer Method,15,5.2 查找问题中的减治法,5.2.1 折半查找,5.2.2

8、二叉查找树,2022/12/20,Reduce and Conquer Method,16,基本思想：(1)取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；(2)若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；(3)若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。重复上述过程，直到成功，或所查找的区域无记录，查找失败。,折半查找,问题：在有序表中查找值为k的记录,2022/12/20,Reduce and Conquer Method,17,例：查找值为14的记录的过程,0 1 2 3 4 5 6 7 8 9 10 11 12 13,7 14 18

9、21 23 29 31 35 38 42 46 49 52,3114,1814,714,14=14,2022/12/20,Reduce and Conquer Method,18,折半查找,2022/12/20,Reduce and Conquer Method,19,算法分析用判定树描述折半查找的判定过程。每个结点对应有序序列中的一个记录，结点值为该记录在有序序列中的位置。长度为n的判定树的构造方法为： （1）当n=0时，判定树为空；（2）当n0时， 根结点：是有序表中序号为mid=(n+1)/2的记录； 左子树：是有序表r1 rmid-1对应的判定树； 右子树：是与rmid+1 rn相对应

10、的判定树,折半查找,2022/12/20,Reduce and Conquer Method,20,具有11个结点的判定树,查找k过程：从根结点该记录结点的路径； 和K值的比较次数：等于该记录结点在树中的层数。具有n个结点的判定数的深度为 。,折半查找,2022/12/20,Reduce and Conquer Method,21,5.2 查找问题中的减治法,5.2.1 折半查找,5.2.2 二叉查找树,2022/12/20,Reduce and Conquer Method,22,二叉查找树（BST）/二叉排序树的性质若它的左子树不空，则左子树上所有结点的值均小于根结点的值；若它的右子树不空

11、，则右子树上所有结点的值均大于根结点的值；它的左右子树也都是二叉排序树。,二叉查找树BST,2022/12/20,Reduce and Conquer Method,23,二叉查找树BST,由二叉排序树的定义，在二叉排序树root中查找给定值k的过程是： 若root是空树，则查找失败； 若k根结点的值，则查找成功； 否则，若k根结点的值，则在root左子树上查找； 否则，在root的右子树上查找； 上述过程一直持续到k被找到或者待查找的子树为空，如果待查找的子树为空，则查找失败。二叉排序树的查找效率就在于只需要查找两个子树之一。,2022/12/20,Reduce and Conquer Me

12、thod,24,二叉查找树BST,查找58与95记录的示例,2022/12/20,Reduce and Conquer Method,25,二叉排序树的结点结构为：struct BiNode int data; /结点的值，假设查找集合的元素为整型 BiNode *lchild, *rchild; /指向左、右子树的指针 ;,二叉查找树BST,2022/12/20,Reduce and Conquer Method,26,建立二叉查找树算法BiNode* InsertBST(BiNode* root, int data) if(root=NULL) root=new BiNode; root-

13、data=data;/申请一个新结点 root-lchild=root-rchild=NULL;/叶子结点 return root; if(datadata)root-lchild=InsertBST(root-lchild, data); elseroot-rchild=InsertBST(root-rchild, data);return root;,二叉查找树BST,2022/12/20,Reduce and Conquer Method,27,BiNode* createBST(int a, int n) /建立二叉查找树 BiNode* T=NULL; for(int i=0; in

14、; i+)T=InsertBST(T, ai); /在二叉查找树 T中插入ai return T;,二叉查找树BST,2022/12/20,Reduce and Conquer Method,28,二叉查找树BST,按63,90,55,58,70,42,10,45,83,67顺序构造的二叉排序树,2022/12/20,Reduce and Conquer Method,29,算法分析：在二叉排序树上查找关键码K等于结点值的过程，恰好走了一条从根结点k结点的路径；和K值的比较次数：等于k值结点在二叉排序树中的层数，比较次数最少为1次（即整个二叉排序树的根结点就是待查结点），最多不超过树的深度。具

15、有n个结点的二叉树的深度至少是 ，至多是n，所以，二叉排序树的查找性能在 O(log2n) 和O (n)之间。,二叉查找树BST,2022/12/20,第5章 减治法,Page 30,问题 设无序序列 T =(r1, r2, , rn)，T 的第k（1kn）小元素定义为T 按升序排列后在第k个位置上的元素。给定一个序列T和一个整数k，寻找 T 的第k小元素的问题称为选择问题。特别地，将寻找第n/2小元素的问题称为中值问题。,5.2.3 选择问题,想法 固然可将T排序后取第k个元素，但排序算法最好时间是O(nlog2n)，如应用减治技术，可将算法平均时间性能提高到O(n)。考虑快速排序中的划分过

16、程，一般情况下，设待划分的序列为ri rj，选定一个轴值将序列ri rj进行划分，使得比轴值小的元素都位于轴值的左侧，比轴值大的元素都位于轴值的右侧，假定轴值的最终位置是s，则：,2022/12/20,第5章 减治法,Page 31,（1）若k=s，则rs就是第k小元素；（2）若ks，则第k小元素一定在序列rs+1 rj中；无论上面哪种情况，或者已经得到结果，或者将选择问题的查找区间减少一半（如果轴值恰好是序列的中值）,5.2.3 选择问题,2022/12/20,第5章 减治法,Page 32,选择问题的例子:查找第4小元素,5.2.3 选择问题,2022/12/20,第5章 减治法,Page

17、 33,5.2.3 选择问题,2022/12/20,第5章 减治法,Page 34,最好情况：每次划分的轴值恰好是序列的中值，则可以保证处理的区间比上一次减半，由于在一次划分后，只需处理一个子序列，所以，比较次数的递推式是：,最坏情况：每次划分的轴值恰好是序列中的最大值或最小值，则处理区间只能比上一次减少1个，所以，比较次数的递推式是：,平均情况：假设每次划分的轴值是划分序列中的一个随机位置的元素，则处理区间按照一种随机的方式减少，可以证明，算法的平均时间是O(n) 。,5.2.3 选择问题,2022/12/20,Reduce and Conquer Method,35,第5章 减治法,5.1

18、 概述,5.2 查找问题中的减治法,5.3 排序问题中的减治法,5.4 组合问题中的减治法,阅读材料 假币问题的复杂版本,2022/12/20,Reduce and Conquer Method,36,5.3 排序问题中的减治法,5.3.1 插入排序,5.3.2 堆排序,5.3.1 插入排序,插入排序属于减治法的减一技术,2022/12/20,第5章 减治法,Page 37,每次将无序区第1条记录插入到有序区适当位置。初始取第1条记录为有序区，其它记录为无序区。随着排序进行，有序区不断扩大，无序区不断缩小。最终无序区为空，有序区包含了全部记录，排序结束。 有序区也可从排序表的尾部生成 。,20

19、22/12/20,第5章 减治法,Page 38,在插入第 i（i1）个记录时，前面的 i-1个记录已经排好序。,（1）如何构造初始的有序序列？(待排序序列第一个记录）（2）如何查找待插入记录的插入位置?,需解决的关键问题?,2022/12/20,第5章 减治法,Page 39,例：对(49 38 13 76 27 49 )进行插入排序。初始：（49）38 13 76 27 49 （38 49）13 76 27 49 （13 38 49）76 27 49 （13 38 49 76）27 49 （13 27 38 49 76 ）49 （13 27 38 49 49 76 ）,自右向左顺序查找插入

20、的位置,插入排序过程示例,2022/12/20,第5章 减治法,Page 40,r 0 1 2 3 4 5 6,21,18,25,22,10,25*,21,插入排序,22,10,25,18,18,r0的作用?,暂存单元,监视哨,25,2022/12/20,第5章 减治法,Page 41,void InsertSort(int r,int n) /设置监视哨for(int i=2;i=n;i+)/进行n-1次插入，依次插入 /r2,r3,rn r0=ri; /r0是监视哨 /顺序比较和移动，查找ri的插入位置 for(int j=i-1;r0rj;j-) rj+1=rj; /记录后移，继续向前搜

21、索 rj+1=r0; /插入ri ,r0为监视哨（Sentinel），省略下标越界检查“j1”：一旦越界，j=01，循环条件r0rj不成立，循环结束。,2022/12/20,第5章 减治法,Page 42,插入排序算法性能分析,最好情况下（正序）：,最坏情况下（逆序或反序）：,时间复杂度为O(n2)。,比较次数：,时间复杂度为O(n)。,移动次数：,平均情况下：,时间复杂度为O(n2)。,比较次数：,移动次数：,2022/12/20,第5章 减治法,Page 43,空间性能：需要一个记录的辅助空间监视哨。插入排序算法是一种稳定的排序算法。,插入排序算法性能分析,插入排序算法简单、容易实现，适用

22、于待排序记录基本有序或待排序记录较小时。当待排序的记录个数较多时，大量的比较和移动操作使插入排序算法的效率降低。,2022/12/20,Reduce and Conquer Method,44,堆(heap)的概念 堆是具有下列性质的完全二叉树：小根堆：每个结点的值都小于或等于其左右孩子结点的值大根堆：每个结点的值都大于或等于其左右孩子结点的值,堆排序,或：n个关键字序列K1,K2,Kn称为堆，当且仅当该序列满足：KiK2i且KiK2i+1 (1in/2)小根堆或者KiK2i且KiK2i+1 (1in/2)大根堆,2022/12/20,第5章 减治法,Page 45,小根堆,大根堆,不是堆,不

23、是堆,堆中任一棵子树也是堆,2022/12/20,Reduce and Conquer Method,46,堆排序,以结点的编号作为下标，将堆用顺序存储结构（即数组）来存储，则堆对应于一组序列。,2022/12/20,Reduce and Conquer Method,47,满二叉树与完全二叉树补充知识满二叉树?一棵深度为 k 且有 2k-1 个结点的二叉树称满二叉树。其特点是：第i层上的结点数都是最大结点数2i-1 。完全二叉树? 一棵深度为k 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至 n 结点一一对应时，称为完全二叉树。或者：除最后一层外，每一层上

24、的节点数均达到最大值；在最后一层上只缺少右边的若干结点。,堆排序,2022/12/20,Reduce and Conquer Method,48,(a)满二叉树,(b) 完全二叉树,(c) 完全二叉树,1,4,5,3,6,5,3,6,1,2,5,3,1,2,2,4,4,堆排序,7,完全二叉树的特点有二：叶子结点只可能在层次最大的两层上出现；对任一结点，若其右分支下的子孙的最大层次为 k ，则其左分支下的子孙的最大层次必为 k 或 k+1 。,2022/12/20,Reduce and Conquer Method,49,有n 个结点的完全二叉树的深度为log2n+1 证明： 因为：,堆排序,o

25、r,所以：,2022/12/20,Reduce and Conquer Method,50,堆排序的基本思想是：（1)将待排序的记录序列构造成一个堆；（2）选出堆中所有记录的最大者即堆顶记录，然后将它从堆中移走（通常将堆顶记录和堆中最后一个记录交换）；（3）将剩余的记录再调整成堆，这样又找出了次大的记录，以此类推，直到堆中只有一个记录为止。,堆排序,2022/12/20,第5章 减治法,Page 51,为保证时间性能，就要利用已有结果，每次输出堆顶后，剩下元素不是完全重建，应该在原堆上通过某些调整得到；为保证空间性能，输出的堆顶应利用原有空间，可将它与无序区最后记录交换位置。排序过程中有序区在

26、原记录区的尾部逐步形成并向前扩大，和直接选择排序相反。,两个问题：（1）最初如何由一个无序序列建成一个堆？（2）在输出堆顶元素后，如何调整剩余元素成为一个新的堆？,堆排序,1、初始堆的建立,2022/12/20,第5章 减治法,Page 52,把完全二叉树中以每一结点为根的子树都调整为堆。,只有一个结点的树是堆，在完全二叉树中，所有序号in/2的结点都是叶子，以这些结点为根的子树均已是堆。（即叶子已是堆）,依次将以序号为n/2，n/21,1的结点作为根的子树都调整为堆。,按该次序调整各结点时，其左、右子树均已是堆。,堆排序,2022/12/20,第5章 减治法,Page 53,例，对（1,2,

27、9,11,4,6,8,10,16, 5）建初始堆（大根）。n=10，故从第10/2 5个结点开始进行调整,2022/12/20,第5章 减治法,Page 54,初始大根堆！,2、调整和重建,2022/12/20,第5章 减治法,Page 55,将堆顶元素与堆最后的元素互换；将其余的元素筛选成堆；,堆排序,2022/12/20,第5章 减治法,Page 56,堆调整筛选法 关键问题：完全二叉树中，根结点的左右子树均是堆，如何调整根结点，使整个完全二叉树成为一个堆？,堆排序,2022/12/20,第5章 减治法,Page 57,Ri左、右子树是堆，子树的根为各自子树中关键字最大者，将Ri和其左、右

28、孩子中关键字最大者进行比较。若Ri最大，则无需调整，以其为根的子树已是堆；否则，将Ri和具有最大关键字的左孩子R2i或右孩子R2i+1进行交换。交换后以R2i和R2i+1为根的子树可能不再是堆，但其左、右子树仍然是堆，于是重复上述过程，将子树调整为堆，如此逐层递推下去，最多可能一直调整到树叶。这一过程就像过筛子一样，把较小的关键字筛下去，而将最大关键字一层层地选择上来。,堆调整筛选法,2022/12/20,第5章 减治法,Page 58,大根堆,例:筛选法（大根堆）示例。,2022/12/20,第5章 减治法,Page 59,设要筛选结点的编号为k，堆中最后一个结点的编号为n，并且结点k的左右

29、子树均是堆（即rk+1 rn满足堆的条件),时间性能是O(log2n)。,堆调整筛选法,2022/12/20,第5章 减治法,Page 60,堆调整筛选法,2022/12/20,第5章 减治法,Page 61,交换,筛选,交换,筛选,经过跟刚才一样的步骤,堆排序,2022/12/20,第5章 减治法,Page 62,交换,筛选,交换,筛选,2022/12/20,第5章 减治法,Page 63,交换,筛选,交换,筛选,2022/12/20,第5章 减治法,Page 64,交换,筛选,交换,筛选,2022/12/20,第5章 减治法,Page 65,交换,堆排序小结,（1）建堆/堆调整方法：筛选法

30、：将结点与其孩子结点比较。（2）堆排序方法：先建堆；取出堆顶；剩下元素再调整为堆；直至剩下一个元素为止。,2022/12/20,第5章 减治法,Page 66,2022/12/20,Reduce and Conquer Method,67,第5章 减治法,5.1 概述,5.2 查找问题中的减治法,5.3 排序问题中的减治法,5.4 组合问题中的减治法,阅读材料 假币问题的复杂版本,2022/12/20,Reduce and Conquer Method,68,5.4 组合问题中的减治法,5.4.1 淘汰赛冠军问题,5.4.2 假币问题,2022/12/20,Reduce and Conquer

31、 Method,69,淘汰赛冠军问题,问题 假设有n=2k个选手进行竞技淘汰赛，最后决出冠军的选手，请设计淘汰赛的过程。想法 分治法是将所有选手分成两部分，每部分决出胜者后，让这些胜者再进行比赛，最后决出冠军。减治法：将所有选手分成n/2组，每组两个选手比赛，败者被淘汰，然后再将剩余选手分成n/4组，每组两个选手进行比赛，直到剩余最后两个选手决出冠军。,T（n）=O(n),2022/12/20,Reduce and Conquer Method,70,淘汰赛冠军问题,2022/12/20,Reduce and Conquer Method,71,算法分析 因为n=2k，所以，外层的while循

32、环共执行k次，在每一次执行时，内层的for循环的执行次数分别是n/2，n/4，1，而函数comp可以在常数时间内完成，因此，算法5.8的执行时间为：,淘汰赛冠军问题,2022/12/20,Reduce and Conquer Method,72,5.4 组合问题中的减治法,5.4.1 淘汰赛冠军问题,5.4.2 假币问题,2022/12/20,Reduce and Conquer Method,73,假币问题?,问题 在n枚外观相同的硬币中，有一枚是假币，并且已知假币较轻。可以通过一架天平来任意比较两组硬币，从而得知两组硬币的重量是否相同，或者哪一组更轻一些，但不知道轻多少，假币问题是要求设计

33、一个高效的算法来检测出这枚假币。,2022/12/20,Reduce and Conquer Method,74,问题的解决是经过一系列比较和判断，可以用判定树来描述这个判定过程。想法 解决这个问题的最自然的想法就是一分为二，也就是把硬币分成两组。（1）把n 枚硬币分成两组，每组有 枚硬币，如果 n为奇数，就留下一枚硬币，然后把两组硬币分别放到天平的两端。（2）如果两组硬币的重量相同，那么留下的硬币就是假币；否则，用同样的方法对较轻的那组硬币进行同样的处理，假币一定在较轻的那组里。,假币问题,2022/12/20,Reduce and Conquer Method,75,在假币问题中，每次用天

34、平比较后，只需解决一个规模减半的问题，所以，它属于一个减治算法。该算法在最坏情况下的时间性能有这样一个递推式：,求解这个递推式，得到T(n)=O(log2n)。,假币问题,2022/12/20,Reduce and Conquer Method,76,硬币分成两组不一定最佳，考虑分成三组，前两组有 组硬币，其余的硬币作为第三组，将前两组硬币放到天平上，如果他们的重量相同，则假币一定在第三组中，用同样的方法对第三组进行处理；如果前两组的重量不同，则假币一定在较轻的那一组中，用同样的方法对较轻的那组硬币进行处理。显然这个算法存在递推式：,这个递推式的解是T(n)=O(log3n)。,假币问题,20

35、22/12/20,第5章 减治法,Page 77,采用递归技术设计假币问题的算法如下：,算法5.5假币问题Coin输入：硬币所在数组的下标范围low和high，硬币的个数n输出：假币在硬币集合中的序号 1. 如果n等于1，则该硬币即为假币，输出对应的序号，算法结束； 2. 计算3组的硬币个数num1、num2和num3； 3. add1=第1组硬币的重量和；add2=第2组硬币的重量和； 4. 根据情况执行下述三种操作之一： 4.1 如果add1add2，则在第2组硬币中查找； 4.3 如果add1=add2，则在第3组硬币中查找；,假币问题,2022/12/20,Reduce and Con

36、quer Method,78,考虑假币问题的一个更复杂的版本不知道假币与真币相比较轻还是较重。 设有八枚硬币，分别表示为a，b，c，d，e，f，g，h，从八枚硬币中任取六枚a，b，c，d，e，f，在天平两端各放三枚进行比较。假设a，b，c三枚放在天平的一端，d，e，f三枚放在天平的另一端，可能出现三种比较结果： abcdef abcdef abcdef,阅读材料假币问题的复杂版本,2022/12/20,Reduce and Conquer Method,79,若abcdef，可以肯定这六枚硬币中必有一枚为假币，同时也说明g，h为真币。这时可将天平两端各去掉一枚硬币，假设去掉c和f，同时将天平两

37、端的硬币各换一枚，假设硬币b，e作了互换，然后进行第二次比较，比较的结果同样可能有三种： aedb：这种情况表明天平两端去掉硬币c，f且硬币b，e互换后，天平两端的轻重关系保持不变，从而说明了假币必然是a，d中的一个，这时我们只要用一枚真币（例如h）和a进行比较，就能找出假币。若ah，则a是较重的假币；若ah，则d为较轻的假币；不可能出现ah的情况。,阅读材料假币问题的复杂版本,2022/12/20,Reduce and Conquer Method,80, aedb：此时天平两端由不平衡变为平衡，表明假币一定在去掉的两枚硬币c，f中，同样用一枚真币（例如h）和c进行比较，若ch，则c是较重的假币；若ch，则f为较轻的假币；不可能出现ch，则b是较重的假币；若bh，则e为较轻的假币；不可能出现bh的情况。,阅读材料假币问题的复杂版本,2022/12/20,Reduce and Conquer Method,81,阅读材料假币问题的复杂版本,人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。,