一道小小的算法题、、高手来
1/7 = 0.142857142... 是个无限循环小数。
任何有理数都可以表示为无限循环小数的形式。
*
本题目要求即是：给出一个数字的循环小数表示法。
例如：
输入：
1,5
则输出：
0.2
输入：
1,7
则输出：
0.[142857]
输入：
7,6
则输出:
1.1[6]
用户输入的格式是：
整数,整数
每个整数范围均为：1~1000
程序输出两个整数做除法产生的小数或无限循环小数（循环节用方括号括起）。
[解决办法]
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; }
[解决办法]
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); }}
[解决办法]
public class Fraction{ public static int findGreatestCommonDivisor(int a,int b) //计算最大公约数(辗转相除法) { while(a%b!=0) { int tmp=b; b=a%b; a=tmp; } return b; } public static boolean IsExisted(int value,int[] array,int index) //数值曾今出现过吗？ { for(int i=0;i<=index;i++) { if(array[i]==value) return true; } return false; } public static String OutputResult(int a,int b) //输出结果 { String s1="",s2=""; //用于存储结果 int GreatestCommonDivisor=findGreatestCommonDivisor(a,b); a=a/GreatestCommonDivisor;//将a,b约分，减少计算量。 b=b/GreatestCommonDivisor; int Z=a/b;//将a/b化为Z+p/q。Z为整数，p<q。 int p=a%b; int q=b; s1=Z+""; //保存整数部分,及紧跟小数点的0； if(p==0) //没有小数 return s1; else s1+="."; p*=10; while(p<q) //将p*=10使p>q { s1+="0"; p*=10; } int[] Remainder=new int[q] ; //用于保存余数 int Index=0; while(p%q!=0 && !IsExisted(p%q,Remainder,Index)) //没找到小数循环体或没整除 { //p%q==0表示整除 IsExist=true 表示找到循环体 s2+=(p/q+""); Remainder[Index]=p%q; //存入余数数组 Index++; p=p%q*10; } if(p%q==0) //有限小数 return s1+s2+(p/q); //整除要加上最后一位 return s1+"["+s2+"]"; } public static void main(String args[]) { int a=1,b=765432; //用户输入的数。书还没看到那部分，先直接赋值了，就不让用户输入了。 System.out.println(OutputResult(a,b)); }}
[解决办法]
算法的核心思想判断余数是否重复出现,代码如下:
package Core.Java.Chapter1;
import java.util.HashSet;
import java.util.Set;
public class Fraction {
public String getAnswer(int a,int b){
Set<String> hashset = new HashSet<String>();
String answer ="";
if (a % b == 0 ) return (a / b) +"";
answer = a/b +".";
a = a % b;
while (a != 0)
{
if( !hashset.contains(a+""))
hashset.add(a+"");//如果余数重复出现 表明是循环小数
else
{
int j = answer.lastIndexOf((a*10)/b+"");//找到出现循环的位置
answer = answer.substring(0, j)+"["+answer.substring(j, answer.length())+"]";
break;
}
a = a*10;//余数*10
answer += a/b;//保存商
a = a % b;//求下一个余数
}
return answer;
}
public static void main(String[] args) {
Fraction f = new Fraction();
for (int i = 1;i < 20;i++)
System.out.println(f.getAnswer(1, i));
}
}
输出结果:
1
0.5
0.[3]
0.25
0.2
0.1[6]
0.[142857]
0.125
0.[1]
0.1
0.[09]
0.08[3]
0.[076923]
0.0[714285]
0.0[6]
0.0625
0.[0588235294117647]
0.0[5]
0.[052631578947368421]