Binary Representation

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に対して余剰を取ってから、余剰を反転すればいいです.
では、小数部をどのようにバイナリに表すかは、次のようになります.
10進小数に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に戻ります.
では、コードで精度要求に達しているか、ループに入っているかをどのようにチェックしますか.
方法1:精度に達したかどうかのみを検査する.すなわち、小数部が32ビットを超えたかどうかのみを検査し、超えた場合はERRORを返す.方法2:計算精度を検査し、同時に1つのSetで毎回計算された小数部を記録し、次の計算の前にこのSetに同じ数字が現れたかどうかを検査する.いずれもERRORに戻るべきである(この場合も精度要求に達していないため、後続の計算では必ず精度要求を超える).
コードは次のとおりです.
方法1

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;
    }
}

方法2

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 set = new HashSet();
        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;
    }
}