题目
一个连续乘法的算式，只考虑结合律，不考虑交换律，共有多少种计算方法？
例如：a*b*c*d，可以如a*b*(c*d)，a*(b*c)*d等
解析思路
递归实现。只考虑结合律，结合律就是将算式进行拆分，拆分为多个不同的子算式。首先将完整的算式拆分为两个独立的子算式，两个子算式分别计算有多少种计算方法，两个子算式结果相乘就是完整算式的有多少种计算方法。子算式再继续拆分为子子算式，直到子算式只剩下一个乘数，或者两个乘数，那么此时计算方法为1。
代码
//输入乘法算式乘数的个数
public int mulDistribution(int number){
//如果乘数个数小于等于0，返回0。
if (number <= 0){
return 0;
}
//如果乘数个数为1或2，返回1。
if (number < 3){
return 1;
}
//递归实现，每一个算式都拆分为两个子算式递归结果的乘积
int total = 0;
for (int i = 1; i < number; i++){
total = total + mulDistribution(i) * mulDistribution(number - i);
}
return total;
}
网友评论