1、進制轉換及應用一、引言計算機的一個重要理論基礎就是二進制思想。任何信息最終都是以二進制數的形式存儲在計算機中 的,在計算機中有時還用到十六進制和八進制。所以,在實際應用中,經常需要將一個十進制數轉換成 二進制、八進制或十六進制的數,有時又需逆向轉換,將二進制、八進制或十六進制的數轉換成十進制 數,有時還需要在二進制、八進制和十六進制數之間進行相互轉換(2, 8, 10, 16等一般稱為“ 基 ” 。不同進制數之間轉換的基本算法是:(1 十進制整數轉換成 n 進制數的方法:將十進制整數不斷除以 n 取余,最后反序輸出即可。(2 n進制數(整數、實數都可以轉換成十進制數方法:按“權 n ”展開,即

2、表示成若干項形如a i *ni 的累加和即可。(3 二進制、八進制、十六進制之間的轉換方法:利用 3位二進制表示 1位八進制數, 4位二進制 數表示 1位十六進制數的基本思想, 3位一段(或 4位一段分別轉換即可。注:一般 2 n 16,十進制以上、十六進制以下的數制除了 09十個字符外,還用到 A 、 B 、 C 、 D 、 E 、 F 幾個字符,分別表示 1015。對于十進制,我們稱它的基數為 10,而二進制的基數就是 2,十六進制的基數就是 16。對于十進制數 1234.56,我們可以表示成 1*103+2*102+3*101+4*100+5*10-1+6*10-2,我們把 10i 稱之

3、為十進制各個位的“ 權 ” 。對于二進制數 11001.01001,我們也可以類似地表示成 1*24+1*23+1*20+1*2-2+1*2-5,即二進制各個位的權為 2i 。這一方法(按權展開同樣可以用在任意 n 進制 中。二、不同進制數之間的相互轉換1、十進制正整數轉換成任意 n 進制數方法介紹 就是模擬小學學過的除法運算,比如要把十進制整數 39轉換成二進制數,則轉換方法如下左圖,即 不斷除以 2,直到商為 0,再倒序輸出即可,結果一般表示為(39 10 =(100111 2 。而要把十進制整數 245轉換成八進制數,方法一樣,只要不斷地除以 8即可,如下右圖所示,結果可以表示為:(24

4、5 10 = (365 8。一定要注意的是“ 倒序輸出 ” 。 圖 1 十進制整數轉換成 n 進制方法示意圖算法描述 設十進制數為Y, 要轉換成 n 進制, 用數組 a 存放最后的轉換結果, i 為數組下標, 則算法描述如下: i:=0;重復做:i:=i +1;ai:=Y mod nY := Ydiv n直到Y=0為止。依次輸出最高位 ai到最低位 a1。參考程序 將十進制整數 Y 轉換成任意 n 進制數(設 n<10 。Program ex1(input,output;var a: array 1.100 of integer;n,y,i,j:longint;beginwrite(&#

5、39;input number y: 'readln(y;write('input number n: 'readln(n;write('(',y,'10=','('i:=0;repeati:=i+1;ai:=y mod n;y:=y div n;until y=0;for j:=i downto 1 do write (aj;writeln('',n;readlnend.程序樣例 輸入:2458輸出:(24510=(3658思考練習 如果 n 超過了 10,比如要轉換成十六進制數,可以用字符 A 、 B

6、、 C 、 D 、 E 、 F 分別表示數 1015, 轉換方法一樣, 只要在輸出時把余數轉換為字符(A F即可 。這個程序請大家完成。2、任意 n 進制數(整數、實數轉換成十進制數方法介紹 我們知道一個十進制數 1234.56, 按權展開可以表示成 1*103+2*102+3*101+4*100+5*10-1+6*10-2, 同樣, 對于任意 n 進制數X,按權展開的方法是:(165 8 = 1*82 + 6*81 + 5*80 = 64+48+5 = 117這兒計算出來的 13.25和 117就是(1101.01 2和(165 8所對應的十進制數。參考程序 將任意 n 進制整數 X 轉換成

7、十進制數(設 n<10 。Program ex2(input,output;const m=100;var str:string;n,i,weight,total:longint;a:array1.m of integer;beginwrite('input number n: 'readln(n;write('input number x: 'readln(str;write('(',str,'',n , '=('for i:= 1 to Length(str doai:= ord (stri-ord (&

8、#39;0' 取出數中的每一位 weight:=1;total:=aLength(str;for i:=Length(str-1 downto 1 dobeginif ai > n then 判斷輸入的數是否合法 beginwriteln('input error! 'exit;end;weight:=weight*n; 累乘計算出每一位的權 total:=total+ai*weight; 按權展開每一位,累加求和 end;writeln(total, 10;readlnend.程序樣例 輸入:2100110輸出:(1001102=(3810思考練習 如果 n 超

9、過了十進制,則程序怎么修改呢?這個方法也適用于把任意 n 進制小數轉換成十進制小數,方法基本一樣。因此,我們對一個 n 進制的實數,就可以把 整數和小數部分截取出來后,分別進行轉換 ,最后再加 起來輸出即可。請大家完成。3、將十進制小數轉換為其它進制的小數方法介紹 將十進制小數轉換為其它進制的數,其基本算法是:將小數乘以待轉換的進制數,正向取整。例如 把(0.325 10轉換成二進制小數的過程如下圖 2所示: 圖 2 十進制小數轉換成其它進制小數方法示意圖所以,運算結果是:(0.325 10 (0. 0101 2大家發現,這種轉換有時是一個近似值。思考:為什么?參考程序 程序請大家完成。對于一

10、個十進制的實數,我們就可以把整數和小數分解出來,分別轉換成其它進制的整數和小數, 最后再加起來輸出結果。4、二進制和十六進制之間的轉換如要把二進制數(1111011001.01111 2轉換成十六進制數,則我們以小數點為準,向前 4位一段轉 換整數部分,不足則高位補 0;再向后 4位一段轉換小數部分,不足則低位補 0。如下圖,最后相加輸出 即可得到答案:(3D9.78 16。 圖 3 二進制數轉換成十六進制數的方法示意圖反之也一樣,如要把十六進制數(A1F5.2 16二進制數,則結果為(1010 0001 1111 0101.0010 2。 注意:一定要補齊 4位,為什么?參考程序 程序請大家

11、完成。三、進制轉換原理的應用在有些實際問題中,巧妙地應用“進制轉換”思想,可以起到很好的效果,下面舉例說明。例 1、用質量為 1, 3, 9, 27和 81的五種砝碼各 1個(假如單位為克稱物體的質量,最大可稱 121, 在實驗室我們一般要求“物左砝右” 。如果砝碼允許放在天平的兩邊,編程輸出稱不同質量(1121物 體時,砝碼應該怎樣安排?例如要稱一個 m=14克的物體,我們知道 14=27-9-3-1,即 14+9+3+1=27。所以我們可以把天平一端放置該和 9、 3、 1的砝碼,而另一端放 27的砝碼,這樣即可稱出。問題分析 被稱物體的質量計算的數學原理:設被稱物體 m 放在天平左邊,根

12、據天平平衡原理,左邊質量應等 于右邊質量。 問題關鍵在于算法中如何體現砝碼放在天平左邊、 右邊或沒有參加稱量。 這里可以用 -1、 1、 0表示砝碼放在天平左、 右和沒有參加稱量,再沒有其它數,所以稱為三進制數,每個砝碼都有這樣的三 種狀態。被稱物體質量計算為:m = a*81 + b*27 + c*9 + d*3 + e。這里 a , b , c , d , e 分別表示 81, 27, 9, 3, 1克的砝碼是放在天平的左邊、右邊或是沒用。參考程序 Program ex3(input,output;var a,b,c,d,e,m:integer;Beginfor m:=1 to 121 d

13、ofor a:= 0 to 1 dofor b:= -1 to 1 dofor c:= -1 to 1 dofor d:= -1 to 1 dofor e:= -1 to 1 doif m = a*81+b*27+c*9+d*3+e thenbeginwrite(m,'=',a*81;if b<0 then write(b*27 else write('+',b*27;if c<0 then write(c*9 else write('+',c*9;if d<0 then write(d*3 else write('+&

14、#39;,d*3;if e<0 then writeln(e else writeln('+',e;end;readlnEnd.程序樣例 運行程序,得到結果如下(共 121行 :1=0+0+0+0+131=0+27+0+3+1121=81+27+9+3+1例 2、 01圈將 2n 個 0和 2n 個 1排成一圈。從任意一個位置開始,每次按逆時針的方向以長度為 n+1的單位計數二進 制數。要求給出一種排法,用上面的方法產生出 2n+1個不相同的二進制數。如當 n=2時,有 22個 0和 22個 1排 列如下圖 4所示。如果從 a 位置開始,逆時針方向取三個數 000,然后再

15、從 b 位置上開始取三個數 001,接著 取 010,可以得到 8個不同的二進制數。設 n<8。 圖 4問題分析 (1若要產生 n 位二進制數,則有 2n-1個 0和 2n-1個 1,由這些 0, 1組成 n 位的二進制數,所以用數組記 錄 2n-1個 0和 2n-1個 1的排列方法。(2若要產生 3位二進制數,即 n=3時,則有:a1=0, a2=0, a8=1,表示為:a 1a 2a 3=0, a 2a 3a 4=1, a 3a 4a 5=2, , a 7a 8a 1=6, a 8a 1a 2=4所以數組多定義 2位。為此,一般情況多定義 n-1位。(3所產生的不同二進制數的判斷方法

16、:將產生的二進制轉換成十進制數,其范圍是 0 2n 1的 整數,判斷所產生的二進制數是否在此范圍內。(4從后向前產生數據 t 。 t= ai-1 * 2n-1+ t/2 ,若 t 在 s 中則可以接受,否則不可以接受, 應另換一個值。(5本題輸入的 n 小于 8,這樣可以用集合判斷是否出現過某個數;否則要換成數組判斷。參考程序 program ex4(input,output;const maxn=16;m=127;type ts=set of 0.m;var n: 1.maxn;a :array 1.m of integer;s: ts;p,y,i:integer;function bbb(

17、k,t:integer:boolean;var b:boolean;beginif k=0 then bbb:=true k 表示位數 else begint:=t div 2; 產生一個數 if t in s then begins:=s - t; 從集合 s 中除去 tak:=0; n個 0b:=bbb(k-1,t;if not b then s:=s+t; 添加到集合中 endelse b:=false;if not b then begint:=t + p div 2; 產生下一個數 if t in s then begins:=s -t;ak:=1; n 個 1b:=bbb(k-1,

18、t;if not b then s:=s + t endelse b:=false;end;bbb:=b;end;end;begin 主程序 readln(n;p:=1;for i:=1 to n do p:=p*2; 計算 2nfor i:=1 to p+n-1 do ai:=0; 數組 a 初始化 s:=1.p-1;if bbb(p-1,0 thenfor i:=1 to p do write(ai:2 輸出每一位 else write('no solution !'writeln;end.程序樣例 輸入 :4輸出: 0 0 0 1 1 1 1 0 1 0 1 1 0 0

19、1 0例 3、階乘數與全排列所謂階乘數是指其最低位的基為 1,即逢一進一,每高一位則基加一,即進位依次為二、三, n 位 階乘數共有 n! 個。如三位階乘數從小到大依次為:000, 010, 100, 110, 200, 210。設 n 元集合 S=a 0 , a1 , a2, an-1,則 S 的全排列與 n 位階乘數一一對應。對應方式為:從 n 個 元素中選取第一個元素有 n 種方法, 被選取的元素的下標值為 0到 n-1之間的一個整數, 將這個數作為 n 位階乘數的最高位,將剩下的元素按下標從 0到 n-2重新編號,重新編號時不改變它們的相對次序,則 選取第二個元素有 n-1種方法,被選

20、取的元素的下標值為 0到 n-2之間的一個整數,將這個數作為 n 位 階乘數的次高位,選取最后一個元素只有 1種方法,被選取的元素的下標值為 0,將這個數作為 n 位階乘數的最低位,這樣任何一種排列必可對應一個 n 位階乘數,顯然這種對應關系是一一對應的。 問題:請用階乘數法生成 1到 n 的全排列。算法設計 首先用最低位加一的方法依次產生所有的 n 位階乘數,對任意一個 n位階乘數用上述方法求出其對應的排列。參考程序 program ex5(input,output;const maxn=9;type arraytype=array0.maxn of integer;var i,j,n:in

21、teger;a,b,p:arraytype;beginwrite('Input n:'readln(n;for i:=0 to n-1 do bi:=0;while bn=0 dobeginfor i:=0 to n-1 do ai:=i+1;for i:=n-1 downto 0 dobeginpi:=abi;for j:=bi to i-1 do aj:=aj+1end;for i:=n-1 downto 0 do write(pi,' 'write(' ':20-2*n;b0:=b0+1;i:=0;while bi>i dobegin

22、bi:=0;bi+1:=bi+1+1;i:=i+1endend;writelnend.程序樣例 輸入 :4輸出:1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 31 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 12 4 1 3 2 4 3 1 3 1 2 4 3 1 4 2 3 2 1 43 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 4 1 3 24 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1例 4、已知 x 的值和系數 a 0, a 1, ,a n ,計算 y=an x n +an-1x n-1+an-

23、2x n-2+ +a1x+a0的值。問題分析 該問題看似很容易。其實隨著 n 越大,計算量也越大,乘積和累加的次數也愈多,這里的 n 就是“ 問 題的規模” 。在此,我們想通過這個例子說明一些“ 算法復雜度 ”的問題,同時使大家認識到:一些看似 簡單的問題,其實是可以做很多優化的 。算法設計 算法 1:y=a0;for k:=1 to n dobegins:=ak;for j:=1 to k do s:=s*xy:=y+s;end;writeln ( y=, y ;該運算中用到的存儲單元有 a0, a1, , an,以及固定的幾個簡單變量,所以其空間復雜 性與規模 n 成正比,即為 O (n

24、。而時間復雜性是內循環乘法計算和外循環的累加計算,計算 y 共用乘法次 數是:1+2+3+ +n=n(n+1/2, 加法僅 n 次,而在計算機內部實現乘法要比加法花費更多的時間,所以 該算法的時間復雜性為 O (n(n+1/2 O (n*n/2 O (n2 。算法 2:算法 1中的乘法運算有重復計算:x k 不需要每次從 1, x , x2, x 3, , x k 乘法去實現,只要在原 先 x k-1基礎上再做一次乘法就可以得到 x k 的結果,多用一個 b 數組存放 1, x , x2, x 3, , x n ,該問題 的空間復雜性為 O (2n O(n。b0:=1;for k:=1 to

25、n do bk:= nk-1*x;y:=a0;for k:=1 to n do y:=y+ak*bk;writeln( y=, y;此算法用了兩次單循環命令,共用了 2n 次乘法和 n 次加法,時間復雜性為 O (2n O(n。算法 3:利用我國古代數學家秦九邵提出的一個公式(秦九邵公式 ,將 y 的計算公式改寫為:y=( (an *x+an-1*x+an-2 +a1*x+a0a0, a1, an存放系數, x 為初始數據,則其程序為:y:=an;for k:=n-1 downto 0 do y:=y*x+ak;writeln( y=, y;該算法所用的存儲空間為 n 個單元,即空間復雜性為

26、O (n ,而只用了 n 次乘法和 n 次加法,所以時間 復雜性為 O (n 。由此,我們可以看到,在以上 3個求多項式值的算法中,算法 3可以獲得最好效果。四、作業(只要交源程序 1、 N 進制乘法口訣表(table.pas,table.in,table.out 從 table.in 中讀入一個自然數 N (2 N 16 ,打印出 N 進制乘法口訣表,輸出到 table.out 中。 請注意格式(大寫字母、右對齊,除了最左列外,每個數據項占 4列 ,以下是 N=16時的結果 : * 0 1 2 3 4 5 6 7 8 9 A B C D E F0 01 0 12 0 2 43 0 3 6 9

27、4 0 4 8 C 105 0 5 A F 14 196 0 6 C 12 18 1E 247 0 7 E 15 1C 23 2A 318 0 8 10 18 20 28 30 38 409 0 9 12 1B 24 2D 36 3F 48 51A 0 A 14 1E 28 32 3C 46 50 5A 64B 0 B 16 21 2C 37 42 4D 58 63 6E 79C 0 C 18 24 30 3C 48 54 60 6C 78 84 90D 0 D 1A 27 34 41 4E 5B 68 75 82 8F 9C A9E 0 E 1C 2A 38 46 54 62 70 7E 8C 9A A8 B6 C4F 0 F 1E 2D 3C 4B 5A 69 78 87 96 A5 B4 C3 D2 E12、波浪數(num.pas,num.in,num.out 波浪數是在一對數字之間交替轉換的數, 如 1212121, 雙重波浪數則是指在兩種進制下都是波浪數的 數,如十進制數 191919是一個十進制下的波浪數,它對應的十一進制數 121212也是一個波浪數,所以 十進制數 191919是一個雙重波浪數。類似的可以定義三重波浪數,三重波浪數在三種不同的進制中都是波浪數,甚至還有四重波浪數, 如十進制 300=606(