小学拆解数字题C语言里看不懂!动态规划求解C语言拆解方法个数
题目描述
3 = 2+1 = 1+1+1 所以3有三种拆法
4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1 共五种
5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1 共七种
依此类推,请问一个指定数字NUM的拆解方法个数有多少个?
解法分析
我们以上例中最后一个数字5的拆解为例,假设f( n )为数字n的可拆解方式个数,而f(x, y)为使 用y以下的数字来拆解x的方法个数,则观察:
5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1
使用函式来表示的话: f(5) = f(4, 1) + f(3,2) + f(2,3) + f(1,4) + f(0,5)
其中f(1, 4) = f(1, 3) + f(1, 2) + f(1, 1),但是使用大于1的数字来拆解1没有意义,所以f(1, 4) = f(1, 1),而同样的,f(0, 5)会等于f(0, 0),所以: f(5) = f(4, 1) + f(3,2) + f(2,3) + f(1,1) + f(0,0)
依照以上的说明,使用动态规划(Dynamicprogramming)来进行求解,其中f(4,1)其实就 是f(5-1, min(5-1,1)),f(x, y)就等于f(n-y, min(n-x,y)),其中n为要拆解的数字,而min()表示取两 者中较小的数。
使用一个二维阵列表格table[x][y]来表示f(x, y),刚开始时,将每列的索引0与索引1元素值设定 为1,因为任何数以0以下的数拆解必只有1种,而任何数以1以下的数拆解也必只有1种: for(i = 0; i < NUM +1; i++){ table[i][0] = 1; // 任何数以0以下的数拆解必只有1种 table[i][1] = 1; // 任何数以1以下的数拆解必只有1种 }
接下来就开始一个一个进行拆解了,如果数字为NUM,则我们的阵列维度大小必须为NUM x (NUM/2+1),以数字10为例,其维度为10 x 6我们的表格将会如下所示:
实操代码
准备操作:无实际意义
初始化+动态规划
计算结果以及收尾
更多精彩
閱讀更多 C語言源代碼計劃 的文章