Kotlin面试算法：组合1、2、5，和为100

【出自HW面试题】

难度系数：★★★★☆ 被考察系数：★★★★☆

题目描述：

求出用1、2和5这三个数不同个数组合的和为100的组合个数。为了更好地理解题目的意思，下面给出几组可能的组合：100个1、0个2和0个5，它们的和为100；50个1、25个2和0个5的和也是100；50个1、20个2和2个5的和也为100。

分析与解答：

方法一：蛮力法

最简单的方法就是对所有的组合进行尝试，然后判断组合的结果是否满足和为100，这些组合有如下限制：1的个数最多为100个，2的个数最多为50个，5的个数最多为20个。实现思路是：遍历所有可能的组合1的个数x（0＜=x＜=100），2的个数y（0=＜y＜=50），5的个数z（0＜=z＜=20），判断x+2y+5z是否等于100，如果相等，则满足条件，实现代码如下：

程序的运行结果如下：

541

算法性能分析：

这种方法循环的次数为101*51*21。

方法二：数字规律法(www.xing528.com)

针对这种数学公式的运算，一般都可以通过找出运算的规律进而简化运算的过程，对于本题而言，对x+2y+5z=100进行变换可以得到x+5z=100-2y。从这个表达式可以看出，x+5z是偶数且x+5z＜=100。因此，求满足x+2y+5z=100组合的个数就可以转换为求满足“x+5z是偶数且x+5z＜=100”的个数。可以通过对z的所有可能的取值（0＜=z＜=20）进行遍历从而计算满足条件的x的值。

当z=0时，x的取值为0，2，4，，100（100以内所有的偶数），个数为（100+2）/2

当z=1时，x的取值为1，3，5，，95（95以内所有的奇数），个数为（95+2）/2

当z=2时，x的取值为0，2，4，，90（90以内所有的偶数），个数为（90+2）/2

当z=3时，x的取值为1，3，5，，85（85以内所有的奇数），个数为（85+2）/2

……

当z=19时，x的取值为5，3，1（5以内所有的奇数），个数为（5+2）/2

当z=20时，x的取值为0（0以内所有的偶数），个数为（0+2）/2

根据这个思路，实现代码如下：

算法性能分析：

这种方法循环的次数为21。