用貪心算法進行10進制整數轉化為2進制數

十進制整數轉二進制數用什么方法？網上一搜，大部分答案都是用短除法，也就是除2反向取余法。這種方法是最基本最常用的，但是計算步驟多，還容易出錯，那么還有沒有其他更好的方法嗎？

一、短除反向取余法

具體的步驟是不斷將十進制數除以2，每次記錄余數，直至商為0，然后把所有余數從下向上(反向)的順序排列，即得到二進制數。

例如，把十進制數69轉換為二進制數，結果為1000101，計算過程如圖1所示。

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

$69=1\times 2^{6}+0\times 2^{5}+0\times 2^{4}+0\times 2^{3}+1\times 2^{2}+0\times 2^{1}+1\times 2^{0}$ ? ? ? ? ? ? ?（1）

一般表達式為：

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

十進制數轉化為二進制數的結果就是把系數 $c_{i}$ 從 $i=n$ 到 $i=0$ （從最高位到最低位）的排列。

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

$69=2^{6}+2^{2}+2^{0}$ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?? （3）

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

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

在（3）式中， $n_{0}=6$ ， $n_{1}=2$ ， $n_{2}=0$ 。

也就是在十進制的69轉換為二進制后，數位序號為0，2，6的項系數為1，其他項系數都為0（數位序號從右向左依次增1，最低位序號為0），如表1所示，表格中橙色項系數為1，白色項系數為0。

那么如何快速求 $n_{i}$ 呢？本人經過研究發現，利用貪心算法的思維，可以很好的解決這個問題。

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

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

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

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

（3）跳轉到步驟（1）循環計算，直到 $a=0$ ，計算結束。

例如，十進制數 $a=69$ ，計算過程為：

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

（2） $a=69-64=5$ ；

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

（4） $a=5-4=1$ ；

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

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

計算的結果為：69= $2^{6}$ + $2^{2}$ + $2^{0}$ =64+4+1

二進制數位序號0，2，6的項為1，其他位序號的項為0，得到結果為1000101。

對比短除法和貪心法，可以發現，貪心算法計算步驟少，準確率也較高，不容易算錯，但是需要我們事先記住一些常用的 $2^{n}$ 的值，這樣才有助于我們更快找出最大項。表2為 $0\leqslant n\leqslant 10$ 的 $2^{n}$ 的值。

**表2 常用2為底冪的值**
$2^{n}$	$2^{0}$	$2^{1}$	$2^{2}$	$2^{3}$	$2^{4}$	$2^{5}$	$2^{6}$	$2^{7}$	$2^{8}$	$2^{9}$	$2^{10}$
值	1	2	4	8	16	32	64	128	256	512	1024

（本文結束）

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

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