题目描述：
我们可以用这样的方式来表示一个十进制数：将每个阿拉伯数字乘以一个以该数字所处位置为指数，以 10 为底数的幂之和的形式。例如 123 可表示为 1×10^2+2×10^1+3×10^0 这样的形式。
与之相似的，对二进制数来说，也可表示成每个二进制数码乘以一个以该数字所处位置为指数，以 2为底数的幂之和的形式。
一般说来，任何一个正整数 R 或一个负整数 −R 都可以被选来作为一个数制系统的基数。如果是以 R 或 −R 为基数，则需要用到的数码为 0,1,…,R−1。
例如当 R=7 时,所需用到的数码是 0,1,2,3,4,5,6，这与其是 R 或 −R 无关。如果作为基数的数绝对值超过 10，则为了表示这些数码，通常使用英文字母来表示那些大于 9 的数码。例如对 16 进制数来说,用 A 表示 10，用 B 表示 11，用 C 表示 12，以此类推。
在负进制数中是用 −R 作为基数，例如 −15（十进制）相当于 (110001)−2（−2进制），并且它可以被表示为 2 的幂级数的和数：
(110001)−2=1×(−2)^5+1×(−2)^4+0×(−2)^3+0×(−2)^2+0×(−2)^1+1×(−2)^0
设计一个程序，读入一个十进制数和一个负进制数的基数，并将此十进制数转换为此负进制下的数。
输入格式
输入的每行有两个输入数据。
第一个是十进制数 n。第二个是负进制数的基数 R。
输出格式
输出此负进制数及其基数，若此基数超过 10，则参照 16 进制的方式处理。
题目背景
NOIP2000 提高组 T1
题目来源
P1017 [NOIP2000 提高组] 进制转换
输入输出样例
输入 #1
30000 -2
输出 #1
30000=11011010101110000(base-2)
输入 #2
-20000 -2
输出 #2
-20000=1111011000100000(base-2)
输入 #3
28800 -16
输出 #3
28800=19180(base-16)
输入 #4复制
-25000 -16
输出 #4复制
-25000=7FB8(base-16)
说明/提示
数据范围
对于 100%100% 的数据，−20≤R≤−2，∣n∣≤37336。
思路及部分代码：
1. 平方函数
按照题目要求，需要一个对基数进行相应平方的函数。
//输入一个数，求其的n次方
int number_pow(int a, int n){
int b = 1;
for(int i=0;i<n;i++){
b = b * a;
}
return b;
}2. 数字转字符
在输出时会可能出现超过9的数，我们将其按照 16 进制的方式处理。
//将数字转换成字符
char number_char(int n){
if(n >= 0 && n<=9)
return '0'+n;
else if(n >= 10 && n<=20)
return ('A'+n-10);
}
3. 根据已知位数，递归+遍历扫描
我们先假设知道了R进制后的位数，然后，从最高位依次尝试。
//k = 当前改变位数
//j = 数字总位数位数
//num = 比较数值
//r = 负进制
int compare(int k, int j, int num, int r){
int en = 0; //判断是否到达最低位
if(k == 0) en = 1;//到达最低位
//判断进制正负
int d_r = r;
if(r < 0) d_r = -r;
for(int d = 0; d < d_r; d++){
number[k] = d;
if(en == 0){
if(compare(k-1, j, num, r) == 1) return 1;
}
else{ //en == 1到达最低位
int sum = 0;
for(int i = 0; i <= j; i++){
sum = sum + number[i] * number_pow(r, i);
}
if(num == sum) return 1;
//else return 0;
}
}
return 0;
}4. 遍历出R进制后的位数
尝试从1位开始计算出R进制后的位数，并将compare()函数会保存正确的R进制数。
//返回结果所需的位数
int for_compare(int num, int r){
for(int i = 0;i <= 100000;i++){
if(compare(i,i,num,r) == 1) return i;
}
return -1;
}5. 将结果从高位开始打印
int cnt = for_compare(n,R);
if(cnt != -1){
printf("%d=",n);
for(int i = cnt; i >= 0 ; i--){
printf("%c",number_char(number[i]));
}
printf("(base%d)\r\n",R);
}
else{
printf("没有结果\r\n");
}总代码：
#include <stdio.h>
int n;
int R;
int number[100000] = {0};
//char number_c[100000];
//输入一个数，求其的n次方
int number_pow(int a, int n){
int b = 1;
for(int i=0;i<n;i++){
b = b * a;
}
return b;
}
//将数字转换成字符
char number_char(int n){
if(n >= 0 && n<=9)
return '0'+n;
else if(n >= 10 && n<=20)
return ('A'+n-10);
}
//k = 当前改变位数
//j = 数字总位数位数
//num = 比较数值
//r = 负进制
int compare(int k, int j, int num, int r){
int en = 0; //判断是否到达最低位
if(k == 0) en = 1;//到达最低位
//判断进制正负
int d_r = r;
if(r < 0) d_r = -r;
for(int d = 0; d < d_r; d++){
number[k] = d;
if(en == 0){
if(compare(k-1, j, num, r) == 1) return 1;
}
else{ //en == 1到达最低位
int sum = 0;
for(int i = 0; i <= j; i++){
sum = sum + number[i] * number_pow(r, i);
}
if(num == sum) return 1;
//else return 0;
}
}
return 0;
}
//返回结果所需的位数
int for_compare(int num, int r){
for(int i = 0;i <= 100000;i++){
if(compare(i,i,num,r) == 1) return i;
}
return -1;
}
int main(){
scanf("%d %d",&n,&R);
int cnt = for_compare(n,R);
if(cnt != -1){
printf("%d=",n);
for(int i = cnt; i >= 0 ; i--){
printf("%c",number_char(number[i]));
}
printf("(base%d)\r\n",R);
}
else{
printf("没有结果\r\n");
}
return 0;
}总结：
这段代码实现了在任意进制下，将一个整数转换为负进制的形式。其核心算法是通过递归和遍历，枚举每一位数字的取值，然后根据负进制的规则计算出对应的负进制数。代码中使用了一些辅助函数，如number_pow用于计算一个数的n次方，number_char用于将数字转换为字符，for_compare用于计算负进制数的位数。
不足之处：
1.在函数number_char中，当输入的数字不在0~20的范围内时，没有返回任何值，这可能会导致未定义行为。
2.在函数for_compare中，循环的终止条件是i <= 100000，但数组number的长度只有100000，因此可能会发生数组越界的错误。
改进建议：
1.在函数number_char中，应该添加一个默认情况，当输入的数字不在0~20的范围内时，返回一个默认值，避免未定义行为。
2.在函数for_compare中，应该将循环的终止条件改为i < 100000，避免数组越界的错误。
