进制之间的转换(转)

时间:2024-02-23 17:43:46

十进制与二进制转换之相互算法
十进制转二进制:

用2辗转相除至结果为1
将余数和最后的1从下向上倒序写 就是结果

例如302

302/2 = 151 余0

151/2 = 75 余1

75/2 = 37 余1

37/2 = 18 余1

18/2 = 9 余0

9/2 = 4 余1

4/2 = 2 余0

2/2 = 1 余0
故二进制为100101110

二进制转十进制
从最后一位开始算,依次列为第0、1、2...位
第n位的数(0或1)乘以2的n次方
得到的结果相加就是答案

例如:01101011.转十进制:
第0位:1乘2的0次方=1
1乘2的1次方=2
0乘2的2次方=0
1乘2的3次方=8
0乘2的4次方=0
1乘2的5次方=32
1乘2的6次方=64
0乘2的7次方=0
然后:1+2+0
+8+0+32+64+0=107.
二进制01101011=十进制107.

一、二进制数转换成十进制数

由二进制数转换成十进制数的基本做法是,把二进制数首先写成加权系数展开式,然后按十进制加法规则求和。这种做法称为"按权相加"法。

二、十进制数转换为二进制数

十进制数转换为二进制数时,由于整数和小数的转换方法不同,所以先将十进制数的整数部分和小数部分分别转换后,再加以合并。

1. 十进制整数转换为二进制整数

十进制整数转换为二进制整数采用"除2取余,逆序排列"法。具体做法是:用2去除十进制整数,可以得到一个商和余数;再用2去除商,又会得到一个商和余数,如此进行,直到商为零时为止,然后把先得到的余数作为二进制数的低位有效位,后得到的余数作为二进制数的高位有效位,依次排列起来。

2.十进制小数转换为二进制小数

十进制小数转换成二进制小数采用"乘2取整,顺序排列"法。具体做法是:用2乘十进制小数,可以得到积,将积的整数部分取出,再用2乘余下的小数部分,又得到一个积,再将积的整数部分取出,如此进行,直到积中的小数部分为零,或者达到所要求的精度为止。

然后把取出的整数部分按顺序排列起来,先取的整数作为二进制小数的高位有效位,后取的整数作为低位有效位。


1.二进制与十进制的转换

(1)二进制转十进制<BR>方法:"按权展开求和"

例:

(1011.01)2 =(1×23+0×22+1×21+1×20+0×2-1+1×2-2)10

=(8+0+2+1+0+0.25)10

=(11.25)10

(2)十进制转二进制

· 十进制整数转二进制数:"除以2取余,逆序输出"

例: (89)10=(1011001)2

2 89

2 44 …… 1

2 22 …… 0

2 11 …… 0

2 5 …… 1

2 2 …… 1

2 1 …… 0

0 …… 1

· 十进制小数转二进制数:"乘以2取整,顺序输出"

例:

(0.625)10= (0.101)2

0.625

X 2

1.25

X 2

0.5

X 2

1.0

2.八进制与二进制的转换

例:将八进制的37.416转换成二进制数:

37 . 4 1 6

011 111 .100 001 110

即:(37.416)8 =(11111.10000111)2

例:将二进制的10110.0011 转换成八进制:

0 1 0 1 1 0 . 0 0 1 1 0 0

2 6 . 1 4

即:(10110.011)2 =(26.14)8

3.十六进制与二进制的转换<BR>例:将十六进制数5DF.9 转换成二进制:

5 D F . 9

0101 1101 1111.1001

即:(5DF.9)16 =(10111011111.1001)2



例:将二进制数1100001.111 转换成十六进制:

0110 0001 . 1110

6 1 . E

即:(1100001.111)2 =(61.E)16




                           ★★★★★★★★★★★
给定一个十进制正整数n,分别设计一个迭代和递归的算法吧正整数n转换成二进制,并分析算法的时间复杂性。

         迭代算法:

                  for(n;n>0;n/=2)

                    {

                       b[i]=n%2;

                       i++;

}

                   for(i;i>=0;i--)

                     {

                        cout<<b[i];

                     }

                   以上为在C++中经调试验证的程序段。

                   分析:上程序段中for循环的次数由a决定,对a的计算过程做逆运算,即20 ,21 ,22……2n=a,所以for循环中计算的次数为log2(n),在输出程序段中,输出的次数也与计算算法中的次数相同。所以本迭代算法的时间复杂度为2log (n ),即

                   O(n)=log(n)

           递归算法:

                   binary1(int n,int c)

                     {

                           if(n=0)

                                return n;

                           else

                               {  b[i]=c;

                                 i++;

                                 return binary1(n/2,n%2);

                              }

                      }

                    分析:此递归算法由上迭代算法演变而来,不做赘述。本算法的时间复杂度为:

                   O(n)=log(n)

4-5 给定两个十进制正整数m和n,分别设计一个迭代和递归的算法计算m和n的最大公约数,并分析算法的时间复杂性。

迭代算法:

                    while(m!=0)

                        {

                          a=m;

                          m=n%m;

                          n=a;

                        }

                        cout<<n;

                   分析:上程序段中的最坏情况下的时间,假定m>n>=0,如果实际情况是n>m,那么在执行第一次循环后,m和n将会对换位置,如果其中一个等于0,那么只循环一次,两个变量相等,那么循环也是只执行一次,Leme定理,对于任意整数,如果m>n>=1,且m<斐波那契数的第k+1个数,那么本循环的执行次数少于k次。所以,本算法的最坏时间复杂度为:

                            log(n)

           递归算法:

                   EDCLID(m,n)

                     {

                           if(n=0)

                                return m;

                           else

                              return EUCLID(n,m%n)

                    分析:上递归算法由本迭代算法演变而来,不做赘述。本算法的时间复杂度为:

                            log(n)