三、编程题 (每题 25 分，共 50 分)

1、进制转换
问题描述
N进制数指的是逢N进⼀的计数制。例如，⼈们日常⽣活中⼤多使用⼗进制计数，而计算机底层则⼀般使用二进制。除此之外，⼋进制和⼗六进制在⼀些场合也是常⽤的计数制（⼗六进制中，⼀般使用字母A 至F表⽰⼗⾄⼗五；本题中，⼗⼀进制到⼗五进制也是类似的）。
在本题中，我们将给出 N个不同进制的数。你需要分别把它们转换成⼗进制数。
提示
对于任意⼀个L位K进制数，假设其最右边的数位为第 0位，最左边的数位为第 L - 1 位，我们只需要将其第i位的数码乘以权值 Kⁱ，再将每位的结果相加，即可得到原K进制数对应的⼗进制数。下⾯是两个例⼦：

1.⼋进制数1362 对应的⼗进制数为1 × 8³＋3 × 8²＋6 × 8¹＋2 × 8⁰= 754；

2.⼗六进制数3F0 对应的⼗进制数为3 × 16²＋15 × 16¹+ 0 × 16⁰= 1008 。

输入描述
输⼊的第⼀⾏为⼀个⼗进制表示的整数N。接下来N⾏，每⾏⼀个整数K，随后是⼀个空格，紧接着是⼀个K进制数，表示需要转换的数。保证所有K进制数均由数字和⼤写字母组成，且不以0开头 。保证K进制数合法。

保证N ≤ 1000 ；保证2 ≤ K ≤ 16。
保证所有K进制数的位数不超过9。
输出描述
输出N行，每⼀个十进制数，表⽰对应K进制数的十进制数值。

样例输入1

2
8 1362
16 3F0

样例输出1

754
1008

样例输入2

2
2 11011
10 123456789

样例输出2

27
123456789

【题目大意】
1.有n个k进制的整数，将它们分别转换成对应的十进制。

【考纲知识点】
1.基本运算、输入输出语句、循环、进制转换的知识。

【解题思路】
1.按题目要求定义好需要的变量，并实现输入；
2.输入n行，每行2个整数，分别表示进制和要转换的数字；

3.按求进制方法求即可。例如：(abc)2=a*2²+b*2¹+c*2⁰
【参考程序】

#include <iostream>
#include <cstring>
using namespace std;
int trans_digit(int k,char c){
	if(c<='9')
		return(c-'0');
	return(c-'A'+ 10);
}
long long trans(int k,char str[]){
	int l = strlen(str);
	long long res=0, pw=1;
	for(int i=l-1;i>=0;i--){
		res += pw*trans_digit(k,str[i]);
		pw *= k;
	}
	return res;
}
int main(){
	int n=0;
	cin >>n;
	for(int t=0;t<n;t++){
		int k=0;
		char str[10];
		cin >>k>> str;
		cout<<trans(k,str)<< endl;
	}
	return 0;
}

2、变长编码
问题描述
小明刚刚学习了三种整数编码方式:原码、反码、补码，并了解到计算机存储整数通常使用补码。但他总是觉得生活中很少用到2³¹-1这么大的数，生活中常用的0 ~ 100这种数也同样需要用4个字节的补码表示，太浪费了些。热爱学习的小明通过搜索，发现了一种正整数的变长编码方式。这种编码方式的规则如下:
1.对于给定的正整数，首先将其表达为二进制形式。例如，(0){10} =(0){2}，(926){10}=(1110011110){2}。
2.将二进制数从低位到高位切分成每组7 bit，不足7bit的在高位用0填补。例如，(0){2}变为0000000的一组,(1110011110){2}变为0011110和0000111的两组。

3.由代表低位的组开始，为其加入最高位。如果这组是最后一组，则在最高位填上0，否则在最高位填上1。于是，0的变长编码为00000000一个字节，926的变长编码为10011110和00000111两个字节。
这种编码方式可以用更少的字节表达比较小的数，也可以用很多的字节表达非常大的数。例如，987654321012345678的二讲制为(0001101 1011010 01101101001011 1110100 0100110 1001000 0010110 1001110){2}于是它的变长编码为(十六进制表示) CE 96 C8 A6 F4 CB B6 DA OD，共9个字节。

你能通过编写程序，找到一个正整数的变长编码吗?
输入描述
输⼊第⼀⾏ ，包含⼀个正整数N。约定0≤N≤10¹⁸。
输出描述
输出⼀⾏ ，输出N对应的变长编码的每个字节 ，每个字节均以2位⼗六进制表示（其中， A-F使⽤⼤写字母表⽰） ， 两个字节间以空格分隔。

样例输入1

    0

样例输出1

    00

样例输入2

926

样例输出2

9E 07

样例输入3

987654321012345678

样例输出3

CE 96 C8 A6 F4 CB B6 DA OD

【题目大意】
1.给一个正整数，根据题目要求找它的变长编码，变长编码用16进制表示。

【考纲知识点】
1.基本运算、输入输出语句、一维数组、位运算的知识。

【解题思路】
1.按题目要求定义好需要的变量，并实现输入；
2.根据题意，1、将n对应的二进制，每7位1组，保存起来；

3.除了包含最高位那组，其他组最前面都增加1，例如中间一组是0001111，最前面加1变成10001111；
4.注意输出是先输出低位的数组，输出内容用16进制表示即可。

【参考程序】

#include <iostream>
using namespace std;

void output_digit(int d){
	if(d >= 10)
		cout <<(char)('A'+d-10);
	else
		cout <<(char)('0'+d);
}
void output_code(int s){
	output_digit(s >> 4);
	output_digit(s & 0x0f);
}
int main(){
	long long n=0;
	cin >> n;
	int split[10];
	int l=0;
	while(n>0){
		split[l]=(int)(n& 0x7f);
		n >>= 7;
		l++;
	}
	for(int i=0;i<l-1;i++)
		split[i] |= 0x80;
	output_code(split[0]);
	for(int i=1;i<l;i++){
		cout << " ";
		output_code(split[i]);
	}
	cout << endl;
	return 0;
}