线上OJ:
一本通:1820:【00NOIP提高组】进制转换 (opens in a new tab)
AcWing:5505. 进制转换 (opens in a new tab)
洛谷:P1017 [NOIP2000 提高组] 进制转换 (opens in a new tab)
核心思想:
1、题中告诉我们一个关键信息:
任何一个十进制数 X 都可以表示为 以 R 为基数的幂次方的和,并且不管R > 0,还是R < 0都适用。 即
公式 ①
举例:
(求15对2为底)
(求-15对-2为底),切记,不要误以为
正确答案为:
2、由于在进行进制转换时,基础算法与R是否大于0无关。现在只要求出 公式① 中的每项系数 a 即可
常规的位权展开如下(短除法+逆序输出):
例:十进制的10=8+2,对应着二进制的 1010
10 / 2 = 5 … 0
5 / 2 = 2 … 1
2 / 2 = 1 … 0
1 / 2 = 0 … 1
如果是 -15 对 -2 进行短除法,则C++执行的结果为
-15 / -2 = 7 ... -1 (因为 -15 = 7 *(-2) + (-1))。
由于在进制转换时每项系数均为正,不能为负数(注解:不可能出现类似 11(-1)1 )
所以应该把 7 (-2) + (-1) 转换 为 8(-2) + (2 + (-1))。
即,余数为负数时,应 加上底的绝对值;同时前面再多减去一个底
3、实现步骤
a. 读入 n 和 R
b. 只要 n 不为0 ,就计算 n 对 R的余数和商
b1. 如果计算出来的余数为负数,则调整为正数(余数+abs(R)),同时,调整商(商+1)
c. 逆序输出结果。 由于本题的进制 R 超过10,需要用到字母表示。所以输出时统一先转换成字符再输出
c1. 如果系数 < 10, 则 cout << (char)('0' + a[j])
c2. 如果系数 >=10, 则 cout << (char)('A' + a[j] - 10)
注意,连续输出时,需要都转换成相同的格式。不能上面cout int, 下面cout char
题解代码:
#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[100]; // 存储余数,最后倒序输出
char ans[100]; // 由于超过10会变成ABCD...,所以统一转换为字符再输出
int main()
{
cin >> n >> k;
int i;
for(i = 0; n != 0; i++)
{
a[i] = n % k; // a[i] 为余数(即最后总倒序输出的数值)
n /= k;
if(a[i] < 0) // 如果余数为负,需转为正。举例: -15 = 7 *(-2) + (-1),应转为 8*(-2) + (2 + (-1))
{
a[i] = a[i] + abs(k);
n++;
}
}
for(int j = i - 1; j >= 0; j--) //倒序遍历数组,输出时统一转换为 char 型字符输出
{
if(a[j] < 10) cout << (char)('0' + a[j]); // 统一转换为字符输出 (因为超过10的只能以字符输出)
else cout << (char)('A' + a[j] - 10); // 不能一部分cout int,一部分 cout char
}
return 0;
}