22 枚举
理论说明
枚举是最简单也是最直白的搜索方式,它依次尝试搜索空间中所有的解,测试是否符合条件,若符合则输出答案,否则继续测试下一组解。 但是在使用枚举这种相对比较暴力的算法来解题时,我们对其时间复杂度要做特别的关注。枚举问题的时间复杂度往往需要与需要枚举的情况个数有关,因为我们必须不遗不漏的枚举每一种可能成为答案的情况。所以搜索空间越大,枚举的时间复杂度越高。所以,我们对某一问题进行枚举时,必须保证其时间复杂度在题目时限可以接收的范围内。
题目来源和说明
2009年哈尔滨工业大学计算机研究生机试真题
题目描述
用小于等于n元去买100只鸡,大鸡5元/只,小鸡3元/只,还有1/3元每只的一种小鸡,分别记为x只,y只,z只。编程求解x,y,z所有可能解。
输入说明
测试数据有多组,输入n
输出说明
对于每组输入,请输出x,y,z所有可行解,按照x,y,z依次增大的顺序输出。
样例展示
输入:
40
输出:
x=0,y=0,z=100
x=0,y=1,z=99
x=0,y=2,z=98
x=1,y=0,z=99
C++代码
#include<iostream>
using namespace std;
int n;
int main() {
while(scanf("%d",&n)!=EOF) {
for(int x=0;x<=100;x++) {
for(int y=0;y<=100-x;y++) {
int z=100-x-y;
if(x*5*3+y*3*3+z<=n*3) { //考虑到一只小小鸡的价格为1/3,为了避免除法带来的精度损失,这里采用了对不等式两端所有数字都乘3的操作,这也是避免除法的常用技巧
printf("x=%d,y=%d,z=%d\n",x,y,z);
}
}
}
}
return 0;
}
abc
设a、b、c均是0到9之间的数字,abc、bcc是两个三位数,且有:abc+bcc=532。求满足条件的所有a、b、c的值。
C++代码
#include<iostream>
using namespace std;
int main() {
int a,b,c;
for(a=1;a<=9;a++) {
for(b=1;b<=9;b++) {
for(c=0;c<=9;c++) {
if(a*100+b*10+c+b*100+c*10+c == 532) {
printf("%d %d %d\n",a,b,c);
}
}
}
}
return 0;
}
Old Bill
C++代码
高校夏令营机试训练 文章被收录于专栏
Leetcode题目太多,不知道如何准备高校夏令营?欢迎关注本专栏,和本小白一起准备夏令营吧! 本专题的规划如下: 截止到4月下旬:以王道考研为依托,提供夏令营机考的准备计划,打好基础 截止到5月中旬:以剑指offer进一步加强 本专题的内容如下: 1. 给出题目的在线测试链接,方面您检查代码的正确性 2. 给出题解