内容发布更新时间 : 2024/11/20 6:18:09星期一 下面是文章的全部内容请认真阅读。

实验一 分治与递归算法的应用

一、实验目的

1．掌握分治算法的基本思想（分-治-合）、技巧和效率分析方法。 2．熟练掌握用递归设计分治算法的基本步骤（基准与递归方程）。 3．学会利用分治算法解决实际问题。

二、实验内容

1.问题描述：

题目一：大整数乘法

用分治算法编程实现两个n位十进制大整数的乘法运算。 题目二：线性时间选择

给定n个元素和一个整数k，要求用O(n)时间找出这n个元素中第k小元素。 题目三：二分搜索算法

设a[0:n-1]是一个已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素的位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。并对自己的程序进行复杂性分析。

题目四：找最小向量问题

给定两个向量X=(x1,x2,… ,xn)和Y=(y1,y2,…,yn)。如果存在一个i，1≤i≤n，使得对于1≤j

题目五：找数

设n个不同的整数排好序后存于T[0:n-1]中。若存在一个下标0≤i

题目六：双色四圆盘梵塔问题

与梵塔问题相同，设ABC是3个塔座，初始时塔座A上有四个圆盘，各圆盘从小到大编号为：1、2、3、4，奇数号圆盘为红色，偶数号圆盘为蓝色。现要求将塔座A上的圆盘移到塔座C上，除满足梵塔问题的移动规则外，还必须满足：任何时刻不允许将同色圆盘叠在一起。试设计一个算法，以最少次数完成上述移动，并输出每次移动的圆盘编号、起始塔座、目的塔座。并对自己的程序进行复杂性分析。

2.数据输入：个人设定，由键盘输入。 3.要求：

1）上述题目任选二做。上机前，完成程序代码的编写 2）独立完成实验及实验报告

三、实验步骤

1.理解算法思想和问题要求； 2.编程实现题目要求；

3.上机输入和调试自己所编的程序； 4.验证分析实验结果；

5.整理出实验报告。

附：实验报告的主要内容

一．实验目的 二．问题描述 三．算法设计

包含：数据结构与核心算法的设计描述、主要算法流程等 四.程序调试及运行结果分析 五.实验总结

附录：程序清单 （程序过长，可附主要部分）