مساله:
کدگذاری اعداد اعشاری با فاکتوریل راهی است برای نوشتن اعداد در یک سیستم پایه که به فاکتوریل بستگی دارد ، نه به توان اعداد.
در این سیستم، آخرین رقم همیشه 0 است و در مبنای !0 قرار دارد و رقم قبل از آن یا 0 یا 1 است و در مبنا !1 قرار دارد و غیره. به طور کلی ، رقم n تا آخرین همیشه 0 ، 1 ، 2 ، … ، n است و در مبنای !n قرار دارد.
اطلاعات بیشتر در مورد آن را در http://fa.wikipedia.org/wiki/Factorial_number_system بخوانید.
مثال:
عدد 463 به عنوان “341010” کدگذاری شده است، زیرا:
463 = 3×5! + 4×4! + 1×3! + 0×2! + 1×1! + 0×0!
اگر محدود به ارقام 0..9 باشیم، بزرگترین عددی که می توانیم کدگذاری کنیم 10! -1 (= 3628799) است. بنابراین 0..9 را با حروف A..Z بسط می دهیم. با این 36 رقم می توان اعداد تا 36! -1 (= 3.72 × 1041) را رمزگذاری کرد.
ماموریت:
ما به دو تابع نیاز داریم. اولین مورد یک عدد اعشاری دریافت می کند و یک رشته را با نمایش فاکتوریل برمی گرداند.
توجه: عدد ورودی معمولا طولانی است.
دومی یک رشته با نمای فاکتوریل دریافت می کند و نمایش اعشاری را تولید می کند.
Coding decimal numbers with factorials is a way of writing out numbers in a base system that depends on factorials, rather than powers of numbers.
In this system, the last digit is always 0 and is in base 0!. The digit before that is either 0 or 1 and is in base 1!. The digit before that is either 0, 1, or 2 and is in base 2!, etc. More generally, the nth-to-last digit is always 0, 1, 2, …, n and is in base n!.
Read more about it at: http://en.wikipedia.org/wiki/Factorial_number_system
Example
The decimal number 463 is encoded as “341010”, because:
463 = 3×5! + 4×4! + 1×3! + 0×2! + 1×1! + 0×0!
If we are limited to digits 0..9, the biggest number we can encode is 10!-1 (= 3628799). So we extend 0..9 with letters A..Z. With these 36 digits we can now encode numbers up to 36!-1 (= 3.72 × 1041)
Task
We will need two functions. The first one will receive a decimal number and return a string with the factorial representation.
Note: the input number is at most a long.
The second one will receive a string with a factorial representation and produce the decimal representation.
Given numbers will always be positive.
راه حل ها (Solutions):
public class Dec2Fact {
public static String dec2FactString(long n) {
var sb = new StringBuilder();
var fRadix = 1;
while (n>0){
long r = n % fRadix;
n /= fRadix;
sb.append( r>9 ? (char)(r-10+'A') : ""+r);
fRadix++;
}
return sb.reverse().toString();
}
public static long factString2Dec(String s) {
long n=0L, fact=1L, fRadix=1L;
for (long r: new StringBuilder(s).reverse().toString().chars().mapToLong(x -> x>64 ? x-'A'+10 : x-'0').toArray()){
n += r*fact;
fact *= fRadix++;
}
return n;
}
}public class Dec2Fact {
private final static String baseNum = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
public static String dec2FactString(long nb) {
int radix = getRaidx(nb);
StringBuffer res = new StringBuffer();
for(int i = radix - 1; i >= 0; i--) {
int temp = (int)(nb / getFactorials(i));
res.append(baseNum.charAt(temp));
nb -= temp * getFactorials(i);
}
return res.toString();
}
public static long factString2Dec(String str) {
long res = 0;
String temp = new StringBuffer(str).reverse().toString();
for(int i = 0; i < temp.length(); i++) {
res += baseNum.indexOf(temp.charAt(i)) * getFactorials(i);
}
return res;
}
private static int getRaidx(long nb) {
for(int i = 0; ; i++)
if(getFactorials(i) >= nb)
return i;
}
private static long getFactorials(int num) {
if(num == 0)
return 1L;
long res = 1;
for(long i = 1; i <= num; i++)
res *= i;
return res;
}
}public class Dec2Fact {
public static String dec2FactString(long nb) {
String res = "";
String retRes = "";
int previous = 37;
while (previous != 1){
previous--;
long fact = findFact(previous);
int coeff = (int)Math.floor(1.0 *nb / fact);
if (coeff <= 0 && res == "") continue;
res += coeff + "x" + previous + "!+";
if (coeff>9){
char letter = (char)(coeff - 10 + 65);;
retRes += letter;
} else{
retRes += coeff;
}
nb -= coeff * fact;
}
return retRes+"0";
}
public static long factString2Dec(String str) {
long sumRes = 0;
for (int i = str.length()-1; i >= 0; i--){
long currFact = findFact(str.length() - i - 1);
sumRes += Character.getNumericValue(str.charAt(i)) * currFact;
}
return sumRes;
}
public static long findFact(long x){
long res = 1;
for (int i = 1; i <= x; i++){
res*=i;
}
return res;
}
}import java.util.*;
public class Dec2Fact {
public static final String translate = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
public static String dec2FactString(long nb) {
long count = 1;
long cur = nb;
String ret = "";
while(cur != 0L) {
ret = translate.toCharArray()[(int)(cur % count)] + ret;
cur /= count;
count++;
}
return ret;
}
public static long factString2Dec(String str) {
str = new StringBuilder(str).reverse().toString();
long ret = 0L;
long curFact = 1L;
for(int i = 1; i < str.length(); i++){
curFact *= i;
ret += curFact * translate.indexOf(str.toCharArray()[i]);
}
return ret;
}
}import java.util.List;
public class Dec2Fact {
static final List<Character> NUMS = List.of(
'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');
public static String dec2FactString(long nb) {
var quotient = nb;
var remainders = new StringBuilder();
for (int i = 1; i < NUMS.size() && quotient > 0; i++) {
remainders.append(NUMS.get((int) (quotient%i)));
quotient = quotient/i;
}
return remainders.reverse().toString();
}
public static long factString2Dec(String str) {
String reversed = new StringBuilder(str).reverse().toString();
long acc = 0;
for (int i = 0; i < reversed.length(); i++) {
Character c = reversed.charAt(i);
acc += NUMS.indexOf(c) * factorial(i);
}
return acc;
}
private static long factorial(long i) {
if (i < 1) return 1;
return i * factorial(i - 1);
}
}
