如何确定数字可以分解为较小数字的总和的方式

Question

我的朋友给了我这个问题他在接受采访时被问到他无法回答.经过几个小时的思考,我们无法提出解决方案.

考虑一下三号.我需要编写一个程序来计算不同的方式,你可以将数字写为小于数字的数字之和.

例如:

如果数字是2,它可以写成sum(1,1)

如果数字是3,它可以写成sum(1,1,1),sum(1,2),sum(2,1)

如果数字是4,它可以写成sum(1,1,1,1),sum(1,3),sum(3,1),sum(1,2,1),sum(2,1) ,1),总和(1,1,2),总和(2,2).7种不同的方式

如果数字是5,它可以写成sum(1,1,1,1,1),sum(1,1,1,2),sum(1,1,2,1),sum(1, 2,1,1),总和(2,1,1,1)等

如何编写程序来确定数字可以分解为较小数字的总和的方式

如果使用http://www.programminglogic.com/integer-partition-algorithm/中的算法将sum(1,2)和sum(2,1)视为等效,我能够找到解决问题的方法.

但问题是总和(1,2)和总和(2,1)是不同的.我根本看不到这样做的模式.

任何帮助,将不胜感激.我只是想知道解决方案.

Answer 1

将数字视为一条点线:

4     -> . . . .

在两个相邻的点之间,我们可以放一个墙来将数字分成更小的数字:

1+3   -> .|. . .
2+2   -> . .|. .
1+2+1 -> .|. .|.

对于每一个n-1空白,我们都可以选择是否设置墙,以实现各种2^(n-1)可能性.然而,没有墙只留下我们只有数字,这是不允许的,所以我们删除它作为最终总2^(n-1)-1解决方案的可能性.

Answer 2

这是解决这个问题的一个简单的递归方程：-

 F(N) = (F(N-1)+1) + (F(N-2)+1) + F(N-3)...........F(1)+1
 F(2) = 1
 F(1) = 0
 F(N-1) = (F(N-2)+1) + F(N-3)...........F(1)+1 
 F(N) = F(N-1)  + F(N-1) + 1
 F(N) = 2*F(N-1) + 1

解方程：

 F(N) = 2^(N-2) + 2^(N-2) - 1
      = 2^(N-1) - 1