進(jìn)制轉(zhuǎn)換（遞歸+冪的三種計算方法）

進(jìn)制轉(zhuǎn)換（遞歸+冪的三種計算方法）十進(jìn)制轉(zhuǎn)成其他進(jìn)制用兩種方法編碼：遞歸、非遞歸。---------------------------例題：進(jìn)制轉(zhuǎn)換

/problem/B2143題目描述：用遞歸算法將一個十進(jìn)制整數(shù)

X（1≤X≤109）轉(zhuǎn)換成任意進(jìn)制數(shù)M（2≤M≤16，M為整數(shù)）。

輸入格式：一行兩個數(shù)，第一個十進(jìn)制整數(shù)X，第二個為進(jìn)制M。

輸出格式：輸出結(jié)果。

輸入樣例43116輸出樣例1AF---------------------------【考點(diǎn)】進(jìn)制轉(zhuǎn)換、短除法、遞歸。【思路和證明】進(jìn)制轉(zhuǎn)換是計算機(jī)基礎(chǔ)知識。如何把十進(jìn)制轉(zhuǎn)成其他進(jìn)制？設(shè)十進(jìn)制數(shù)X的M進(jìn)制是bk...b2b1b0，根據(jù)M進(jìn)制的定義，有：X=bkMk

+...+b2M2

+b1M1

+b0M0為了求十進(jìn)制X的M進(jìn)制bk...b2b1b0，進(jìn)行以下步驟：（1）用X除以M，得商為a0，此時余數(shù)為b0；（2）繼續(xù)用a0除以M，記商為a1，此時余數(shù)為b1；重復(fù)步驟（2）直至商為0，倒序輸出記下的余數(shù)bk...b2b1b0，就是X的M進(jìn)制。這種方法稱為“短除法”。下面以樣例輸入“43116”，把十進(jìn)制整數(shù)431轉(zhuǎn)為16進(jìn)制為例。16進(jìn)制有16個數(shù)碼：0、1、2、...、9、A、...、F。第1步：431除以16，商為26，余數(shù)為F；第2步：26除以16，商為1，余數(shù)為A；第3步：1除以16，商為0，余數(shù)為1。結(jié)束。答案是1AF，即倒序輸出的余數(shù)。計算過程用下圖表示：【代碼展示：非遞歸實現(xiàn)】下面代碼的func()給出了短除法的代碼。由于要倒序輸出余數(shù)，需要先用s[]存余數(shù)，計算完后在第12行倒序輸出。#include

<bits/stdc++.h>usingnamespacestd;charch[]="0123456789ABCDEF";

//存進(jìn)制的數(shù)碼，能轉(zhuǎn)2進(jìn)制~16進(jìn)制voidfunc(intx,intm){

//必須滿足2≤M≤16，否則會出錯

strings;

intlen=0;

while(x!=0){ s[len]=ch[x%m];

//存余數(shù) x/=m; len++;

}

for(inti=len-1;i>=0;i--)//倒序輸出余數(shù) cout<<s[i];

}

intmain(){

intx,m;

cin>>x>>m;

func(x,m);

//短除法

return0;}【代碼展示：遞歸實現(xiàn)】倒序輸出如果用遞歸來處理，編碼非常簡單。下面把func()改成遞歸函數(shù)。#include<bits/stdc++.h>usingnamespacestd;charch[]="0123456789ABCDEF";

void

func(int

x,

int

m){

if(x/m)

func(x/m,m);//先遞歸：繼續(xù)除

cout<<ch[x%m];//再輸出：倒序輸出余數(shù)}intmain(){

intx,m;

cin>>x>>m;

func(x,m);

//短除法

return0;}如何倒序輸出余數(shù)？在遞歸函數(shù)func()中，先繼續(xù)遞歸，遞歸返回后再輸出，就倒序輸出了余數(shù)。如果先輸出再遞歸，就是正序輸出，結(jié)果是錯的。初學(xué)者請一定要掌握好遞歸。本題是把十進(jìn)制轉(zhuǎn)換為其他進(jìn)制，如果要求在任意進(jìn)制間互相轉(zhuǎn)換，可以用十進(jìn)制中轉(zhuǎn)。例如五進(jìn)制轉(zhuǎn)為九進(jìn)制，先把五進(jìn)制轉(zhuǎn)為十進(jìn)制，再把十進(jìn)制轉(zhuǎn)為九進(jìn)制。其他進(jìn)制轉(zhuǎn)成十進(jìn)制---------------------------例題：X進(jìn)制轉(zhuǎn)10進(jìn)制

/problem/B3620題目描述：給一個小整數(shù)x和一個x進(jìn)制的數(shù)S。將S轉(zhuǎn)為10進(jìn)制數(shù)。對于超過十進(jìn)制的數(shù)碼，用A，B，…表示。輸入格式：第一行一個整數(shù)x;第二行一個字符串S。

輸出格式：輸出一個整數(shù)，表示答案。輸入樣例167B輸出樣例123---------------------------【考點(diǎn)】進(jìn)制轉(zhuǎn)換，pow()函數(shù)的精度問題?！舅悸泛妥C明】如何把M進(jìn)制轉(zhuǎn)成十進(jìn)制？設(shè)M進(jìn)制數(shù)是bk...b2b1b0，轉(zhuǎn)成十進(jìn)制數(shù)X。根據(jù)進(jìn)制的定義，有：X=bkMk

+...+b2M2

+b1M1

+b0M0只需按上述公式計算即可得到X。公式中需要計算冪，有三種方法實現(xiàn)：用庫函數(shù)pow()提前預(yù)計算冪for循環(huán)遞推計算冪前2種方法下面做個測試，第3種見后面的代碼。測試代碼，計算3的冪：#include<bits/stdc++.h>usingnamespacestd;longlongpower[50];

//存預(yù)計算的冪intmain(){

power[0]=1;

for(inti=1;i<50;i++)

power[i]=power[i-1]*3;//預(yù)計算3的冪

for(inti=0;i<40;i++){

cout<<i<<":\n";

cout<<

(longlong)pow(3,i)<<'\n';

cout<<

power[i]<<'\n';

}

return0;}（1）第10行用pow()計算冪，返回值是double，轉(zhuǎn)成整型后可能有誤差。（2）第11行用提前計算出的冪，在數(shù)組power[]中。看看結(jié)果：計算3的34次冪時，pow()已經(jīng)產(chǎn)生了誤差?！敬a展示】第9行提取出M進(jìn)制數(shù)的每一位，轉(zhuǎn)成數(shù)字num，就是公式中的bi，然后在17行乘以Mi，并累加得到十進(jìn)制數(shù)X。#include

<bits/stdc++.h>usingnamespacestd;intmain(){

intm;

cin>>m;

//輸入進(jìn)制

strings;

cin>>s;//輸入數(shù)字s，用字符形式輸入

intans=0;//答案

intlen=s.length();//數(shù)字的長度

for(inti=len-1;i>=0;i--){//從高位往低位處理數(shù)字，和第15行配合

charch=s[len-1-i];

intnum;//把這個字符轉(zhuǎn)成整數(shù)

if(ch>='0'&&ch<='9')

num=ch-'0';

if(ch>='A'&&ch<='Z')

num=ch-'A'+10;

if(ch>='a'&&ch<='z')

num=ch-'a'+10;

//ans+=num*pow(m,i);//累加對應(yīng)的十進(jìn)制值。用pow可能有誤差

ans=ans*m+num;

//這樣不會有誤差，建議使用

}

cout<<ans;

return0;}第17行用到庫函數(shù)pow(m,i)，本題也是對的。不過要注意，當(dāng)i較大時，pow()函數(shù)有精度誤差第18行通過for循環(huán)遞推冪，就沒有精度問題。但是要注意，第8行應(yīng)該從高位向低位處理數(shù)字，這樣第18行的累乘m，才能使高位得到更大的冪次。例題---------------------------進(jìn)制

/problem/P10510題目描述：三進(jìn)制和十進(jìn)制的互轉(zhuǎn)。規(guī)定：三進(jìn)制的第0位為最左側(cè)的那一數(shù)位。輸入格式：第一行輸入兩個正整數(shù)V，q。V是十進(jìn)制。接下來q行，每行一個操作，形如:opi操作1：把三進(jìn)制的第i位數(shù)進(jìn)行加法操作，0變1，1變2，2變0操作2：把三進(jìn)制第i位數(shù)進(jìn)行減法操作，0變2，1變0，2變1操作3：三進(jìn)制的第i位，0不變，1變2，2變1輸出格式：輸出q行，第i行表示第i個操作后的答案。答案用十進(jìn)制表示。---------------------------【考點(diǎn)】進(jìn)制轉(zhuǎn)換，pow()函數(shù)的精度?！舅悸泛妥C明】模擬題目的要求，先十進(jìn)制轉(zhuǎn)三進(jìn)制，然后執(zhí)行每個操作，最后輸出時把三進(jìn)制轉(zhuǎn)十進(jìn)制?！敬a展示】十進(jìn)制轉(zhuǎn)三進(jìn)制轉(zhuǎn)換仍然用短除法。前面的例題B2143用遞歸函數(shù)來求進(jìn)制轉(zhuǎn)換的余數(shù)的倒序輸出。不過，本題要求低位在前，高位在后，余數(shù)本來就是正序的，不需要用遞歸。代碼第14行的while循環(huán)是十進(jìn)制轉(zhuǎn)三進(jìn)制。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;lls[50];//18位十進(jìn)制數(shù)(<264)轉(zhuǎn)成三進(jìn)制不會超過50位。如果不放心，用s[100]llpower[50];

//預(yù)計算3的冪intmain(){

llV;

intq;

cin>>V>>q;

power[0]=1;

for(inti=1;i<=50;++i)

power[i]=power[i-1]*3;//預(yù)計算3的冪

llans=0;

intlen=0;

//三進(jìn)制數(shù)的位數(shù)

while(V){

//十進(jìn)制轉(zhuǎn)三進(jìn)制

s[len++]=V%3;

V/=3;

}

while(q--)

{

ans=0;

intop,x;

cin>>op>>x;

if(op==1)s[x]=(s[x]+1)%3;

if(op==2)s[x]=(s[x]+2)%3;

if(op==3)s[x]=(3-s[x])%3;

for(inti=49;i>=0;i--)//三進(jìn)制轉(zhuǎn)十進(jìn)制。注意本題的i可以大于len

ans=ans*3+s[i];//從高位往低位處理數(shù)字，得到3的冪

//ans+=