本帖最后由 业余的业余 于 2019-2-10 01:56 编辑
回复 1# lrh2006
后来查了一下,这个才是所谓的堆垒数论问题,和丢番图方程有某种联系。我只有题和解,没有书,所以也搞不懂堆垒数论怎么玩。
不过这个问题用编程的思路来接,却是必杀,而且其算法可以简单地套用到纸笔求解。
关键词: 动态规划算法。
这个算法的思路我就不介绍了,本质上要递归地表达问题的解。动态规划是用于合并相同的子问题,从而减少计算工作量。不要小看这个减少,很多时候它是把一个指数/阶乘复杂度的问题降低为一个多项式复杂度的问题,从几乎不可解到可轻松求解。
我们把 正整数 $ n $, 分解为 从 $ k $ 开始, 不大于$ 999 $ 的若干个整数项(允许重复项)的和的方法的个数记为 $ P(n,k) $. 那么显然,你的问题就是找 $ P(1000,1) $.
第一步,我们可以先选定不同个数的$1$, 然后要求剩下的数用$2-999$的项来分解,所以
$\begin{align} \begin{aligned}P(1000,1)=&P(999,2)& \text{取了1个1 ,剩下的交给2和以上的去分割}\\
+&P(998,2) & \text{ 取了2个1, 剩下的交给2和以上的去分割}\\
&\vdots \\
+&P(2,2)&\text{ 取了998个1, 剩下的交给2和以上的去分割}\\
+&1&\text{ 全部取1}\end{aligned}\end{align} $
然后 $ P(999,2), P(998,2), \cdots $ 等可以递归的类似求解。用一个小一点的数,比如 $ 5 $, 在纸上比划下就明白了,用大体 $ 5\times 5 $ 的表格,注意求解的顺序。
我不知道用堆垒数论的方法与之相比,更优雅到何种程度,因为不会。这个问题用电脑就是毫秒级问题,时间和空间复杂度都是 $ O(n^2) $, 用纸笔算还费点事,关键很 boring.
---
PS: 这个算法的描述是有问题的。参考后面的程序。具体而言,上面的主要错误有2
1. P(n,k) 定义为 把 n 用 k...n 的任意多个正整数分解的不同式子的个数。(n 包含在 可能的项之中);
2. 要允许选择0个 k 的情形,上面漏掉了。参后面的程序。 |