Decimal to Factorial and Back

kata programming

مساله:

کدگذاری اعداد اعشاری با فاکتوریل راهی است برای نوشتن اعداد در یک سیستم پایه که به فاکتوریل بستگی دارد ، نه به توان اعداد.

در این سیستم، آخرین رقم همیشه 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);
    }

}

دیدگاهتان را بنویسید