实验三(分治算法)

华东师范大学计算机科学技术系学生上机实践报告第1页共3页华东师范大学计算机科学技术系上机实践报告课程名称：算法设计与分析年级：05上机实践成绩：指导教师：柳银萍姓名：上机实践名称：分治算法学号：上机实践日期：2007-4-24上机实践编号：NO.3组号：上机实践时间：10:00-11:30一、目的二、内容与设计思想1.在一个数组A[1..n]中，同时寻找最大值和最小值[假设n为2的方幂]。并给出你的算法的复杂度分析。要求：输入：第一行为一个正整数N(0N=500000),表示数组中有多少个元素,当N=0时表示输入结束。接下来一行中有N个数。表示数组A中的元素，这些数不超过65535。输出：输出最大元素和最小元素，输出见sample。每个Case之间用一个空行隔开。1.1其思路是：1.2具体算法是：1.3其复杂度分析2.给出一个分治算法，在一个具有n个数的数组中找出第二个最大元素。要求：输入：第一行为一个正整数N(0N=500000)，表示数组中有多少个元素，当N=0时表示输入结束。接下来一行中有N个数，表示数组A中的元素，这些数不超过65535。输出：输出第二个最大元素，每一个输出占一行。2.1其思路是：2.2具体算法是：3．给出一个分治算法，计算两个n位大整数的乘积。即A*B.并给出你的算法的复杂度分华东师范大学计算机科学技术系学生上机实践报告第2页共3页析。要求：输入：输入有多组测试数据，每个输入占两行，第一行表示整数A，第二行表示整数B。.输出：输出A*B。3.1其思路是：3.2具体算法是：3.3其复杂度分析：三、使用环境四、调试过程五、总结六、附录1.求最值问题的程序：（此处放程序）运行结果：2.求次最大值问题的程序：（此处放程序）运行结果:3．大整数乘积问题的程序：华东师范大学计算机科学技术系学生上机实践报告第3页共3页（此处放程序）运行结果:要求至少给出1组测试数据运行结果。