pta-等长编码

pta-等长编码

等长编码是一种简单且译码具有唯一性的编码方式，这种编码方式的特点是每个字符的编码长度相同（编码长度就是每个编码所含的二进制位数）。假设字符集只含有4个字符A，B，C，D，用两位二进制表示的编码分别为00，01，10，11。

现有n个字符需要编码，编号为1-n，其二进制编码按照字典序递增顺序进行对照，比如当n=8时，二进制编码000，001，010，011，100，101，110，111分别是编号1,2,3,4,5,6,7,8的编码。

给定字符总个数n和其中一个字符编号m，请你给出这n个字符采用等长编码方案时，第m号字符的编码。

输入格式:

输入第一行为两个正整数n和m（1<=n,m<2^30），分别代表字符总个数和指定的字符编号。

输出格式:

输出第m号字符的等长编码。

输入样例:

20 15

输出样例:

01110

 代码如下：

#include
using namespace std;
int main()
{
	int n, m;
	cin >> n >> m;
	int k = 0;//这个k代表有几层
	for (int i = 0; i < n; i++)
	{
		if (pow(2, i) >= n)
		{
			k = i;
			break;
		}

	}
	//cout << k;
	m--;
	int a[100];
	for (int i = 0; i < k; i++)
	{
		if (m % 2 == 0) {
			a[i] = 0;
		}
		else
		{
			a[i] = 1;
		}
		m /= 2;
	}
	for (int i = k - 1; i >= 0; i--)
	{
		cout << a[i];
	}

}