知识卡片
反射格雷码每步只翻一位
二进制格雷码让相邻数只差一位。
反射构造从k−1位序列出发,后接其逆序并给后半各数加2^(k−1),得到k位序列;最后一个数回到首个数也只差一位。
它按序列邻接定义,不等于普通二进制加一。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第16章 摊还分析 · 查看原书依据
A binary Gray code represents a sequence of nonnegative integers in binary such that to go from one integer to the next, exactly one bit flips every time.
参考来源
- 位置:《算法导论(第4版)》第16章《摊还分析》(OEBPS/chapter016.xhtml,文本字符[45000,50000))。
- 结论依据:问题16-1 定义相邻格雷码只翻一位;反射构造将 k−1 位序列与其逆序加 2^(k−1) 后拼接,环首尾相邻性质需按题目验证。
- 原始内容:A binary Gray code represents a sequence of nonnegative integers in binary such that to go from one integer to the next, exactly one bit flips every time.