Binary Representation
今天还是一道有关数学计算的题目，Binary Representation，来自LintCode，难度为Hard， Acceptance为19%。
这类题目不涉及太多的数据结构和算法，更多的是考察基础知识的运用。
题目如下
Given a (decimal - e.g. 3.72) number that is passed in as a string, return the binary representation that is passed in as a string. If the fractional part of the number can not be represented accurately in binary with at most 32 characters, return
ERROR.
Example
For n = "3.72", return "ERROR".
For n = "3.5", return "11.1".
思路如下
小数的二进制表示法
首先，这个的输入是小数，这里就设计到小数的二进制表示法。整数部分表示成二进制相信大家都会，只要不断的对2取余，然后再将余数反转就可以。
那么小数部分如何表示成二进制，方法如下：
对十进制小数乘2，得到的整数部分和小数部分，整数部分既是相应的二进制数码，再用
2乘小数部分(之前乘后得到新的小数部分)，又得到整数和小数部分。如此不断重复，直到小数部分为0或达到精度要求为止。第一次所得到为最高位，最后一次得到为最低位如：0.25的二进制0.25*2=0.5取整是0。0.5*2=1.0取整是1即0.25的二进制为0.01( 第一次所得到为最高位，最后一次得到为最低位)。例子如下：
0.8125的二进制
0.8125*2=1.625取整是1
0.625*2=1.25取整是1
0.25*2=0.5取整是0
0.5*2=1.0取整是1
即0.8125的二进制是0.1101（第一次所得到为最高位,最后一次得到为最低位）
精度
在上述的计算方法中，可能出现无限循环的情况，因此必须控制精度。题目中已经给出32位小数精度，超过则返回ERROR。
那么在代码中如何检查是否达到精度要求或者已经进入循环呢。
方法一：只检查是否达到精度，即只检查小数部分是否已经超过32位，超过则返回ERROR。
方法二：检查计算精度，同时用一个Set记录每次计算得到的小数部分，在下一次计算之前检查这个Set中是否出现了同一个数字，是则说明出现了循环，此时不论是否达到精度，都应该返回ERROR（因为即使此时还没达到精度要求，在后续的计算中一定会超过精度要求）。
代码如下
方法一
public class Solution {
/**
*@param n: Given a decimal number that is passed in as a string
*@return: A string
*/
private String parseInteger(String str) {
int n = Integer.parseInt(str);
if (str.equals("") || str.equals("0")) {
return "0";
}
String binary = "";
while (n != 0) {
binary = Integer.toString(n % 2) + binary;
n = n / 2;
}
return binary;
}
private String parseFloat(String str) {
double d = Double.parseDouble("0." + str);
String binary = "";
int count = 0;
while (d > 0) {
count++;
if(count > 32)
return "ERROR";
d = d * 2;
if (d >= 1) {
binary = binary + "1";
d = d - 1;
} else {
binary = binary + "0";
}
}
return binary;
}
public String binaryRepresentation(String n) {
if (n.indexOf('.') == -1) {
return parseInteger(n);
}
String[] params = n.split("\\.");
String flt = parseFloat(params[1]);
if (flt == "ERROR") {
return flt;
}
if (flt.equals("0") || flt.equals("")) {
return parseInteger(params[0]);
}
return parseInteger(params[0]) + "." + flt;
}
}
方法二
public class Solution {
/**
*@param n: Given a decimal number that is passed in as a string
*@return: A string
*/
private String parseInteger(String str) {
int n = Integer.parseInt(str);
if (str.equals("") || str.equals("0")) {
return "0";
}
String binary = "";
while (n != 0) {
binary = Integer.toString(n % 2) + binary;
n = n / 2;
}
return binary;
}
private String parseFloat(String str) {
double d = Double.parseDouble("0." + str);
String binary = "";
HashSet<Double> set = new HashSet<Double>();
while (d > 0) {
if (binary.length() > 32 || set.contains(d)) {
return "ERROR";
}
set.add(d);
d = d * 2;
if (d >= 1) {
binary = binary + "1";
d = d - 1;
} else {
binary = binary + "0";
}
}
return binary;
}
public String binaryRepresentation(String n) {
if (n.indexOf('.') == -1) {
return parseInteger(n);
}
String[] params = n.split("\\.");
String flt = parseFloat(params[1]);
if (flt == "ERROR") {
return flt;
}
if (flt.equals("0") || flt.equals("")) {
return parseInteger(params[0]);
}
return parseInteger(params[0]) + "." + flt;
}
}
如果觉得文章有帮助的话，不妨关注一下本公众号，当然也希望能帮作者推广一下，更多人关注我也会更有动力，在此先谢过了。
关注我
