在信息编码中,两个二进制编码的对应位取值不同的数量称为这两个编码的海明距离。例如:10101和00110从第一位开始依次有第一位、第四、五位不同,则海明距离为3。 若两个二进制编码的每一位都不相同,则这两个编码产生了海明悬崖(Hamming Cliff)。例如,15的二进制编码为01111,16的二进制编码为10000,则产生“Hamming Cliff”。 任务:给你两个正整数,请你判断是否会产生“Hamming Cliff”。 输入格式: 输入数据的第一行为一个正整数T, 表示测试数据的组数。然后是T组测试数据(1<=T<=30)。 每组测试数据输入两个正整数n,m(1<=n<=2 31 -1)。 说明:若两个二进制编码长度不等,则在较短的编码前面添加前导0。 输出格式: 对于每组测试数据,若产生“Hamming Cliff”输出“Yes”,否则输出“No”。引号不必输出。 输入样例: 3 15 16 2 3 512 511 输出样例: Yes No Yes
时间: 2024-03-14 13:43:03 浏览: 215
二进制下的海明校验
以下是 Python3 代码实现:
```python
def hamming_cliff(n: int, m: int) -> bool:
"""
判断两个二进制编码是否产生 Hamming Cliff。
"""
# 将两个二进制编码转换为字符串
n_str = format(n, 'b')
m_str = format(m, 'b')
# 在较短的编码前面添加前导0,使得两个编码长度相等
max_len = max(len(n_str), len(m_str))
n_str = n_str.zfill(max_len)
m_str = m_str.zfill(max_len)
# 判断两个编码是否每一位都不相同
for i in range(max_len):
if n_str[i] == m_str[i]:
return False
return True
# 读入测试数据的组数
t = int(input())
for _ in range(t):
# 读入两个正整数
n, m = map(int, input().split())
# 判断是否产生 Hamming Cliff 并输出结果
if hamming_cliff(n, m):
print('Yes')
else:
print('No')
```
思路解析:
本题要求我们判断两个二进制编码是否产生 Hamming Cliff,即它们每一位都不相同。我们可以将两个二进制编码转换为字符串,然后在较短的编码前面添加前导0,使得两个编码长度相等,最后逐位比较它们是否相同即可。
具体实现时,我们可以先定义一个函数 `hamming_cliff(n, m)`,该函数接受两个正整数 `n` 和 `m`,返回一个布尔值,表示它们是否产生 Hamming Cliff。函数实现时,我们可以将两个二进制编码转换为字符串 `n_str` 和 `m_str`;然后,我们可以求出两个编码的最大长度 `max_len`,并在较短的编码前面添加前导0,使得两个编码长度相等;最后,我们逐位比较两个编码是否相同,如果有一位相同,则说明没有产生 Hamming Cliff,我们可以直接返回 False;否则,说明产生了 Hamming Cliff,我们可以返回 True。
最后,我们读入测试数据的组数 `t`,然后对于每组测试数据,读入两个正整数 `n` 和 `m`,判断它们是否产生 Hamming Cliff,并输出结果即可。
阅读全文