生成格雷码---Python练习

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了生成格雷码---Python练习，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2346字，纯文字阅读大概需要4分钟。

内容图文

果然大早上就该做点简单题，一做难题大脑就宕机

题目描述

通常，人们习惯将所有 n 位二进制串按照字典序排列，例如所有 2 位二进制串按字典序从小到大排列为：00，01，10，11。

格雷码（Gray Code）是一种特殊的 n 位二进制串排列法，它要求相邻的两个二进制串间恰好有一位不同，特别地，第一个串与最后一个串也算作相邻。

所有 2 位二进制串按格雷码排列的一个例子为：00，01，11，10。

n 位格雷码不止一种，下面给出其中一种格雷码的生成算法：

1、1 位格雷码由两个 1 位二进制串组成，顺序为：0，1。

2、n+1 位格雷码的前 2^n 个二进制串，可以由依此算法生成的 n 位格雷码（总共 2^n个 n 位二进制串）按顺序排列，再在每个串前加一个前缀 0 构成。

3、n+1 位格雷码的后 2^n 个二进制串，可以由依此算法生成的 nn 位格雷码（总共 2^n 个 n 位二进制串）按逆序排列，再在每个串前加一个前缀 1 构成。综上，n+1 位格雷码，由 n 位格雷码的 2^n 个二进制串按顺序排列再加前缀 0，和按逆序排列再加前缀 1 构成，共 2^（n+1）个二进制串。另外，对于 n 位格雷码中的 2^2n个二进制串，我们按上述算法得到的排列顺序将它们从 0～2^(n+1 )-1编号。

按该算法，2 位格雷码可以这样推出：

已知 1 位格雷码为 0，1。

前两个格雷码为 00，01。后两个格雷码为 11，10。合并得到 00，01，11，10，编号依次为 0～3。

同理，3 位格雷码可以这样推出：

已知 2 位格雷码为：00，01，11，10。

前四个格雷码为：000，001，011，010。后四个格雷码为：110，111，101，100。合并得到：000，001，011，010，110，111，101，100，编号依次为 0～7。

现在给出 n，k，请你求出按上述算法生成的 n 位格雷码中的 k 号二进制串。

输入描述

输入一行两个整数 n，k，意义见题目描述。

其中，1≤n≤64,0≤k<2^n 。

输出描述
输出仅一行一个 n 位二进制串表示答案。

输入输出样例

输入

	2 3

输出

10

示例 2
输入

	44 1145141919810

输出

	00011000111111010000001001001000000001100011

思路

第一次用递归的方法把1~n位中每一部分的list都找出来了，果不其然运行超时，毕竟2的44次方大于10^13

第二次找规律，我们知道在n位的数组中，中间的那个元素序号是2^(n-1)-1，就是n-1位数组中最后一位的序号，所以n位的数组中，前2 ^ (n-1)个元素都是n-1位数组中的元素加0所得到的，而后2 ^ (n-1)个元素都是n-1位数组中的元素加1所得到的。

假设我们要找n位中的k号。

如果k>2 ^ (n-1)-1

那么它应该是n-1位中的2 ^ n - 1 - k号加1变成的

如果k<=2 ^ (n-1) -1

那么它应该是n-1位中的k号变成的

倒退回到1位就好了

代码

import os
import sys

# 请在此输入您的代码

numbers=["0","1"]

m=list(map(int,input().split()))

n=m[0]

k=m[1]

nums=""

def con(k,n):
  global nums
  a=2**(n-1)
  if k>2**(n-1)-1:
    nums+='1'
    k=a*2-1-k
  else:
    nums+="0"
  n-=1
  if n==0:
    return
  else:
    con(k,n)
  
con(k,n)
print(nums)

内容总结

以上是互联网集市为您收集整理的生成格雷码---Python练习全部内容，希望文章能够帮你解决生成格雷码---Python练习所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端