Common denominators

kata programming

مخرج مشترک

شما لیستی از دلایل منطقی را به فرم زیر خواهید داشت.

{ {numer_1, denom_1} , ... {numer_n, denom_n} } 
or
[ [numer_1, denom_1] , ... [numer_n, denom_n] ] 
or
[ (numer_1, denom_1) , ... (numer_n, denom_n) ] 

که همه اعداد int مثبت هستند. شما باید نتیجه ای را به شکل زیر تولید کنید:

(N_1, D) ... (N_n, D) 
or
[ [N_1, D] ... [N_n, D] ] 
or
[ (N_1', D) , ... (N_n, D) ] 
or
{{N_1, D} ... {N_n, D}} 
or
"(N_1, D) ... (N_n, D)"

بسته به زبان (به نمونه آزمایشات مراجعه کنید) که در آن D تا حد ممکن کوچک است و

N_1/D == numer_1/denom_1 ... N_n/D == numer_n,/denom_n.

مثال ها:

convertFracs [(1, 2), (1, 3), (1, 4)] `shouldBe` [(6, 12), (4, 12), (3, 12)]

نکته:

با توجه به این واقعیت که اولین ترجمه ها مدتها پیش نوشته شده است – بیش از 6 سال – این ترجمه های اولیه فقط دارای کسرهای غیر قابل کاهش هستند.

ترجمه های جدید دارای کسر قابل کاهش هستند. برای ایمن بودن، بهتر است با کار بیشتری با ساده کردن کسرها انجام بدیم، حتی اگر مجبور نباشیم.


Common denominators

You will have a list of rationals in the form

{ {numer_1, denom_1} , ... {numer_n, denom_n} } 
or
[ [numer_1, denom_1] , ... [numer_n, denom_n] ] 
or
[ (numer_1, denom_1) , ... (numer_n, denom_n) ] 

where all numbers are positive ints. You have to produce a result in the form:

(N_1, D) ... (N_n, D) 
or
[ [N_1, D] ... [N_n, D] ] 
or
[ (N_1', D) , ... (N_n, D) ] 
or
{{N_1, D} ... {N_n, D}} 
or
"(N_1, D) ... (N_n, D)"

depending on the language (See Example tests) in which D is as small as possible and

N_1/D == numer_1/denom_1 ... N_n/D == numer_n,/denom_n.

Example:

convertFracs [(1, 2), (1, 3), (1, 4)] `shouldBe` [(6, 12), (4, 12), (3, 12)]

Note:

Due to the fact that the first translations were written long ago – more than 6 years – these first translations have only irreducible fractions.

Newer translations have some reducible fractions. To be on the safe side it is better to do a bit more work by simplifying fractions even if they don’t have to be.

Note for Bash:

input is a string, e.g “2,4,2,6,2,8” output is then “6 12 4 12 3 12”


const gcd = (a, b) => b ? gcd(b, a % b) : a;
const lcm = (a, b) => a * b / gcd(a, b);

function convertFrac(arr) {
  const cd = arr.reduce((a, [_, d]) => lcm(d, a), 1);
  return arr.map(([n, d]) => `(${n * cd/d},${cd})`).join('');
}
class Fracts {
    
    static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    static long lcm(long a, long b) {
        return a * b / gcd(a, b);
    }

    public static String convertFrac(long[][] lst) {
        long lcmall = 1;
        long[][] newlst = new long[lst.length][2];
        for  (int i = 0; i < lst.length; i++) {
            long g = gcd(lst[i][0], lst[i][1]);
            newlst[i][0] = lst[i][0] / g;
            newlst[i][1] = lst[i][1] / g;
        }
        for (long[] item : newlst) {
            lcmall = lcm(lcmall, item[1]);
        }
        String result = "";
        for (long[] item : newlst) {
            result += "(" + (item[0] * lcmall / item[1]) + "," + lcmall + ")";
        }
        return result;
    }
}
import java.util.Arrays;
import java.util.stream.Collectors;

public class Fracts {
  
  public static long gcd(long a, long b) {
    return b==0 ? a : gcd(b, a%b);  
  }
  
  private static long lcm(long a, long b)
  {
      return a * (b / gcd(a, b));
  }
  
  public static String convertFrac(long[][] lst) {
    if(lst.length == 0) 
      return "";
    
    long lcm = Arrays.stream(lst).map( arr -> arr[1] ).reduce(lst[0][1], (a,b) -> lcm(a,b));
    long gcd = Arrays.stream(lst).map(arr -> arr[0] * lcm/arr[1]).reduce(lcm, (a,b) -> gcd(a,b));
    return "(" + Arrays.stream(lst).mapToLong(arr -> (arr[0] * lcm/arr[1])/gcd).mapToObj(l -> ((Long)(l)).toString()).collect(Collectors.joining("," + (lcm/gcd) + ")(")) +"," + (lcm/gcd)+")"; 
  }

}
import static java.math.BigInteger.valueOf;
import static java.util.Arrays.stream;
import static java.util.stream.Collectors.joining;

import java.util.function.LongBinaryOperator;

class Fracts {
  static LongBinaryOperator gcd = (a, b) -> valueOf(a).gcd(valueOf(b)).longValue();
  static LongBinaryOperator lcm = (a, b) -> b / gcd.applyAsLong(a, b) * a;

  static String convertFrac(long[][] lst) {
    if (lst.length == 0) return "";

    long lcm = stream(lst).map(r -> r[1]).reduce(lst[0][1], Fracts.lcm::applyAsLong);
    long gcd = stream(lst).map(r -> lcm * r[0] / r[1]).reduce(lcm, Fracts.gcd::applyAsLong);
    var str = stream(lst).mapToLong(r -> lcm * r[0] / r[1] / gcd).mapToObj(Long::toString);
    return "(" + str.collect(joining("," + lcm / gcd + ")(")) + "," + lcm / gcd + ")";
  }
}
import java.util.Arrays;
import java.util.stream.Collectors;

public class Fracts {

    public static String convertFrac(long[][] lst) {
        final Long dividor = Arrays.stream(lst)
                .map(pair -> new Long[]{pair[0], pair[1]})
                .map(Fracts::divideByGreatestCommonDivider)
                .map(longs -> longs[1])
                .reduce(1L, Fracts::leastCommonMultiple);

        return Arrays.stream(lst)
                .map(pair -> pair[0] * dividor / pair[1])
                .map(aLong -> String.format("(%d,%d)", aLong, dividor))
                .collect(Collectors.joining());
    }

    private static Long greatestCommonDivider(Long a, Long b) {
        return b == 0 ? a : greatestCommonDivider(b, a % b);
    }

    private static Long[] divideByGreatestCommonDivider(Long[] pair) {
        Long gcd = greatestCommonDivider(pair[0], pair[1]);
        return new Long[]{pair[0] / gcd, pair[1] / gcd};
    }

    private static Long leastCommonMultiple(Long a, Long b) {
        return Math.abs(a * b) / greatestCommonDivider(a, b);
    }
}
public class Fracts {
  public static String convertFrac(long[][] list) {
    reduceFractions(list);
    long lcm = calculateTotalLcm(list);
    StringBuilder result = new StringBuilder();
    for(long[] fraction : list) {
      long ratio = lcm / fraction[1];
      result.append('(')
            .append(fraction[0] * ratio).append(',').append(fraction[1] * ratio)
            .append(')');
    }
    return result.toString();
  }
  
  private static void reduceFractions(long[][] list) {
    for(int i = 0; i < list.length; i++) {
      long[] fraction = list[i];
      long gcd = gcd(fraction[0], fraction[1]);
      fraction[0] = fraction[0] / gcd;
      fraction[1] = fraction[1] / gcd;
    }
  }
  
  private static long calculateTotalLcm(long[][] list) {
    long lcm = 1L;
    for(long[] fraction : list) {
      lcm = lcm(lcm, fraction[1]);
    }
    return lcm;
  }
  
  private static long lcm(long a, long b) {
    return a * b / gcd(a,b);
  }
  
  private static long gcd(long a, long b) {
    if(b == 0) {
      return a;
    } else {
      return gcd(b, a % b);
    }
  }
}
import java.util.Arrays;
public class Fracts {
  public static String convertFrac(long[][] lst) {
    if (lst.length == 0)
      return "";
    long denominadores[] = new long[lst.length],minimoComun;
    String dat="";
    for (int i = 0; i < lst.length; i++) {
      simplificar(lst, i);
      denominadores[i] = lst[i][1];
    }
    minimoComun = mcm(denominadores);
    for (int i = 0; i < lst.length; i++) {
      dat += "(" + (minimoComun / lst[i][1] * lst[i][0]) + "," + minimoComun + ")";
    }
    dat = dat.trim();
    return dat;
  }

  private static void simplificar(long[][] lst, int i) {
    if (lst[i][1] == 0 || lst[i][0] == 0)
      return;
    long max = Math.max(lst[i][1], lst[i][0]);
    for (int j = 2; j <= max; j++) {
      while (lst[i][0] % j == 0 && lst[i][1] % j == 0) {
        lst[i][0] /= j;
        lst[i][1] /= j;
      }
    }
  }

  private static long mcm(long[] denominadores) {
    Arrays.sort(denominadores);
    long cantidad = denominadores[denominadores.length - 1];
    long min = 1;
    for (int i = 2; i <= cantidad; i++) {
      while (esPosibleAunDividir(i, denominadores)) {
        min *= i;
        for (int j = 0; j < denominadores.length; j++) {
          if (denominadores[j] % i == 0 && denominadores[j] != 1) {
            denominadores[j] = denominadores[j] / i;
          }
        }
      }
    }
    return min;
  }

  private static boolean esPosibleAunDividir(int i, long[] denominadores) {
    for (int j = 0; j < denominadores.length; j++) {
      if (denominadores[j] % i == 0) {
        return true;
      }
    }
    return false;
  }
}
public class Fracts {

    public static String convertFrac(long[][] lst) {
        for(int i = 0; i < lst.length; i++) {
            lst[i] = reduction(lst[i][0],lst[i][1]);
        }

        for(int i = 0; i < lst.length - 1; i++) {
            long denom1 = lst[i][1];
            long denom2 = lst[i+1][1];
            long gcd = euclidean(denom1,denom2);
            long lcm = denom1 * denom2 / gcd;

            int j = denom1 != lcm ? 0 : i + 1;
            while(j <= i + 1) {
                long multiplier = lcm / lst[j][1];
                lst[j] = new long[]{multiplier * lst[j][0], lcm};
                j++;
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < lst.length; i++) {
            sb.append("("+lst[i][0]+","+lst[i][1]+")");
        }

        return sb.toString();
    }

    public static long[] reduction(long a, long b) {
        long factor = euclidean(a, b);
        return new long[]{a / factor, b / factor};
    }

    public static long euclidean(long a, long b) {
        return a % b != 0 ? euclidean(b, a%b) : b;
    }
}

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

نشانی ایمیل شما منتشر نخواهد شد.