|
在數(shù)據(jù)結(jié)構(gòu)課關(guān)于棧的這一章中，我們都學(xué)過用“模2取余法”來將一個10進(jìn)制數(shù)轉(zhuǎn)換為一個二進(jìn)制數(shù)，進(jìn)而可以推廣到“模n取余法”，經(jīng)其轉(zhuǎn)換為n進(jìn)制（n任意指定）。
確實(shí)，這是一個很基礎(chǔ)的題目，可你是否想過如果這個10進(jìn)制數(shù)是一個大數(shù)（其位數(shù)可能上千位，此時用一般數(shù)據(jù)類型肯定是會溢出的），那么這個問題又如何來求解呢？
當(dāng)然，也許你會說很簡單嘛，自己寫一個大數(shù)類（當(dāng)然至少要寫一個大數(shù)除法才行），或者你用的是Java這種現(xiàn)代化語言，就更輕松了，直接用BigInteger這樣的大數(shù)類就可以來表示一個大數(shù)，進(jìn)而用書上教的方法來實(shí)現(xiàn)。
但是，真的需要用到大數(shù)類嗎？事實(shí)上，“殺雞焉用牛刀“，我們在紙上模擬一番上述運(yùn)算后就可以發(fā)現(xiàn)，只要做一些小小的改進(jìn)，就可以在不使用大數(shù)的情況下，也可以通過“模n
取余”的原理來實(shí)現(xiàn)大數(shù)的進(jìn)制轉(zhuǎn)換的。（當(dāng)然，整體的思想仍然是“模n取余”原理?。。。?。
舉個簡單的例子，就比如說把10進(jìn)制數(shù)12轉(zhuǎn)換為2進(jìn)制形式，書上的方法可以用下圖來表示
按照 “先余為低位，后余為高位“這條鐵律，其結(jié)果為1100.
這是書上教我們的常規(guī)思路（可惜按這個的話，大數(shù)是沒法考慮的，因?yàn)榧偃邕@里不是12，而是一個1000位的大數(shù)，由于是是對大數(shù)的整體進(jìn)行取余運(yùn)算，不使用大數(shù)類及其
除法操作，又如何得以進(jìn)行呢？），可我們的目的是不使用大數(shù)類，那么現(xiàn)在我們就來換一個視角來看這個問題，12是一個十位數(shù)，十位上是1，個位上是2，按照我們正常的
思維來看，這個計(jì)算應(yīng)該是下面這樣的：
那么我們發(fā)現(xiàn)在第一輪運(yùn)算時，十位上的1作為被除數(shù)，2作為除數(shù)，得到的商是0，余數(shù)是1(可以斷言只考慮當(dāng)前這一個數(shù)位的計(jì)算，余數(shù)或是0，或是1，若是1的話，則進(jìn)
下一數(shù)位（這里即對個位進(jìn)行運(yùn)算）時，要用1乘上進(jìn)制（這里是10）再加上下一個數(shù)位上的值（這里是2）)，即得到運(yùn)算進(jìn)入個位時被除數(shù)是12，除數(shù)是2，得到的商是6，
數(shù)是0。第一輪運(yùn)算的結(jié)果是商是06，余數(shù)是0.
進(jìn)入第二輪運(yùn)算，則上一輪的商6（這里首先要去掉前面多余的0）變成本輪的被除數(shù)，如此下去，即可得到每輪的余數(shù)。
推廣開來，如果被除數(shù)是一個1000位的大數(shù)，例如“12343435154324123……342314324343”
那么我們照樣可以從第一個數(shù)位開始逐位考慮，比如第一位是1（作為被除數(shù)），2是除數(shù)，得到的商是0，余數(shù)是1，然后是第二個數(shù)位2，由于上一位留下了余數(shù)1，則此時被
除數(shù)應(yīng)該是1*10+2 = 12,所以得到的商是6，余數(shù)是0，即運(yùn)算到此時的商是06，然后是第三個數(shù)位3，由于上一個數(shù)位留下的余數(shù)是0，所以此時被除數(shù)就是3，。。。如此下去
就完成第一輪的運(yùn)算，這一輪完畢后，需要把得到的商變成下一輪的被除數(shù)，繼續(xù)上述的運(yùn)算，直到被除數(shù)為0才停止。
下面給出了一個示例代碼，展示了如何將一個10進(jìn)制的大數(shù)轉(zhuǎn)換為其二進(jìn)制形式，僅供參考：
- #include <stdio.h>
- #include <string.h>
-
- char str[1000];//輸入字符串
- int start[1000],ans[1000],res[1000]; //被除數(shù)，商，余數(shù)
-
- //轉(zhuǎn)換前后的進(jìn)制
- const int oldBase = 10;
- const int newBase = 2;
-
- void change()
- {//各個數(shù)位還原為數(shù)字形式
- int i,len = strlen(str);
- start[0] = len;
- for(i=1;i<= len;i++)
- {
- if(str[i-1] >= '0' && str[i-1] <= '9')
- {
- start[i] = str[i-1] - '0';
- }
- }
- }
-
- void solve()
- {
- memset(res,0,sizeof(res));//余數(shù)初始化為空
- int y,i,j;
- //模n取余法，(總體規(guī)律是先余為低位，后余為高位)
- while(start[0] >= 1)
- {//只要被除數(shù)仍然大于等于1，那就繼續(xù)“模2取余”
- y=0;
- i=1;
- ans[0]=start[0];
- //
- while(i <= start[0])
- {
- y = y * oldBase + start[i];
- ans[i++] = y/newBase;
- y %= newBase;
- }
- res[++res[0]] = y;//這一輪運(yùn)算得到的余數(shù)
- i = 1;
- //找到下一輪商的起始處
- while((i<=ans[0]) && (ans[i]==0)) i++;
- //清除這一輪使用的被除數(shù)
- memset(start,0,sizeof(start));
- //本輪得到的商變?yōu)橄乱惠喌谋怀龜?shù)
- for(j = i;j <= ans[0];j++)
- start[++start[0]] = ans[j];
- memset(ans,0,sizeof(ans)); //清除這一輪的商，為下一輪運(yùn)算做準(zhǔn)備
- }
- }
-
- void output()
- {//從高位到低位逆序輸出
- int i;
- for(i = res[0];i >= 1;--i)
- {
- printf("%d",res[i]);
- }
- printf("\n");
- }
-
- int main()
- {
- scanf("%s",str);
- change();
- solve();
- output();
- return 0;
- }
高精度進(jìn)制轉(zhuǎn)換模版：
- /*
- 高精度進(jìn)制轉(zhuǎn)換
- 把oldBase 進(jìn)制的數(shù)轉(zhuǎn)化為newBase 進(jìn)制的數(shù)輸出。
- 調(diào)用方法，輸入str, oldBase newBase.
- change();
- solve();
- output();
- 也可以修改output(),使符合要求，或者存入另外一個字符數(shù)組，備用
- */
- #include<stdio.h>
- #include<string.h>
- #defien MAXSIZE 1000
- char str[MAXSIZE];//輸入字符串
- int start[MAXSIZE],ans[MAXSIZE],res[MAXSIZE];//被除數(shù)，商，余數(shù)
- int oleBasw,newBase;//轉(zhuǎn)換前后的進(jìn)制
-
- //單個字符得到數(shù)字
- int getNum(char c)//這里進(jìn)制字符是先數(shù)字，后大寫字母，后小寫字母的
- {
- if(c>='0'&&c<='9') return c-'0';//數(shù)字
- if(c>='A'&&c>='Z') return c-'A'+10;//大寫字母
- return c-'a'+36;//小寫字母
- }
- //數(shù)字得到字符
- char getChar(int i)
- {
- if(i>=0&&i<=9)return i+'0';
- if(i>=10&&i<=35)return i-'10'+'A';
- return i-36+'a';
- }
- void change()//把輸入的字符串的各個數(shù)位還原為數(shù)字形式
- {
- int i;
- start[0]=strlen(str);//數(shù)組的0位存的是數(shù)組長度
- for(i=1;i<=start[0];i++)
- start[i]=getNum(str[i-1]);
- }
- void solve()
- {
- memset(res,0,sizeof(res));//余數(shù)位初始化為空
- int y,i,j;
- while(start[0]>=1)
- {
- y=0;i=1;
- ans[0]=start[0];
- while(i<=start[0])
- {
- y=y*oldBase+start[i];
- ans[i++]=y/newBase;
- y%=newBase;
- }
- res[++res[0]]=y;//這一輪得到的余數(shù)
- i=1;//找下一輪商的起始處，去掉前面的0
- while(i<=ans[0]&&ans[i]==0) i++;
- memset(start,0,sizeof(start));
- for(j=i;j<ans[0];j++)
- start[++start[0]]=ans[j];
- memset(ans,0,sizeof(ans));
- }
- }
- void output()//從高位到低位逆序輸出
- {
- int i;
- for(i=res[0];i>=1;i--)
- printf("%d",getChar(res[i]));
- printf("\n");
- }
如果你對這個話題感興趣的話，可以用這個思路來嘗試解決下PKU
1220這個題目：http://acm.pku.edu.cn/JudgeOnline/problem?id=
|
