Last active
November 16, 2015 10:53
-
-
Save sentenzo/f5c187d82d87b36a6f50 to your computer and use it in GitHub Desktop.
Rational number conversion to non decimal base
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com.company; | |
import java.util.Scanner; | |
import java.util.HashMap; | |
public class Main { | |
// / n \ | |
// | --- | | |
// \ d /(b) | |
public static void main(String[] args) { | |
Scanner s = new Scanner(System.in); | |
int n = s.nextInt(); // numerator | |
int d = s.nextInt(); // denominator | |
int b = s.nextInt(); // base | |
int i_num = n / d; // integer part | |
int f_num = n % d; | |
int f_den = d; | |
Base e = new Base(b); | |
String si = e.integer_base_convert(i_num); | |
String sf = e.fractional_base_convert(f_num, f_den); | |
System.out.println(si + "." + sf); | |
} | |
} | |
class Base { | |
// digits alphabet | |
private static final String[] abc = { | |
"0", "1", "2", "3", "4" | |
, "5", "6", "7", "8", "9" | |
, "a", "b", "c", "d", "e" | |
, "f", "g", "h", "i", "j" | |
, "k", "l", "m", "n", "o" | |
, "p", "q", "r", "s", "t" | |
, "u", "v", "w", "x", "y" | |
, "z" | |
}; | |
private int base; | |
public Base(int b) { | |
if (b > abc.length) | |
throw new Error("Only bases up to " | |
+ abc.length + " are supported"); | |
base = b; | |
} | |
public String integer_base_convert(int x) { | |
StringBuilder ret = new StringBuilder(); | |
if (x == 0) | |
return abc[0]; | |
while (x > 0) { | |
ret.append(abc[x % base]); | |
x /= base; | |
} | |
ret.reverse(); | |
return ret.toString(); | |
} | |
// | |
// let's find 5/12 in binary base | |
// -------+ | |
// | | |
// +-> 10/12 20/12 16/12 8/12 | 16/12 <-- we've already met "16" before | |
// | | so, we found the period | |
// 5 | 10 8 4 8| 4 answer: 0.01(10) | |
// --*2= 0 + --*2= 1 + --*2= 1 + --*2= 0 + --*2= 1 + --*2=... | |
// 12 | 12 | 12 | 12 | 12| | 12 | |
// v v v v | v | |
// 0 . 0 1 ( 1 0 ) | 1 | |
// | | |
// -------+ | |
// | |
public String fractional_base_convert(int n, int d) { | |
StringBuilder ret = new StringBuilder(); | |
int sch = 0; | |
if (n >= d) | |
n = n % d; | |
if (n == 0) | |
return abc[0]; | |
// state memory to search for periods | |
HashMap<Integer, Integer> memory = new HashMap<>(); | |
while (true) { | |
n *= base; | |
if (memory.containsKey(n)) { | |
int v = memory.get(n); | |
// excluding cases like this: 54.321(0) | |
if (sch - v <= 1 && | |
ret.substring(ret.length()-1) | |
.equals(abc[0])) { | |
ret.setLength(ret.length() - 1); | |
break; | |
} | |
// 0.33333... => 0.(3) | |
ret.append(")"); | |
ret.insert(v, "("); | |
break; | |
} | |
memory.put(n, sch++); | |
ret.append(abc[n / d]); | |
n %= d; | |
} | |
return ret.toString(); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment