题目大意
按照格雷码的生成方式,输出 n 位格雷码的第 k 号二进制串。(从 0 开始编号)
思路
填完第 k 个 n 位格雷码的第 1 位后,把它转化成某一个 n−1 位格雷码继续填这个 n−1 位格雷码的第 1 位,以此类推。
如何确定转化成第几个 n−1 位格雷码:
当 k<2n−1,因为这个 n 位格雷码的前 2n−1 个二进制串的后 n−1 位是由 n−1 位格雷码正序排列而成的,所以 k 保持不变。
当 k≥2n−1,因为这个 n 位格雷码的后 2n−1 个二进制串的后 n−1 位是由 n−1 位格雷码逆序排列而成的,所以 k 要先减去 2n−1,变成 n−1 位格雷码,再翻转才能保证是逆序的,即 k=r-k+l