算法设计与分析复习题最终版

5、

#include using namespace std; double GetSum(int n) {

if(n == 0) return 0;

return GetSum(n - 1) + 1.0 / n; }

int main() {

cout<

四、算法实现题

1、把一个字符串（数组）进行逆序操作，如“abc\逆序为“cba” ，要求空间复杂度为O(1).

2、请用递归算法实现判断一个数组是否是从小到大排序，要求递归函数返回bool值. 比如数组1，2，3，4，5，6是从小到大排序,递归函数返回true.

3、 五对括号可以有多少种匹配排列方式？

4、求一个数组的最长递减（上升）子序列 比如{9，4，3，2，5，4，3，2}的最长递减子序列为 {9，5，4，3，2}

5、请用递归算法实现判断一个字符串是否是对称字符串，要求递归函数返回bool值. 比如“abcdcba”是对称字符串,递归函数返回true.

6、请用递归算法求和，公式为：f(n)=2+4+6+.....+(2*n)，n为正整数，f(n)不会超出整数范围。要求递归函数返回int类型。

7、一个硬币有两种状态，正面朝上和反面朝上。现在有N个硬币，请输出它们排出正面朝上的硬币数大于反面朝上的硬币数的所有情况，要求用回溯法解决该问题．比如有４个硬币的情况: (0-正面朝上, 1- 反面朝上)

0 0 0 0 0 0 0 1 0 0 1 0 ............ ............

8、请用递归算法求和，公式为：f(n)=1+3+5+.....+（2*n-1），n为正整数，f(n)不会超出整数范围。要求递归函数返回int类型。

从三个方面进行答题：算法描述、算法时间度分析、算法实现