知识卡片

普通读书笔记卡 · 3630

反射格雷码每步只翻一位

理解等级:中级

二进制格雷码让相邻数只差一位。

反射构造从k−1位序列出发,后接其逆序并给后半各数加2^(k−1),得到k位序列;最后一个数回到首个数也只差一位。

它按序列邻接定义,不等于普通二进制加一。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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.