题目描述
将M进制的数X转换为N进制的数输出。
输入描述:
输入的第一行包括两个整数：M和N(2<=M,N<=36)。
下面的一行输入一个数X，X是M进制的数，现在要求你将M进制的数X转换成N进制的数输出。
输出描述:
输出X的N进制表示的数。
分析一
不妨先從熟悉的2到10進制之間的轉化入手，分析進制轉化問題的規律。
將十進制數x轉為二進制數的方法是，依次記錄x除以2所得的餘數，同時用商替換掉x。x=0時，停止計算，所記錄的餘數排成一行就是所求的二進制數。例如，十進制數11轉為二進制，步驟如下：
11 ÷ 2 = 5 ······ 1
5 ÷ 2 = 2 ······ 1
2 ÷ 2 = 1 ······ 0
1 ÷ 2 = 0 ······ 1
從下往上取餘數，得二進制數1011.
反過來，要從二進制數1011得到其十進制表示方法是，將二進制數的每一位都乘上該位的權數，相乘的結果的和就是所求的十進制數。第i位對應的權數是. 例如
以上雖然講的是十進制數與二進制數之間的轉化，但該原理可以推廣到十進制數與N進制數之間的轉化。原理是一樣的。於是可以得到思路一.
思路一
先將M進制數轉化為十進制數，方法類似於二進制數轉化為十進制數。得到十進制數之後，再將其轉化為N進制數，方法類似於十進制數轉為二進制數。這樣，利用十進制數作為中介，就完成了任意進制之間的轉化。
代碼略
分析二
一般來說，運用思路一就可以快速寫出正確的進制轉換代碼。然而考慮到一些特別的條件，思路一還不是完美的。
在思路一中，需要做兩次進制轉化才能實現一次計算。這兩次進制轉化的方法相去甚遠：其中一個需要利用到除法，取餘數；而另一個則用到乘法。
在這類問題中，出題者往往會給出一個超長的數，例如字符長度為999的十進制數。這種數是無法用int、long long類型儲存的，於是我們不得不用數組來儲存這種超大的数，這意味著我們需要自己實現乘除法。
十进制转二进制，和二进制转十进制，为什么要用两种不同的方法？难道不能统一成一种方法吗？答案是可以。二進制數轉化為十進制數，其實也可以採取同十進制數轉化為二進制數一樣的方法。例如，將二進制數1011轉化為十進制數：
一樣能得到11.
这种转化方法也可以推广到任意的进制之间的转化。方法统一之后，只要实现除法和取余操作就可以了，不用实现乘法了，这就减少了代码量。
代码如下：
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
int m, n;
string x;
while (cin >> m >> n >> x) {
string res;
// 讀入字符串，並將字符轉化為數字，存入數組中。
vector<int> x2(x.size());
for (int i = 0; i < x.size(); i++) {
char c = x[i];
x2[i] = ('0' <= c && c <= '9') ? c - '0' : c - 'A' + 10;
}
// 進制轉換
for (int i = 0; i < x2.size(); ) {
// 除以N并取余
int remainder = 0;
for (; i < x2.size(); i++) {
int d = x2[i] + remainder * m;
x2[i] = d / n;
remainder = d % n;
}
// 餘數轉化為字符，拼接到字符串中
res = char(remainder < 10 ? '0' + remainder : 'a' + remainder - 10) + res;
// 略去數組前面的0，從第一個非0位開始下一輪計算
for (i = 0; i < x2.size() && x2[i] == 0; )
i++;
}
cout << res << endl;
}
return 0;
}
网友评论