[问答题]
#include <iostream>
#include <vector>
#include <cstdlib>
#include <cstdio>
using namespace std;
int nums[3] = {1,2,5};
int combine(int n) {
if (n < 0) return 0;
vector<int> f(n+1, 1);
int size = sizeof(nums)/sizeof(int);
for (int i = 1; i < size; i++) {
for (int j = nums[i]; j <= n; j++) {
f[j] += f[j - nums[i]];
}
}
return f.back();
}
int main(int argc, char **argv) {
printf("%d\n", combine(100));
return 0;
}
编辑于 2015-07-08 11:41:59
回复(0)
void Sum100(){
int nu1=0;
int nu2=0;
int nu5=0;
int count=0;
for(nu5=0;nu<21;nu++){
for(nu2=0;nu2<51;nu2++){
for(nu1=0;nu1<101;nu1++){
if(nu1+nu2*2+nu5*5==100{
if(nu1!=0){
printf("%d*1+",nu1);
}
if(nu2!=0 && nu5!=0){
printf("%d*2+%d*5",nu2,nu5);
}
else if(nu2!=0 && nu5==0){
printf("%d*2",nu2);
}
else if(nu2==0 && nu5!=0){
printf("%d*5",nu5);
}
printf("=100\n");
count++;
}
}
}
}
printf("总的组合数为 %d\n",count);
}
发表于 2015-06-24 11:16:12
回复(0)
问题信息
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
A．答案：最容易想到的算法是：
设x是1的个数，y是2的个数，z是5的个数，number是组合数
注意到0<=x<=100，0<=y<=50，0<=z=20，所以可以编程为：
number=0; for (x=0; x<=100;x++) for (y=0; y<=50;y++) for (z=0; z<=20;z++) if ((x+2*y+5*z)==100) number++; cout<<number<<endl;上面这个程序一共要循环100*50*20次，效率实在是太低了
B．事实上，这个题目是一道明显的数学问题，而不是单纯的编程问题。我的解法如下：
因为x+2y+5z=100
所以x+2y=100-5z，且z<=20 x<=100 y<=50
所以(x+2y)<=100，且(x+5z)是偶数
对z作循环，求x的可能值如下：
因此，组合总数为100以内的偶数+95以内的奇数+90以内的偶数+...+5以内的奇数+1，
即为：
(51+48)+(46+43)+(41+38)+(36+33)+(31+28)+(26+23)+(21+18)+(16+13)+(11+8)+(6+3)+1
某个偶数m以内的偶数个数（包括0）可以表示为m/2+1=(m+2)/2
某个奇数m以内的奇数个数也可以表示为(m+2)/2
所以，求总的组合次数可以编程为：
number=0; for (int m=0;m<=100;m+=5) { number+=(m+2)/2; } count << number << endl;
这个程序,只需要循环21次, 两个变量，就可以得到答案,比上面的那个程序高效了许多
倍----只是因为作了一些简单的数学分析。