一道小小的算法题、、高手来

Question

 1/7 = 0.142857142... 是个无限循环小数。
任何有理数都可以表示为无限循环小数的形式。 * 
本题目要求即是：给出一个数字的循环小数表示法。例如：
输入：
1,5
则输出：
0.2输入：
1,7
则输出：
0.[142857]输入：
7,6
则输出:
1.1[6]用户输入的格式是：
整数,整数每个整数范围均为：1~1000程序输出两个整数做除法产生的小数或无限循环小数（循环节用方括号括起）。

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

不好意思啊。最后一个return 写错了。还要做个循环确定[]的位置

Answer 5

算法的核心思想判断余数是否重复出现,代码如下:
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]

Answer 6

刚发的代码有问题,应该找余数出现的位置,不是找商出现的位置.
package Core.Java.Chapter1;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Fraction {
public String getAnswer(int a,int b){
String answer ="";
String ss = "";
List<String> temp = new ArrayList<String>();
if (a % b == 0 )  return (a / b) +"";
ss = a/b +".";
a = a % b;
while (a != 0)
{
if (!temp.contains(a+""))
{
temp.add(a+"");
}
else  
{
   int j;
   int len = temp.size();
   for (j= 0;j<len;j++) if(temp.get(j).equals(a+"")) break;        
   answer = answer.substring(0, j)+"["+answer.substring(j, answer.length())+"]";
   break; 
}  
a = a*10;//余数*10
answer += a/b;//保存商
a = a % b;//求下一个余数
}
return ss +answer;
}
public static void main(String[] args) {
Fraction f = new Fraction();
for (int i = 1;i<20;i++)
System.out.println(f.getAnswer(2, i));
}
}
打印结果:
2
1
0.[6]
0.5
0.4
0.[3]
0.[285714]
0.25
0.[2]
0.2
0.[18]
0.1[6]
0.[153846]
0.[142857]
0.1[3]
0.125
0.[1176470588235294]
0.[1]
0.[105263157894736842]