一、题目背景
本题为2021年省赛填空题
- C/C++A组第1题
- C/C++B组第2题
- Java B组第2题
- Java B组第3题
- Python组第1题
二、题目描述
小蓝有很多数字卡片，每张卡片上都是数字 0 到 9。
小蓝准备用这些卡片来拼一些数，他想从 1 开始拼出正整数，每拼一个就保存起来，卡片就不能用来拼其它数了。小蓝想知道自己能从 1 拼到多少。例如，当小蓝有 30 张卡片，其中 0到9各3 张，则小蓝可以拼出 1到 10。但是拼 11 时卡片 1 已经只有一张了，不够拼出 11。
现在小蓝手里有 0到9 的卡片各 2021 张，共 20210 张，请问小蓝可以从 1拼到多少?
提示:建议使用计算机编程解决问题。
三、题目分析
本题是一道非常典型的基础枚举题。想求出最多拼到多少，那就从1开始一直往后枚举，枚举的过程中检查这个数是不是符合条件，如果符合卡片条件就继续枚举，直到不符合条件为止（卡片不够了）。
所以这道题的核心就转到了 如何检查 上。
1.检查思路
我们可以申请一个下标分别从0到9的数组，对应卡片从0~9，让每一个数组的值都为卡牌的总数量大小：2021。
然后通过取余的方式，将每一位对应的数字求出来，然后看看这些对应位置的数的数量是不是符合卡牌的数量。
取余求每个位置的数 ：
例如： 求189的每一位数的大小
个位：189%10 = 9
十位：（189/10）%10 = 8
百位：（189/10/10）%10 = 1
下面我用C语言写一下这段起检查作用的函数
#include<stdio.h>
int card[10]; // （1）
int check(int num) // （2）
{
while (num)
{
int a = num % 10; //（3）
if (card[a] > 0) //（4）
card[a]--; //（5）
else
return 0; //（6）
num = num / 10; //（7）
}
return 1;
}- （1）申请下标分别从0到9的数组，用来存卡片
- （2）num表示需要检查的数
- （3）求每一位的数是多少
- （4）判断这个数对应的卡牌还有没有
- （5）如果有，就符合要求，但是用过了这张卡牌所以减一
- （6）如果没有，就不符合要求
- （7）改变位数（将百位变为十位，十位变为个位......）
2.思路优化
上面的思路，其实已经能够完成检查的任务，但是如果仔细想想，其实枚举是从1开始，那么消耗卡片1的数量是最多的。卡片1的数量是最先小于0，所以我们只需要检查卡片1的数量就可以了。
下面我用C语言写一下优化后的函数
#include<stdio.h>
int card[10];
int check(int num)
{
while (num)
{
int a = num % 10; //（1）
if (a == 1) //（2）
if (card[1] == 0) //（3）
return 0;
else
card[1]--; //（4）
num = num / 10; //（5）
}
return 1;
}- （1）求每一位的数是多少
- （2）如果这一位是1
- （3）如果卡牌1的数量等于0，结束检查
- （4）如果不为0，卡牌1的数量减一
- （5）改变位数（将百位变为十位，十位变为个位......）
四、代码汇总
1.C语言代码
C语言里面没有bool类型，但是C语言中0代表假，非0代表真。
#include<stdio.h>
int card[10];
int check(int num)
{
while (num)
{
int a = num % 10;
if (a == 1)
if (card[1] == 0)
return 0;
else
card[1]--;
num = num / 10;
}
return 1;
}
int main()
{
for (int i = 0; i <= 9; i++)
card[i] = 2021; //(1)
for (int i = 1;check(i); i++) //(2)
{
printf("%d\n", i ); //(3)
}
return 0;
}（1）循环，让每个卡牌的数量都为2021个
（2）逐个枚举检查
（3）输出符合的正确的结果
2. C++代码
C++代码和C语言代码大致差不多，不同的是C++里面有bool类型。
当然printf也可也用c++里面的cout代替
cout不需要记太多的占位符，更加方便。
#include<iostream>
using namespace std;
int card[10];
bool check(int num)
{
while (num)
{
int a = num % 10;
if (a == 1)
if (card[1] == 0)
return false;
else
card[1]--;
num = num / 10;
}
return true;
}
int main()
{
for (int i = 0; i <= 9; i++)
{
card[i] = 2021;
}
for (int i = 1;check(i); i++)
{
cout << i << endl;
}
return 0;
}3.运行结果
| 以下为代码的运行结果。 |
故最终答案为：3181
五、总结
1.枚举思想
枚举就是是从问题所有可能的解的集合中一一枚举出各种元素。
并且用题目中给定的检验条件判定哪些元素是错误的，哪些是正确的。
2.取余求位数
取余求各个位数是常用的基本功。
不管是几位数个位数都可以直接使用 数 % 10 来取余数获得
至于获取十位数，百位数，只需要处于10或100再进行取余即可获得。
