「PAT乙级真题解析」Basic Level 1023 组个最小数 (问题分析+完整步骤+伪代码描述+提交通过代码)
题目给的要求很明确, 给定若干数字, 要求输出排列组合组成的数中值最小的数。 只要知道如何组合出值最小的数, 就可以按照步骤组合出最小的数, 也就解决了问题。
#算法#数据结构#pat考试#c语言#需求分析
Table of Contents
乙级的题目训练主要用来熟悉编程语言的语法和形成良好的编码习惯和编码规范。从小白开始逐步掌握用编程解决问题。
问题分析
题目给的要求很明确, 给定若干数字, 要求输出排列组合组成的数中值最小的数。 只要知道如何组合出值最小的数, 就可以按照步骤组合出最小的数, 也就解决了问题。
值最小的数
尽量在高位放置值小的数字, 最后得到的数值就会最小。 考虑到0不能在首位, 所以首位需要特殊处理: 放置1-9中能放置的最小数字 其他数字从小到大排序,然后依次从左到右放置在各个数位上, 得到的数就是最小数. 比如题目样例: 2个0, 2个1, 3个5, 1个8.
- 选出非0的最小数字: 1
- 其他数字从小到大排序: 0015558
- 两部分组合起来: 10015558
完整描述步骤
- 统计各个数字在输入数据中出现的频率
- 选出非零的最小数字
- 排序其他数字
- 将数字最小到大接在最小数字后面
伪代码描述步骤
- get input
- count each digit frequency
- select minial digit
- sort rest digits
- if stored in array, sorting is not necessary
- put digits behind the minial digit selected previously
- if stored in array, for digit in frequency_counter:
- for (int i = 0; i < frequency; i++) print(digit)
- if stored in array, for digit in frequency_counter:
完整提交代码
/*
# 问题分析
题目给的要求很明确, 给定若干数字, 要求输出排列组合组成的数中值最小的数。
只要知道如何组合出值最小的数, 就可以按照步骤组合出最小的数, 也就解决了问题。
## 值最小的数
尽量在高位放置值小的数字, 最后得到的数值就会最小。
考虑到0不能在首位, 所以首位需要特殊处理: 放置1-9中能放置的最小数字
其他数字从小到大排序,然后依次从左到右放置在各个数位上, 得到的数就是最小数.
比如题目样例: 2个0, 2个1, 3个5, 1个8.
1. 选出非0的最小数字: 1
2. 其他数字从小到大排序: 0015558
3. 两部分组合起来: 10015558
# 完整描述步骤
1. 统计各个数字在输入数据中出现的频率
2. 选出非零的最小数字
3. 排序其他数字
4. 将数字最小到大接在最小数字后面
# 伪代码描述步骤
1. get input
2. count each digit frequency
3. select minial digit
4. sort rest digits
- if stored in array, sorting is not necessary
5. put digits behind the minial digit selected previously
- if stored in array, for digit in frequency_counter:
- for (int i = 0; i < frequency; i++) print(digit)
*/
int main(){
int digits_count[10];
for (int i =0; i< 10; i++){
scanf("%d", &digits_count[i]);
}
for (int i = 1; i< 10; i++){
if (digits_count[i] != 0){
printf("%d", i);
digits_count[i] --;
break;
}
}
for (int i = 0; i < 10; i++){
for (int j = 0; j < digits_count[i]; j ++){
printf("%d", i);
}
}
return 0;
}