7.6 如何组合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。
方法二：数字规律法
针对这种数学公式的运算，一般都可以通过找出运算的规律进而简化运算的过程，对于本题而言，对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。