用貪心算法計算十進制數轉二進制數（小數部分）

在上一篇博文用貪心算法計算十進制數轉二進制數（整數部分）-CSDN博客中，小編介紹了用貪心算法進行十進制整數轉化為二進制數的操作步驟，那么有朋友問我，那十進制小數轉二進制，可以用貪心算法來計算嗎？我研究了一下，發現也是可以用的，下邊介紹一下操作步驟。

一、乘2正向取整法

二、十進制小數轉化為二進制小數的數學原理

三、貪心算法

1、貪心算法簡介

2、操作步驟

3、結論

一、乘2正向取整法

在介紹貪心算法之前，還是先介紹一下常用的計算方法，就是“乘2取整”法。

這種方法就是把十進制的小數部分乘2，并記錄得到的積的整數部分，把積的整數部分減掉，再把積的小數部分進行乘2，并記錄得到的積的整數部分，依次乘2取整，直到乘2后得到的積為1，也就是整數部分為1，小數部分為0時，轉化完成。轉化完成后，從上往下（正向）依次把整數部分排列起來，就是轉化后的二進制小數。

注意，并不是所有的十進制小數都能精確地轉化為二進制小數。如果出現乘2后的積一直不為1的情況時，此十進制小數就不能精確轉化為二進制小數，只能無限接近。

例如，十進制小數0.15就無法精確地轉換為二進制，轉化的結果為0.001001100110011……循環不盡，無法得到精確轉化值。

二、十進制小數轉化為二進制小數的數學原理

通過觀察圖1，可以看出：

$0.6875=1\times 2^{-1}+0\times 2^{-2}+1\times 2^{-3}+1\times 2^{-4}$ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（1）

一般的表達式為：

? ? $a=\sum_{i=1}^{i=n}\left ( c_{i}\ast 2^{-i} \right ),c_{i}\in \left \{ 0,1 \right \}$ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （2）

十進制小數轉化為二進制小數的過程就是把系數 $c_{i}$ 從 $i=1$ 到 $i=n$ （從最高位到最低位）的排列。? ?

在（1）式中， $c_{1}=1,c_{2}=0,c_{3}=1,c_{4}=1$ ，所以 $\left ( 0.6875 \right )_{10}=\left ( 0.1011 \right )_{2}$ 。

如果把（1）式中的系數? $c_{_i}=0$ 的項去掉，那么有

$0.6875=1\times 2^{-1}+1\times 2^{-3}+1\times 2^{-4}$ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（3）

也就是把十進制小數轉換為二進制小數的過程，實際上就是把十進制小數轉換為若干個以2為底的冪運算之和，那么一般表達式為：

$a=\sum_{i=0}^{i=m}2^{-n_{i}}$ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??? ? ? ? ? ? ? ? ?（4）

在（3）式中， $n_{0}=1,n_{1}=3,n_{2}=4$ 。也就是在十進制小數0.6825轉換為二進制小數后，數位序號為1，3，4的項系數為1，其他項系數都為0（數位序號從左向右依次增1，最低位序號為1），如表1所示，表格中橙色項系數為1，白色項系數為0。

表1 十進制小數0.6875的二進制轉換結果
位序號	1	2	3	4
位權重	1/2	1/4	1/8	1/16
項系數	1	0	1	1
二進制數	1	0	1	1

三、貪心算法

那么如何快速計算出（4）式的 $n_{i}$ 呢？與十進制整數轉化二進制數類似，也可以用貪心算法進行計算。

1、貪心算法簡介

貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的是在某種意義上的局部最優解。

2、操作步驟

假設十進制數為 $a$ ，根據公式（4），用貪心算法思維進行十進制小數轉二進制小數計算的步驟為：

（1）先找出 $a$ 中最大的那一項 $2^{-n_{i}}$ ，并記錄 $n_{i}$ ；

（2）把最大項的值從??????? $a$ 中減掉： $a=a-2^{-n_{i}}$

（3）跳轉到步驟（1）循環計算，直到??????? $a=0$ 或 $a\leqslant$ 給定極小值，計算結束。

為了人工計算更直觀，我們通常把 $2^{-n_{i}}$ 寫為小數形式0.5，0.25，0.125，0.0625，0.03125。

因此（1）式右邊的指數形式轉化為小數形式

$0.6825=1\times 0.5+0\times 0.25+1\times0.125+1\times 0.0625$ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （5）

同樣，可以把（3）式改寫為：

$0.6825=1\times 0.5+1\times0.125+1\times 0.0625$ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （6）

下邊以十進制小數 $a=0.6875$ 轉化為二進制小數為例，介紹貪心算法的計算步驟：

（1）找出0.6875中最大的項為0.5，也就是 $2^{-1}$ ，記錄 $n_{0}=1$ ；

（2） $a=0.6875-0.5=0.1875$ ；

（3）找出0.1875中最大的項為0.125，也就是 $2^{-3}$ ，記錄 $n_{1}=3$ ；

（4） $a=0.1875-0.125=0.0625$ ；

（5）找出0.0625中最大的項為0.0625，也就是 $2^{-4}$ ，記錄 $n_{1}=4$ ；

（6） $a=0.0625-0.0625=0$ ，計算結束；

計算的結果為：0.6875=0.5+0.125+0.0625= $2^{-1}+2^{-3}+2^{-4}$

二進制小數位序號為1,3,4的項為1，其他位序號的項為0，計算結果為 $\left ( 0.6875 \right )_{10}=\left ( 0.1011 \right )_{2}$ 。

3、結論

對比乘2取整法和貪心法，可以發現，對于可以轉化為精確二進制小數的情況來說，貪心算法計算量少，準確率較高，不容易算錯，也更直觀，更好理解和記憶，但是需要我們事先記住一些常用的 $2^{-n}$ 的值，這樣才有助于我們更快找出最大項。表2為 $1\leqslant n\leqslant 5$ 的 $2^{-n}$ 的值。

**表2 常用2為底冪的值**
$2^{-n}$	$2^{-1}$	$2^{-2}$	$2^{-3}$	$2^{-4}$	$2^{-5}$
值	0.5	0.25	0.125	0.0625	0.03125

（本文結束）

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/bicheng/20498.shtml
繁體地址，請注明出處：http://hk.pswp.cn/bicheng/20498.shtml
英文地址，請注明出處：http://en.pswp.cn/bicheng/20498.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！