实验三(分治算法)(3页).doc

《实验三(分治算法)(3页).doc》由会员分享，可在线阅读，更多相关《实验三(分治算法)(3页).doc（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-实验三(分治算法)-第 3 页华东师范大学计算机科学技术系上机实践报告课程名称： 算法设计与分析年级：05上机实践成绩：指导教师： 柳银萍姓名：上机实践名称：分治算法学号：上机实践日期：2007-4-24上机实践编号：NO.3组号：上机实践时间：10:00-11:30一、目的二、内容与设计思想1. 在一个数组A1.n 中，同时寻找最大值和最小值假设 n 为 2 的方幂。并给出你的算法的复杂度分析。要求：输入：第一行为一个正整数N(0N=500000),表示数组中有多少个元素,当N=0时表示输入结束。接下来一行中有N个数。表示数组A中的元素，这些数不超过65535。输出：输出最大元素和最小元素

2、，输出见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.并给出你的算法的复杂度分析。要求：输入：输入有多组测试数据，每个输入占两行，第一行表示整数A，第二行表示整数B。.输出：输出A*B。3.1其思路是：3.2具体算法是：3.3其复杂度分析：三、使用环境四、调试过程五、总结六、附录1. 求最值问题的程序： （此处放程序）运行结果：2. 求次最大值问题的程序：（此处放程序）运行结果: 3大整数乘积问题的程序：（此处放程序）运行结果:要求至少给出1组测试数据运行结果。