国际摄影作品网站,信诺盛世网站,网页设计模板图片下载,太原市住房和城乡建设局网站首页n 位格雷码序列 是一个由 2n 个整数组成的序列#xff0c;其中#xff1a;
每个整数都在范围 [0, 2n - 1] 内#xff08;含 0 和 2n - 1#xff09;第一个整数是 0一个整数在序列中出现 不超过一次每对 相邻 整数的二进制表示 恰好一位不同 #xff0c;且第一个 和 最后一…n 位格雷码序列 是一个由 2n 个整数组成的序列其中
每个整数都在范围 [0, 2n - 1] 内含 0 和 2n - 1第一个整数是 0一个整数在序列中出现 不超过一次每对 相邻 整数的二进制表示 恰好一位不同 且第一个 和 最后一个 整数的二进制表示 恰好一位不同
给你一个整数 n 返回任一有效的 n 位格雷码序列 。
思路一找规律
int* grayCode(int n, int* returnSize) {int *ret (int *)malloc((1 n) * sizeof(int));ret[0] 0;int ret_size 1;for (int i 1; i n; i) {for (int j ret_size - 1; j 0; j--) {ret[2 * ret_size - 1 - j] ret[j] | (1 (i - 1));}ret_size 1;}*returnSize ret_size;return ret;
}
分析
可将格雷码先列举几个找规律当n1时格雷码为01n2时格雷码为0,1,3,2可以向后递推发现前面的格雷码的顺序可以不变直接考虑下一位的格雷码即可同时发现每当n增加一即二进制数多一位原来的顺序向后递推一位根据该规律编写相应代码解决
思路二公式
int* grayCode(int n, int* returnSize) {int ret_size 1 n;int *ret (int *)malloc(ret_size * sizeof(int));for (int i 0; i ret_size; i) {ret[i] (i 1) ^ i;}*returnSize ret_size;return ret;
}分析
格雷码也可以使用公式直接求出。第 i (i≥0)i~(i \geq 0)i (i≥0) 个格雷码即为gii⊕⌊i/2⌋编写相应代码用异或解决问题
总结
本题考察对新定义的数字找规律的能力将答案列举出来再归纳总结即可解决
