华为薪酬组成面试2：1分2分5分的硬币，组成1角，共有多

来源：蜘蛛抓取(WebSpider) 时间：2018-04-14 04:33 标签： 华为部门组成
动态规划，注意不要有重复的，例如组成1角钱，5 2 2 1 和 1 2 2 5是1种组合
算法的设计思想在程序中注释的很清楚。
// 动态规划
// total_money: 要找的零钱总和
// changes: 零钱数组，已经从小到大排序，第1个元素设为0，有效元素从第2个位置即下标1开始
// kinds_change: 零钱种类
int make_change_problem(int total_money, int *changes, int kinds_change)
// opt[i][j]表示用前j种零钱组成i元钱的组合数目，第j种零钱的数目可以为0
boost::multi_array&int, 2& opt(boost::extents[total_money+1][kinds_change+1]);
// 组成0元钱的组合数目只有1种，即不选择任何零钱
for (j = 0; j &= kinds_ ++j)
opt[i][j] = 1;
// 用0种零钱组成i(1&=i&=total_money)元钱的组合数目是0
for (i = 1; i &= total_ ++i)
opt[i][j] = 0;
for (i = 1; i &= total_ ++i)
for (j = 1; j &= kinds_ ++j)
opt[i][j] = 0;
int K = i / changes[j]; // 第j种零钱的最大数目
for (int k = 0; k &= K; ++k)
opt[i][j] += opt[i-k*changes[j]][j-1];
return opt[total_money][kinds_change];
int main(int argc, char **argv)
int total_money = 10;
int changes[] = {0, 1, 2, 5};
int kinds_change = sizeof(changes) / sizeof(int) - 1;
number = make_change_problem(total_money, changes, kinds_change);
cout && number &&
// total_money: 要找的零钱总和
// changes: 零钱数组，已经从小到大排序，第1个元素设为0，有效元素从第2个位置即下标1开始
// kinds_change: 零钱种类
int make_change_problem_v2(int total_money, int *changes, int kinds_change)
// opt[i]表示i元钱的组合数目
std::vector&int& opt(total_money+1, 0);
// 组成0元钱的组合数目只有1种，即不选择任何零钱
opt[0] = 1;
// 第一个循环计算包含第i种零钱时j元钱的组合数目，第二个循环计算j(j&=changes[i])元钱的组合数目
for (int i = 1; i &= kinds_ ++i)
for (int j = changes[i]; j &= total_ ++j)
opt[j] += opt[j-changes[i]];
return opt[total_money];
浏览: 239631 次
哪个写的DateAdd方法，写得太臭了，还有BUG，时间到了1 ...
楼主需要的其实是一个前端模板库，做到html代码与数据分离，这 ...
java 跟 jsp 代码分离，你有好的想法么？
不错，挺好的，&script type=&te ...
(window.slotbydup=window.slotbydup || []).push({
id: '4773203',
container: s,
size: '200,200',
display: 'inlay-fix' 上传我的文档
 下载
 收藏
粉丝量：53
该文档贡献者很忙，什么也没留下。
 下载此文档
C语言之华为面试2：1分2分5分的硬币，组成1角，共有多少种组合。
下载积分：30
内容提示：C语言之华为面试2：1分2分5分的硬币，组成1角，共有多少种组合。
文档格式：PDF|
浏览次数：6|
上传日期： 10:26:59|
文档星级：
全文阅读已结束，如果下载本文需要使用
 30 积分
下载此文档
该用户还上传了这些文档
C语言之华为面试2：1分2分5分的硬币，组成1角，共有多少种
关注微信公众号posts - 353,&
comments - 50,&
trackbacks - 0
设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+2)/2所以，求总的组合次数可以编程为：number=0;for (int m=0;m&=10;m+=5){number+=(m+2)/2;}cout&&number&&这样程序是不是简单多了（只需要累加3次，而上面的3层循环呢？大家自己想想）。别人考你肯定不是考你会不会编这个程序，是考你如何去使程序的复杂度降低。
6分、4分、2分组成100分怎么处理？
2分为x，4分为y，6分为z。则6*z=100-2*x-4*y，可化简为：3*z=50-x-2*yz可能的取值为0、1、2&&&16，当z=0时，x可以为50 48 46&&&2 0（26个）当z=1时，x可以为47 45 43&&&3 1（24个）当z=2时，x可以为44 42 40&&&2 0（23个）当z=3时，x可以为41 39 37&&&3 1（21个）&&&当z=15时，x可以为5 3 1（3个）当z=16时，x可以为2 0（2个）因此，按照规律，本题目组合总数为50以内的偶数+47以内的奇数+44以内的偶数+&&&+5以内的奇数+2以内的偶数某个偶数m以内的偶数个数（包括0）可以表示为m/2+1=(m+2)/2某个奇数m以内的奇数个数也可以表示为(m+2)/2所以，求总的组合次数可以编程为：number=0;for (int m=0;m&=50;m+=3){number+=(m+2)/2;}cout&&number&&是不是可以看出规律了呢？实际上就是看表达式（这里是3*z=50-x-2*y），就是把最大乘数（这里是3）放在一边，这也是m增加的步长。而m的最大取值也就是表达式中的这个常数。
当然这也是个典型的背包问题：
int dp[10+1];
int main()
int w[] = {1,2,5};
dp[0] = 1;
for(int i=0; i&3; i++){
for(int j=w[i]; j&=10; j++){
dp[j] += dp[j - w[i]];
printf("%d\n",dp[10]);
阅读(...) 评论()用足够多的 1 分，2 分和 5 分硬币凑出 1 元钱，一共有多少种方法？ - 知乎45被浏览<strong class="NumberBoard-itemValue" title="1分享邀请回答12添加评论分享收藏感谢收起NUM-OF-COMBINATIONS(n, k, v)
else if n & 0 or k &= 0
return NUM-OF-COMBINATIONS(n, k-1, v) + NUM-OF-COMBINATION(n-v[k], k, v)
用Java测试了一下，原问题的答案确实是541。这是我在知乎的处女答，如果有错漏的地方，还请大家指教。谢谢。2519 条评论分享收藏感谢收起下次自动登录
现在的位置:
& 综合 & 正文
华为面试题：1分2分5分的硬币，组成1角，共有多少种组合。 Java源代码
public class Jiaofen {
public static void main(String args[])
int i,j,k;
for(i=0;i&3;i++)
//五分的硬币最多2个
for(j=0;j&=(10-5*i)/2;j++)
//2分的硬币的个数最多为（100-5i）/2
for(k=0;k&=10-5*i-2*j;k++)
//1分的硬币的个数最多为100-5i-2j
if(10==5*i+2*j+k)
//注意是“==”
System.out.println("1分硬币的个数为："+k+";" +
"2分硬币的个数为："+j+
";5分硬币的个数为："+i);
System.out.println(n);
运行结果：
【上篇】【下篇】

我要回帖

更多关于 华为部门组成 的文章

 

随机推荐