用VBA解欧拉计划题目（76）--加和计数

grf1973

加和计数

将5写成整数的和有6种不同的方式：

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

将100写成整数的和有多少种不同的方式？

香川群子

16.145s 190569291

grf1973

结果正确。
这题和先前那道英镑凑数的题目是一个类型的。所以代码只要稍微改一下。
两个方法都是秒出结果。

1. '将100写成整数的和有多少种不同的方式？
   
2. Sub problem76()   '结果是  190569291  by GTR  用数组b组成最大N的组数，通用做法
   
3.     n = 100
   
4.     ReDim a(n)
   
5.     ReDim b(1 To n - 1)
   
6.     a(0) = 1
   
7.     For k = 1 To n - 1
   
8.         b(k) = k
   
9.     Next
   
10.     For j = UBound(b) To 1 Step -1
    
11.        For i = UBound(a) To 1 Step -1
    
12.           For k = 1 To i \ b(j)
    
13.               a(i) = a(i) + a(i - b(j) * k)
    
14.     Next k, i, j
    
15.     Debug.Print a(n)
    
16. End Sub
    
17. Sub problem76a()
    
18.     '记a(n,k)为将整数n拆分为k个正整数的方案数，则满足a(n, k) = a(n - 1, k - 1) + a(n - k, k)
    
19.     m = 100
    
20.     ReDim a(m, m)
    
21.     a(1, 1) = 1
    
22.     For n = 2 To m
    
23.         For k = 1 To n
    
24.             a(n, k) = a(n - 1, k - 1) + a(n - k, k)
    
25.         Next
    
26.     Next
    
27.     For k = 2 To m
    
28.         s = s + a(m, k)
    
29.     Next
    
30.     Debug.Print s
    
31. End Sub
    

复制代码

香川群子

grf1973 发表于 2017-12-4 14:19
结果正确。
这题和先前那道英镑凑数的题目是一个类型的。所以代码只要稍微改一下。
两个方法都是秒出结果 ...

你这个是动态规划算法了。效率很高的。