【CODEMATE】进制转换（transform） 粤港澳青少年信息学创新大赛 C/C++/Python 解题思路

问题描述

知识点：字符串 位运算  难度值：3  尝试：15  AC：5  上传者：_Separation

  题目背景：

  码上学习工作室 CSP - J 月赛 A 题

  十六进制是一种基数为 ‘16’ 的计数系统，使用数字 ‘0’ 到 ‘9’ 和字母 ‘A’ 到 ‘F’ 来表示数值。在这种系统中，逢 ‘16’ 进 ‘1’，‘A ~ F’ 代表 ‘10 ~ 15’ 。

  问题描述:

  给定一个正整数 n 和一个有 4n 位的二进制数（不保证没有前导零）

  请你求出，该二进制数转化为十六进制表示后共有多少个 ‘A’ 。

  输入输出格式:

  Input

  输入两行。

  第一行输入一个正整数 n 。

  第二行输入一个只由 ‘01’ 构成的 4n 位二进制数，不保证没有前导零。

  Output

  输出一行。

  行输出一个整数，表示输入的二进制数用十六进制表示时 ‘A’ 的个数。

  输入输出样例:

  输入数据 1

3
101010111100

  输出数据 1

1

  【样例 ‘1’ 解释】：该二进制数用十六进制表示为 ‘ABC’ ，其中有一个 ‘A’ 。

  输入数据 2

10
1111111111111110000000000000001110001101

  输出数据 2

0

  数据范围与提示：

  对于前 20% 的数据，保证 n = 1

  对于前 40% 的数据，保证 n ≤ 10

  对于前 60% 的数据，保证 n ≤ 10³

  对于 100% 的数据，保证 1 ≤ n ≤ 10⁶

---

  
  

做题思路，解决过程

  通过读题可以得知：

  题目至少需要 3 个变量，分别是：输入变量正整数 n 、长度为 4n 的字符串 str（只有01构成的的二进制字符串）、输出变量 num （str 转换成十六进制表示时 ‘A’ 的个数）。

思路：

  第一步：先将二进制串 str 按间距为 4 切片（4 位二进制可以表示 1 位十六进制），如将输入数据 1 ：101010111100，切成 1010 、 1011 、 1100。第二步：由题目得知需要求 ‘A’ 的个数，由于所求 ‘A’ 是个固定值（‘A’ 二进制为 1010 、十进制为 10 、十六进制为 ‘A’），所以直接判断 str 切片里是否有 ‘A’ 的二进制值即可。

踩过的坑：

  一开始看到题目我想着先将二进制串 str 转换为十六进制串，再判断十六进制串里有多少个 ‘A’，如果用这种方法又涉及到不同进制间转换，python 里倒是有方法可以实现，但是放到 C/C++ 里就需要自己写方法函数，走弯路了。

  后来反思为什么会出现这种思路，由于常规思考都是线性的，所以理所当然会按照解决问题的过程一步一步去构思代码（面向过程），在比赛面对算法题时，时间是有限的，输入输出也是有限的，我们只需要将输入输出对应起来即可，所以思考时需要更抽象、抓住问题本质（抽象、黑盒测试、面向对象）。

  还有一点就是题目里说的：“第二行输入一个只由 ‘01’ 构成的 4n 位二进制数，不保证没有前导零。”，还好题目说的是“不保证没有前导零”，意思是会有前导零，使二进制串的长度为 4n。如果题目改成“没有前导零”，那就麻烦一点，需要先判断补多少个前导零，再切片。虽然题目有说输入字符串长度为 4n，但是咱们做题得会举一反三，多点想法是有利于自己的，注意做题思路别被想法带偏了。

核心代码

  1. 将字符串按间距 4 切片

  2. 对 ‘A’ 数量的判断：

C 语言 / C++ 切片：

  利用循环，按 4 为增量做循环，直到遍历数组即可。

int n;	//定义变量 nscanf("%d", &n);	//获取 n 的值
//也可以写成：
//cin >> n;	// C++ 的输入函数char str[n*4];	//定义二进制数组 strscanf("%s", str);	//获取二进制数组值
//cin >> str;//切片
for(int i=0, j=0; i<n*4; i+=4, j++ )
{printf("第 %d 次切片：", j);	//cout << "第 " << j << " 次切片";printf("%c", str[i]);printf("%c", str[i+1]);printf("%c", str[i+2]);printf("%c\n", str[i+3]);
}

---

  
  

  C语言 / C++ 切片运行结果

---

  
  

C 语言 / C++ 判断 ‘A’ 数量：

  稍加修改切片循环的代码，将打印切片的代码换成判断代码即可。

  判断 ‘A’ 的方法有很多种，作者提供两种思路：

  1.按 4 位二进制分成一组，判断是否为 ‘1010’。

  2.将四位二进制分成一组，判断其十进制值是否为 10。

//在切片循环代码的基础上修改
// 方法 1
int num_A=0;
for(int i=0; i<n*4; i+=4)
{if(str[i]!='1')continue;	//如果不符合 'A' 的二进制，则直接寻址下 4 位，节省时间else if(str[i+1]!='0')continue;else if(str[i+2]!='1')continue;else if(str[i+3]!='0')continue;elsenum_A++;/**也可以将循环内代码写成：if(s[i]=='1' && s[i+1]=='0' && s[i+2]=='1' && s[i+3]=='0')num_A++;*/
}printf("%d", num_A);// 方法 2
/**
int num_A=0;// 将字符 ‘1’ 或 ‘0’ 转换成整数 1 或 0
for(i=0;i<n*4;i++)
{str[i]-='0';
}// 4 位二进制为一组，转换成十进制数
for(i=0; i<n*4-3; i+=4)
{	num=bin[i]*8 + bin[i+1]*4 + bin[i+2]*2 + bin[i+3];if(num==10){num_A+=1;}
}printf("%d", num_A);
*/

---

  
  

  C 语言 / C++ 判断 ‘A’ 数量运行结果

---

  
  

Python 切片：

  Python 的切片语句是：序列[start:stop:step]，序列可以是字符串、列表、元组等； start:stop 表示切片起点和终点； step 表示步长，由于切片都是在元素的左边切一刀，这就导致切片 1 序列[0:4] 实际值是 序列[0:3] ，轮到下一个切片 2 序列[4:8] ， 切片 1 的结束下标 3 与切片 2 的起点下标的差值就是 step 。

n=int(input())
str=input()# 利用循环语句切片
for i in range(0, len(str), 4): print(str[i:i+4])

---

  
  

  Python 切片运行结果

---

  
  

Python 判断 ‘A’ 数量：

  判断代码也是在切片的基础上稍加修改，加入变量 num_A 记录 ‘A’ 的个数。由于 Python 里没有自增自减的运算，所以用 += 代替 ++。

n=int(input())
str=input()
num_A=0;# 利用循环语句切片
for i in range(0, len(str), 4): if(str[i:i+4]=="1010")num_A+=1;print(num_A)

---

  
  

  Python 判断 ‘A’ 数量运行结果：

---

  
  

完整代码

C 语言 完整代码

#include <stdio.h>int main()
{int n, num_A=0;	//定义变量 n 、变量 num_Ascanf("%d", &n);	//获取 n 的值char str[n*4];	//定义二进制数组 strscanf("%s", str);	//获取二进制数组值//判断 ‘A’ 数量for(int i=0; i<n*4; i+=4){if(str[i]!='1')continue;	//如果不符合 'A' 的二进制，则直接寻址下 4 位，节省时间else if(str[i+1]!='0')continue;else if(str[i+2]!='1')continue;else if(str[i+3]!='0')continue;elsenum_A++;}printf("%d", num_A);
}

---

  
  

C++ 完整代码

#include <iostream>using namespace std;int main()
{int n, num_A=0;	//定义变量 n 、变量 num_Acin >> n;	//获取 n 的值char str[n*4];	//定义二进制数组 strcin >> str;	//获取二进制数组值//判断 ‘A’ 数量for(int i=0; i<n*4; i+=4){if(str[i]!='1')continue;	//如果不符合 'A' 的二进制，则直接寻址下 4 位，节省时间else if(str[i+1]!='0')continue;else if(str[i+2]!='1')continue;else if(str[i+3]!='0')continue;elsenum_A++;}cout << num_A;
}

---

  
  

Python 完整代码

n=int(input())
str=input()
num_A=0# 利用循环语句切片
for i in range(0, len(str), 4): # 从这里可以看出 n 的数值不影响 str 的输入if(str[i:i+4]=="1010"):num_A+=1# 输出 "A" 的个数
print(num_A)

---

  
  

评测结果

C语言

---

  
  

C++

---

  
  

Python

---

  
  

后记

  通过评测结果可以看出 Python 的代码虽然短，但在耗时、内存占用上远远比不上 C/C++，这也是为什么尽管各大语言兴起，也无法撼动 C/C++ 基石，经典经久不衰是有其道理的。

  这篇文章花了很长时间打磨，从读题、解题再到优化，回顾这一过程也可以说是自己进步的过程，不积硅步无以至千里，不积小流无以成江海，冲！