进制转换（递归+幂的三种计算方法）

进制转换（递归+幂的三种计算方法）十进制转成其他进制用两种方法编码：递归、非递归。---------------------------例题：进制转换

/problem/B2143题目描述：用递归算法将一个十进制整数

X（1≤X≤109）转换成任意进制数M（2≤M≤16，M为整数）。

输入格式：一行两个数，第一个十进制整数X，第二个为进制M。

输出格式：输出结果。

输入样例43116输出样例1AF---------------------------【考点】进制转换、短除法、递归。【思路和证明】进制转换是计算机基础知识。如何把十进制转成其他进制？设十进制数X的M进制是bk...b2b1b0，根据M进制的定义，有：X=bkMk

+...+b2M2

+b1M1

+b0M0为了求十进制X的M进制bk...b2b1b0，进行以下步骤：（1）用X除以M，得商为a0，此时余数为b0；（2）继续用a0除以M，记商为a1，此时余数为b1；重复步骤（2）直至商为0，倒序输出记下的余数bk...b2b1b0，就是X的M进制。这种方法称为“短除法”。下面以样例输入“43116”，把十进制整数431转为16进制为例。16进制有16个数码：0、1、2、...、9、A、...、F。第1步：431除以16，商为26，余数为F；第2步：26除以16，商为1，余数为A；第3步：1除以16，商为0，余数为1。结束。答案是1AF，即倒序输出的余数。计算过程用下图表示：【代码展示：非递归实现】下面代码的func()给出了短除法的代码。由于要倒序输出余数，需要先用s[]存余数，计算完后在第12行倒序输出。#include

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

//存进制的数码，能转2进制~16进制voidfunc(intx,intm){

//必须满足2≤M≤16，否则会出错

strings;

intlen=0;

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

//存余数 x/=m; len++;

}

for(inti=len-1;i>=0;i--)//倒序输出余数 cout<<s[i];

}

intmain(){

intx,m;

cin>>x>>m;

func(x,m);

//短除法

return0;}【代码展示：递归实现】倒序输出如果用递归来处理，编码非常简单。下面把func()改成递归函数。#include<bits/stdc++.h>usingnamespacestd;charch[]="0123456789ABCDEF";

void

func(int

x,

int

m){

if(x/m)

func(x/m,m);//先递归：继续除

cout<<ch[x%m];//再输出：倒序输出余数}intmain(){

intx,m;

cin>>x>>m;

func(x,m);

//短除法

return0;}如何倒序输出余数？在递归函数func()中，先继续递归，递归返回后再输出，就倒序输出了余数。如果先输出再递归，就是正序输出，结果是错的。初学者请一定要掌握好递归。本题是把十进制转换为其他进制，如果要求在任意进制间互相转换，可以用十进制中转。例如五进制转为九进制，先把五进制转为十进制，再把十进制转为九进制。其他进制转成十进制---------------------------例题：X进制转10进制

/problem/B3620题目描述：给一个小整数x和一个x进制的数S。将S转为10进制数。对于超过十进制的数码，用A，B，…表示。输入格式：第一行一个整数x;第二行一个字符串S。

输出格式：输出一个整数，表示答案。输入样例167B输出样例123---------------------------【考点】进制转换，pow()函数的精度问题。【思路和证明】如何把M进制转成十进制？设M进制数是bk...b2b1b0，转成十进制数X。根据进制的定义，有：X=bkMk

+...+b2M2

+b1M1

+b0M0只需按上述公式计算即可得到X。公式中需要计算幂，有三种方法实现：用库函数pow()提前预计算幂for循环递推计算幂前2种方法下面做个测试，第3种见后面的代码。测试代码，计算3的幂：#include<bits/stdc++.h>usingnamespacestd;longlongpower[50];

//存预计算的幂intmain(){

power[0]=1;

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

power[i]=power[i-1]*3;//预计算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，转成整型后可能有误差。（2）第11行用提前计算出的幂，在数组power[]中。看看结果：计算3的34次幂时，pow()已经产生了误差。【代码展示】第9行提取出M进制数的每一位，转成数字num，就是公式中的bi，然后在17行乘以Mi，并累加得到十进制数X。#include

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

intm;

cin>>m;

//输入进制

strings;

cin>>s;//输入数字s，用字符形式输入

intans=0;//答案

intlen=s.length();//数字的长度

for(inti=len-1;i>=0;i--){//从高位往低位处理数字，和第15行配合

charch=s[len-1-i];

intnum;//把这个字符转成整数

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);//累加对应的十进制值。用pow可能有误差

ans=ans*m+num;

//这样不会有误差，建议使用

}

cout<<ans;

return0;}第17行用到库函数pow(m,i)，本题也是对的。不过要注意，当i较大时，pow()函数有精度误差第18行通过for循环递推幂，就没有精度问题。但是要注意，第8行应该从高位向低位处理数字，这样第18行的累乘m，才能使高位得到更大的幂次。例题---------------------------进制

/problem/P10510题目描述：三进制和十进制的互转。规定：三进制的第0位为最左侧的那一数位。输入格式：第一行输入两个正整数V，q。V是十进制。接下来q行，每行一个操作，形如:opi操作1：把三进制的第i位数进行加法操作，0变1，1变2，2变0操作2：把三进制第i位数进行减法操作，0变2，1变0，2变1操作3：三进制的第i位，0不变，1变2，2变1输出格式：输出q行，第i行表示第i个操作后的答案。答案用十进制表示。---------------------------【考点】进制转换，pow()函数的精度。【思路和证明】模拟题目的要求，先十进制转三进制，然后执行每个操作，最后输出时把三进制转十进制。【代码展示】十进制转三进制转换仍然用短除法。前面的例题B2143用递归函数来求进制转换的余数的倒序输出。不过，本题要求低位在前，高位在后，余数本来就是正序的，不需要用递归。代码第14行的while循环是十进制转三进制。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;lls[50];//18位十进制数(<264)转成三进制不会超过50位。如果不放心，用s[100]llpower[50];

//预计算3的幂intmain(){

llV;

intq;

cin>>V>>q;

power[0]=1;

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

power[i]=power[i-1]*3;//预计算3的幂

llans=0;

intlen=0;

//三进制数的位数

while(V){

//十进制转三进制

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--)//三进制转十进制。注意本题的i可以大于len

ans=ans*3+s[i];//从高位往低位处理数字，得到3的幂

//ans+=