《格雷编码王国大冒险》——让小学生也能真正理解“格雷编码”第一章灯泡城堡的大危机1、很久很久以前在“二进制王国”里住着一群神奇的小灯泡。1每个灯泡只有两种状态0 → 熄灭 ❌1 → 点亮 ✅2比如数字二进制00001001201030113国王每天都会按顺序切换灯泡。2、问题来了1有一天工程师发现如果一次切换太多灯泡机器会出错2例如从011变成100竟然有第1位变了第2位变了第3位变了3一下变了3个灯泡机器“啪”地爆炸了 第二章格雷骑士登场1、这时一位聪明的骑士出现了。1他叫 格雷骑士Gray2他说“每次只改变一个灯泡不就安全了吗”3于是他设计出了格雷编码Gray Code4规则只有一句✅ 相邻两个数只允许一位不同第三章看看真正的格雷编码1、普通二进制十进制二进制000010012010301141002、你会发现001 - 010变了2位不安全3、格雷编码版本十进制格雷编码00001001201130104110511161017100观察一下000 - 001只变1位 ✅001 - 011只变1位 ✅011 - 010只变1位 ✅太神奇了第四章为什么叫“格雷编码”1、因为它是数学家 Frank Gray发明的。2、所以叫Gray Code格雷编码第五章格雷编码到底有什么用它可厉害了1. 电梯楼层传感器电梯楼层传感器如果同时变化多位可能把3楼看成7楼 格雷编码一次只变1位更安全。2. 游戏手柄旋钮转动时使用格雷编码可以避免读错位置。3. 火箭、机器人机器特别怕“多个开关同时变化”。格雷编码特别稳定第六章最核心的秘密终于来到真正重要的部分了1、如何把二进制变成格雷编码1公式✅ Gray Binary ^ (Binary 1)2意思格雷码 原数字 ^ (原数字右移1位)2、这里^是位运算异或 XOR第七章再复习下什么是异或异或规则ABA^B000110011101口诀✅ 一样为0不一样为1第八章真正开始计算比如求数字 5 的格雷编码第一步写二进制5 的二进制101第二步右移1位101 1变成010第三步异或101 010 --- 111得到111所以5 的格雷编码是 111第九章C程序实现方法1求一个数的格雷编码#include iostream using namespace std; int main() { int n; cin n; int gray n ^ (n 1); cout gray; return 0; }第十章一步一步看程序1、输入52、n 1101 - 0103、异或101 010 --- 1114、输出75、注意程序输出的是十进制6、因为111二进制 7十进制第十一章打印 n 位格雷编码1、比如输出3位格雷编码000 001 011 010 110 111 101 1002、程序#include iostream using namespace std; int main() { int n; cin n; //例如输入3 int total 1 n; //3位格雷码一共有8个数字 for(int i 0; i total; i) { int gray i ^ (i 1); //使用公式求格雷码10进制 for(int j n - 1; j 0; j--) { cout ((gray j) 1); // 按照位次拆回二进制数字 } cout endl; } return 0; }第十二章详细讲解1. 什么是1 n意思2 的 n 次方例如1 3就是1000二进制 8因为3位二进制000 ~ 111总共有8 个状态2. 为什么(gray j) 1能取出某一位例如gray 111j2111 2 001再001 1 1说明第2位是1。第十三章神奇规律观察iGray0000100120113010你会发现每次只变1位这就是格雷编码最大的特点第十四章小游戏理解1、灯泡挑战赛有3个灯泡000每次只能改一个灯泡你能不能走遍所有状态答案就是格雷编码顺序2、第十五章常见应用1. 状态压缩很多算法会用二进制表示状态。格雷编码可以让状态变化更平滑。2. 枚举所有状态比如开关问题迷宫问题电路问题3. 汉诺塔汉诺塔移动规律其实和格雷编码非常像因为每次也只移动一个盘子第十六章记忆口诀格雷编码口诀相邻只变一位码 机器读取不害怕。 原数右移再异或 Gray编码就是它第十七章小挑战挑战1求6的格雷编码。挑战2输出3位格雷编码。挑战3为什么011 - 010只变化1位看看是哪一位变了最终总结1、什么是格雷编码一种相邻状态只改变1位的编码2、核心公式gray n ^ (n 1)3、核心优点✅ 不容易出错✅ 更稳定✅ 机器特别喜欢4、核心思想“一次只改一点点”这其实也是很多算法的重要思想
GESP6级C++考试语法知识（五、格雷码）
《格雷编码王国大冒险》——让小学生也能真正理解“格雷编码”第一章灯泡城堡的大危机1、很久很久以前在“二进制王国”里住着一群神奇的小灯泡。1每个灯泡只有两种状态0 → 熄灭 ❌1 → 点亮 ✅2比如数字二进制00001001201030113国王每天都会按顺序切换灯泡。2、问题来了1有一天工程师发现如果一次切换太多灯泡机器会出错2例如从011变成100竟然有第1位变了第2位变了第3位变了3一下变了3个灯泡机器“啪”地爆炸了 第二章格雷骑士登场1、这时一位聪明的骑士出现了。1他叫 格雷骑士Gray2他说“每次只改变一个灯泡不就安全了吗”3于是他设计出了格雷编码Gray Code4规则只有一句✅ 相邻两个数只允许一位不同第三章看看真正的格雷编码1、普通二进制十进制二进制000010012010301141002、你会发现001 - 010变了2位不安全3、格雷编码版本十进制格雷编码00001001201130104110511161017100观察一下000 - 001只变1位 ✅001 - 011只变1位 ✅011 - 010只变1位 ✅太神奇了第四章为什么叫“格雷编码”1、因为它是数学家 Frank Gray发明的。2、所以叫Gray Code格雷编码第五章格雷编码到底有什么用它可厉害了1. 电梯楼层传感器电梯楼层传感器如果同时变化多位可能把3楼看成7楼 格雷编码一次只变1位更安全。2. 游戏手柄旋钮转动时使用格雷编码可以避免读错位置。3. 火箭、机器人机器特别怕“多个开关同时变化”。格雷编码特别稳定第六章最核心的秘密终于来到真正重要的部分了1、如何把二进制变成格雷编码1公式✅ Gray Binary ^ (Binary 1)2意思格雷码 原数字 ^ (原数字右移1位)2、这里^是位运算异或 XOR第七章再复习下什么是异或异或规则ABA^B000110011101口诀✅ 一样为0不一样为1第八章真正开始计算比如求数字 5 的格雷编码第一步写二进制5 的二进制101第二步右移1位101 1变成010第三步异或101 010 --- 111得到111所以5 的格雷编码是 111第九章C程序实现方法1求一个数的格雷编码#include iostream using namespace std; int main() { int n; cin n; int gray n ^ (n 1); cout gray; return 0; }第十章一步一步看程序1、输入52、n 1101 - 0103、异或101 010 --- 1114、输出75、注意程序输出的是十进制6、因为111二进制 7十进制第十一章打印 n 位格雷编码1、比如输出3位格雷编码000 001 011 010 110 111 101 1002、程序#include iostream using namespace std; int main() { int n; cin n; //例如输入3 int total 1 n; //3位格雷码一共有8个数字 for(int i 0; i total; i) { int gray i ^ (i 1); //使用公式求格雷码10进制 for(int j n - 1; j 0; j--) { cout ((gray j) 1); // 按照位次拆回二进制数字 } cout endl; } return 0; }第十二章详细讲解1. 什么是1 n意思2 的 n 次方例如1 3就是1000二进制 8因为3位二进制000 ~ 111总共有8 个状态2. 为什么(gray j) 1能取出某一位例如gray 111j2111 2 001再001 1 1说明第2位是1。第十三章神奇规律观察iGray0000100120113010你会发现每次只变1位这就是格雷编码最大的特点第十四章小游戏理解1、灯泡挑战赛有3个灯泡000每次只能改一个灯泡你能不能走遍所有状态答案就是格雷编码顺序2、第十五章常见应用1. 状态压缩很多算法会用二进制表示状态。格雷编码可以让状态变化更平滑。2. 枚举所有状态比如开关问题迷宫问题电路问题3. 汉诺塔汉诺塔移动规律其实和格雷编码非常像因为每次也只移动一个盘子第十六章记忆口诀格雷编码口诀相邻只变一位码 机器读取不害怕。 原数右移再异或 Gray编码就是它第十七章小挑战挑战1求6的格雷编码。挑战2输出3位格雷编码。挑战3为什么011 - 010只变化1位看看是哪一位变了最终总结1、什么是格雷编码一种相邻状态只改变1位的编码2、核心公式gray n ^ (n 1)3、核心优点✅ 不容易出错✅ 更稳定✅ 机器特别喜欢4、核心思想“一次只改一点点”这其实也是很多算法的重要思想
