加载中…
个人资料
老徐
老徐
  • 博客等级:
  • 博客积分:0
  • 博客访问:837,584
  • 关注人气:157
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
正文 字体大小:

解决1分2分5分硬币组合的数学问题

(2012-06-03 19:22:19)
标签:

硬币组合

面试

it

分类: Algorithm/DateStructure
问题的提出如下:1分2分5分的硬币,组成1角,共有多少种组合,如果是组成1块,又有多少种组合。

    这个问题看似很简单,答案为10种。但如果要真正去算,或者写程序来实现。想必大多数的人都会使用3层for循环来实现。即分别令i=0(表示1 分),j=0(表示2分),k=0(表示5分),然后循环条件为3者之和小于10,得出的结果为三者之和大于10。即实现算术 x+2y+5z=10,然后求x,y,z的组合。
    然而,问题在于提出的问题并没有问具体的组合方式,而是只问了究竟有多少种,那么如果再使用这种算法就有点得不偿失了。

*******************************************************************

设1分个数为x,2分个数为y,5分的硬币个数为z,则1*x+2*y+5*z=10;
5z=10-x-2*y;即:
z x
0 10 8 6 4 2 0
1 5 3 1
2 0
总共个数为6+3+1=10.


设1分个数为x,2分个数为y,5分的硬币个数为z,则1*x+2*y+5*z=10;
5*z=10-x-2*y;即:
z x对应可能的取值
0 10 8 6 4 2 0(6个)
1 5 3 1(3个)
2 0(1个)
总共个数为6+3+1=10.
因此,按照规律,本题目组合总数为10以内的偶数+5以内的奇数+0以内的偶数
某个偶数m以内的偶数个数(包括0)可以表示为m/2+1=(m+2)/2
某个奇数m以内的奇数个数也可以表示为(m+1)/2

*******************************************************************

 



0

阅读 收藏 喜欢 打印举报/Report
  

新浪BLOG意见反馈留言板 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

新浪公司 版权所有