日期:2014-05-20  浏览次数:20670 次

一道小小的算法题、、高手来
1/7 = 0.142857142... 是个无限循环小数。
任何有理数都可以表示为无限循环小数的形式。

 * 
本题目要求即是:给出一个数字的循环小数表示法。

例如:
输入:
1,5
则输出:
0.2

输入:
1,7
则输出:
0.[142857]

输入:
7,6
则输出:
1.1[6]

用户输入的格式是:
整数,整数

每个整数范围均为:1~1000

程序输出两个整数做除法产生的小数或无限循环小数(循环节用方括号括起)。

------解决方案--------------------
Java code
    public static void main(String[] args) {
//        int a = 10, b = 2;
//        int a = 1, b = 7;
//        int a = 7, b = 6;
//        int a = 1, b = 5;
        int a = 1, b = 101;
        int gong_yue_shu = find_GongYueShu(a, b);
        a = a/gong_yue_shu;
        b = b/gong_yue_shu;
        int c = a/b;
        List<Integer> result = new ArrayList<Integer>();
        result.add(c);
        a = a-c*b;
        int count = b*3;
        while(a!=0) {
            a = a*10;
            c = a/b;
            result.add(c);
            a = a-c*b;
            count--;
            if(count==0) {
                break;
            }
        }
        printDecimal(result, b);
    }
    
    //找出最大公约数
    private static int find_GongYueShu(int a, int b) {
        int min = Math.min(a, b);
        int result = 1;
        for(int i=2; i<=min; i++) {
            if(a%i==0 && b%i==0) {
                result = i;
            }
        }
        return result;
    }
    
    //打印结果
    private static void printDecimal(List<Integer> l, int b) {
        int[] a = findRepeatParts(l, b);
        if(l.size()<3*b-1) {    //如果列表很短,则表明是可以除尽的小数,无循环体
            a[0] = Integer.MAX_VALUE;
            a[1] = Integer.MAX_VALUE;
        }
        System.out.print(l.get(0));
        if(l.size()>1) {
            System.out.print('.');
        }
        int k=Math.min(a[1], l.size());
        for(int i=1; i<k; i++) {
            if(i==a[0]) {
                System.out.print('[');
            }
            System.out.print(l.get(i));
        }
        if(k==a[1])
            System.out.println(']');
    }
    
    //找出循环体
    private static int[] findRepeatParts(List<Integer> l, int b) {
        int[] a = new int[2];

        boolean flag = true;
        for(int i=1; i<=b; i++) {//循环体的初始位置,有些循环体从第一位小数开始,有些不是(如1/6)
            for(int j=1; j<b; j++) { //循环体的长度,从长度为1开始检验,一直检验到长度为b,总能找到循环体
                for(int x=0; x<j; x++) { //根据循环体的长度,检测每个位置是否都一直在循环 
                    for(int k=i+j+x; k<l.size(); k=k+j) { //检测是否一直在循环
                        if(l.get(k) != l.get(i+x)) {
                            flag = false;
                            x=j;
                            break;
                        }
                    }
                }
                if(flag == true) {
                    a[0] = i;
                    a[1] = i+j;
                    i=b;
                    break;
                }else {
                    flag = true;
                }
            }
        }
        return a;
    }

------解决方案--------------------
Java code

import java.math.BigDecimal;

public class BigDecimalFormat {
    static int subStrCnt(String str, String subStr) {
        int i, j, k, cnt = 0;
        for (i = 0; i <= str.length() - subStr.length(); ++i) {
            k = i;
            j = 0;
            while (str.charAt(k) == subStr.charAt(j)) {
                ++k;
                ++j;
                if (j >= subStr.length()) {
                    ++cnt;
                    break;
                }
            }
        }
        return cnt;
    }

    public static String getSubStr(String str) {
        int count = 0;
        String loopStr = null;
        int i, j, start, tmp;
        int strLen = str.length();
        String dst = new String();
        for (j = 1; j <= strLen; ++j) {
            for (i = 0; i <= strLen - j; ++i) {
                start = i;
                dst = str.substring(i, i + j);
                int cnt = subStrCnt(str, dst);
                if (dst.length() == 1 && cnt < str.length() - str.indexOf(dst)) {
                    continue;
                }
                if (loopStr == null
                        || (loopStr.length() <= dst.length() && count <= cnt)) {
                    loopStr = dst;
                    count = cnt;
                }
            }
        }
        return loopStr;
    }

    static public void main(String[] args) {
        BigDecimal x = new BigDecimal(7);
        BigDecimal y = new BigDecimal(6);
        String divRst = x.divide(y, 30, BigDecimal.ROUND_DOWN).toString();
        while (divRst.charAt(divRst.length() - 1) == '0') {
            divRst = divRst.substring(0, divRst.length() - 1);
        }        
        String loopStr = getSubStr(divRst);
        String rst = null;
        if (loopStr == divRst) {
            rst = divRst;
        } else {
            rst = divRst.replaceAll(loopStr, "") + "[" + loopStr + "]";
        }
        System.out.println(rst);

    }

}