02实验二 递归与二分搜索算法.doc

实验二递归与二分搜索算法
一、实验目的
(分-治-合)、技巧和效率分析方法;
“二分搜索问题”的递归与分治算法;
。
二、实验环境
Windows XP以上版本的操作系统,Visual Studio 2010编程环境。
实验内容
二分搜索问题:
⑴、设:a[0:n-1]是一个已排好序的数组。请改写二分搜索算法,使得当搜索元素x不在数组中时,返回小于x的最大元素的位置I和大于x的最大元素位置j。当搜索元素在数组中时,I和j相同,均为x在数组中的位置。
⑵、设:有n个不同的整数排好序后存放于t[0:n-1]中,若存在一个下标I,0≤i<n,使得t[i]=i,设计一个有效的算法找到这个下标。要求算法在最坏的情况下的计算时间为O(logn)。
集合划分问题:
问题描述
n个元素的集合{1, 2, …, n}可以划分为若干个非空子集。例如,当n=4 时,集合{1,2,3,4}可以划分为15 个不同的非空子集如下:
{{1},{2},{3},{4}},{{1,2},{3},{4}},{{1,3},{2},{4}},
{{1,4},{2},{3}},{{2,3},{1},{4}},{{2,4},{1},{3}},
{{3,4},{1},{2}},{{1,2},{3,4}},{{1,3},{2,4}},
{{1,4},{2,3}},{{1,2,3},{4}},{{1,2,4},{3}},
{{1,3,4},{2}},{{2,3,4},{1}},{{1,2,3,4}}
其中,集合{{1,2,3,4}}由1 个子集组成;集合{{1,2},{3,4}},{{1,3},{2,4}},{{1,4},{2,3}},{{1,2,3},{4}},{{1,2,4},{3}},{{1,3,4},{2}}