Q22： 不缠绕的纸杯电话
笔者为一名南京大学在校本科生，目前是一名算法的初学者。去年冬天购买此书，希望借此提高编程水平。《程序员的算法趣题》这本书由日本大牛增井敏克所作，从算法学习者角度来讲，此书存在一些争议，全书的题目并不是严格的算法题，没有规范的输入输出格式，也没有标注数据范围（因此被我那个搞ACM的室友嗤之以鼻）。但虽然如此书中的题目还是很有趣的，加上了现实背景也显得很有实用性，难度也是渐进增强，没有很强的编程基础与算法问题很难将题目做出来。由于自己比较菜，如今做到现在22题就感觉题目有点难了。今日在做Q22这道题时笔者耗时良久而无果，观看书中给的答案也是一头雾水，在网上搜寻了大量资料进行总结汇总后才将此问题解决。由此心中十分感激那些愿意在网上分享自己学习经验的大佬们，希望自己也能分享一下自己的解题经验，供大家参考。
题目描述：
题目分析：
这个问题一眼看上去非常简单，题目描述也很清楚，简化一点来说就是在一个圆周上有2n个点将其两两相连而不相交的情况一共有多少种。其实OJ上有一摸一样的题目，经常刷OJ的人可能轻易就能看出来这不就是一个卡特兰数的问题吗。而笔者由于薄弱的数学功底与浅薄的编程经验在做此题并不了解卡特兰数也是查阅了相关资料才得知。如有同样不了解科特兰数的小伙伴们可以点击下面的传送门：
卡特兰数是组合数学里的一个重要概念，其应用也是相当广泛。总结来说就是两个公式：
1、递归公式：h(n) = h(1)*h(n-1) + h(2)*h(n-2) + ... + h(n-1)h(1)，n>=2
2、一般公式是：h(n)=C(2n,n)/(n+1)
希望大家能通过矮人排列和出栈次序这两个典型的卡特兰数的应用搞清楚卡特兰数递归公式的由来（一般公式可以由第一个传送门中所讲的直观理解，也可以通过复杂推演由递推公式得到，但这对解这道题可能没有太大意义）。如果看完尚不理解没关系，我讲给你听（滑稽.jpg）。在出栈次序问题中一旦出现栈为空的情况（假设此时共有k个数出栈），对于后面那n-k个尚未入栈的数完全就是一个子问题即h(n-k)，而对前面那k个数如果我们去掉第k个数不谈（根据栈后入先出的原则，这个数其实就是第一个入栈的数，仔细体会），而出栈后栈为空的情况可能发生在这n个元素中的任意一个。因此我们就得到了卡特兰数的递归公式。或许你已经看过书中为本题给出的答案，短短几行，其实就是卡特兰数的递归表达式。然而我相信此刻绝大部分人最为不解的就是：这道题的卡特兰数递推关系是怎么来的呢？（请好好思考一下再看下面的讲解哈）
解决递归问题最关键的步骤就是划分子问题，也就是书中所说的划分范围，出栈次序问题的划分是借助于栈为空这一情形，而本题的划分就是将两个点连线将圆划分成两个部分。递归表达式的由来我们可以这样理解：首先选择一个点，然后从与其相邻的一点遍历到相邻的另一点，将两点连线划分，然后分开的两个部分的点各自在其所属部分内组对，因为要确保各自部分的点能够组对，其个数必须为偶数，因此前面在遍历点时要注意每次遍历跳过一个点，即步长设为二。
题目解决：
下面给出代码
import java.util.Scanner;
/**
* 不缠绕的纸杯电话
* 卡特兰数的应用
* @author zbc
*
*/
public class Q22 {
static long[] pair; //用于动态规划优化的做法
public static void main(String[] args) {
Scanner sc = new Scanner(System.in); //有几对小朋友
int n = sc.nextInt();
sc.close();
System.out.println(getAns1(n));
System.out.println(getAns(n));
}
//递归解法
private static long getAns(int n) {
if(n == 0) {
return 1l;
}
long sum = 0;
for(int i = 0; i < n; i++) {
sum += getAns(i)*getAns(n-i-1);
}
return sum;
}
//动态规划优化
private static long getAns1(int n) {
pair = new long[n+1];
pair[0] = 1;
for(int i = 1; i < pair.length; i++) {
for(int j = 0; j < i; j++) {
pair[i] += pair[j]*pair[i-j-1];
}
}
return pair[n];
}
}
递归解法中要重复不断计算低位情形因此效率远远不如动态规划解法，此外由于卡特兰数增长率特别大，因此推荐大家结果用java内置的BigInteger表示。好啦，今天的分享就到这里啦（话说第一次写写的我好辛苦的说）。总之还是希望能给大家在学习过程中帮上一些忙吧，无论是正在学习这本书的人还是其他碰到类似问题的人。如果大家有什么见解或是什么疑惑，欢迎评论哦。后续待更。。。
网友评论