lavos/cap3/ex6.go

package cap3

// Ex6Output 例六的带输出结果
func Ex6Output(num int, callback func(nums []int)) {
	Ex6RecursionOutput(num, callback)
}

// Ex6NoneOutput 例六的不带输出结果版本，只求数量
func Ex6NoneOutput(num int, algoType AlgoType, callback func(nums []int)) int {
	switch algoType {
	case AlgoTypeRecursion:
		return Ex6Recursion(num)
	default:
		return Ex6NoneRecursion(num)
	}
}

// Ex6Recursion 整数划分，递归写法，只计算结果，但对算法经过调整以适合输出
func Ex6Recursion(num int) int {
	count := 0
	var divider func(num, m int)
	divider = func(num, m int) {
		// num == 0 来源会有两种：递归中num==m，以及传入的num本身就是0，此时可以作为一个划分
		if num == 0 {
			count++
			return
		}

		// 最大划分大小m逐级-1求划分数
		if m > 1 {
			divider(num, m-1)
		}

		// m <= num，对剩余未加的数进行划分
		if m <= num {
			divider(num-m, m)
		}
	}

	divider(num, num)
	return count
}

// Ex6RecursionOutput 整数划分，由上面的递归写法修改而来，可求划分情况，对算法经过调整以适合输出
func Ex6RecursionOutput(num int, callback func(dividedNums []int)) {
	var divider func(num, m int, dividedNums []int, callback func(dividedNums []int))
	divider = func(num, m int, dividedNums []int, callback func(dividedNums []int)) {
		// num==0时，当前已划分完毕，回调输出
		if num == 0 {
			callback(dividedNums)
			return
		}

		// 最大划分大小m逐级-1求划分数
		if m > 1 {
			divider(num, m-1, dividedNums, callback)
		}

		if m <= num {
			// m <= num，对剩余未加的数进行划分，当前的m已经是划分中的一个成员，将其添加进dividedNums中
			divider(num-m, m, append(dividedNums, m), callback)
		}
	}

	divider(num, num, make([]int, 0, num), callback)
}

// Ex6NoneRecursion 整数划分，非递归写法，由递归法改写而来，模拟递归过程
func Ex6NoneRecursion(num int) int {
	divider := func(num, divideMax int) int {
		// 初始化
		result := make([][]int, num+1)
		for i := 0; i < num+1; i++ {
			result[i] = make([]int, num+1)
		}
		for i := 1; i <= num; i++ {
			result[0][i] = 1
		}

		// i从1开始到num进行划分计算，
		// 里层j从1开始到m（最大划分大小）开始计算子问题的划分
		// 从1开始，自底向上计算
		// 此处为非递归写法，当前的结果依赖上一个结果，因此需要先计算上一个结果，
		// 因此整个问题过程需要从最小的问题开始计算
		divideMax = min(num, divideMax)
		for n := 1; n <= num; n++ {
			for m := 1; m <= divideMax; m++ {
				if n <= m {
					// 对应 Q(n,n) = 1 + Q(n, n-1) 的情况
					// n < m (n < m) 时均看作i == m (n == m)
					result[n][m] = 1 + result[n][n-1]
				} else {
					// 对应 Q(n,m) = Q(n, m-1) + Q(n-m, m) 的情况
					result[n][m] = result[n][m-1] + result[n-m][m]
				}
			}
		}

		return result[num][divideMax]
	}

	return divider(num, num)
}