【题目来源】
洛谷：[P1017 NOIP 2000 提高组] 进制转换 - 洛谷
【题目描述】
我们可以用这样的方式来表示一个十进制数：将每个阿拉伯数字乘以一个以该数字所处位置为指数，以 \(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\) 进制的方式处理。
【输入样例】
30000 -2
【输出样例】
30000=11011010101110000(base-2)
【算法标签】
《洛谷 P1017 进制转换》 #数学# #进制# #NOIP提高组# #2000#
【代码详解】
#include <bits/stdc++.h>
using namespace std;int n; // 要转换的十进制数
int r; // 目标进制（可正可负）
int k; // 目标进制的绝对值
int B[50]; // 存储转换后的各位数字
int len; // 转换后数字的位数
int a[50]; // 存储进制幂次方值// 将十进制数x转换为k进制并存储在B数组中
void calc(int x)
{len = 0; // 重置位数计数器memset(B, 0, sizeof(B)); // 清空B数组// 不断除以k取余数，得到k进制表示while (x){len++;B[len] = x % k; // 存储当前位的数字x /= k; // 去掉最低位}
}// 检查当前k进制数是否等于原始十进制数n
bool check()
{int res = 0;// 将k进制数转换回十进制for (int i = 1; i <= len; i++){res += B[i] * a[i - 1]; // 各位数字乘以对应权值}return res == n; // 判断是否等于原始数
}int main()
{// 输入要转换的数和目标进制cin >> n >> r;k = abs(r); // 取进制的绝对值// 预计算进制r的各次幂a[0] = 1; // r^0 = 1for (int i = 1; i <= 20; i++){a[i] = a[i - 1] * r; // 计算r^i}// 尝试所有可能的i值for (int i = 0; ; i++){calc(i); // 将i转换为k进制// 检查转换后的k进制数是否等于原始十进制数nif (check()){// 输出结果cout << n << "=";// 从高位到低位输出k进制数for (int j = len; j >= 1; j--){if (B[j] >= 10) cout << char('A' + B[j] - 10); // 处理大于等于10的数字else cout << B[j]; // 直接输出数字}// 输出进制信息cout << "(base" << r << ")";return 0;}}return 0;
}
【运行结果】
30000 -2
30000=11011010101110000(base-2)