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. 给出题解

全部评论

相关推荐

头像
今天 14:28
长沙理工大学
刷算法真的是提升代码能力最快的方法吗?&nbsp;刷算法真的是提升代码能力最快的方法吗?
牛牛不会牛泪:看你想提升什么,代码能力太宽泛了,是想提升算法能力还是工程能力? 工程能力做项目找实习,算法也分数据结构算法题和深度学习之类算法
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务