2

これは CodeSprint3 の問題ですhttps://cs3.interviewstreet.com/challenges/dashboard/#problem/50877a587c389 基本的に問題は、与えられた n と r に対して可能な組み合わせ nCr の数を計算することです。また、1 <= n < = 1000000000 および 0 <= r <= n。142857 を法とするすべての回答を出力します。

 Since 6C4=6!/4! 2!
        =6*5/2!     
        =6*5/2*1

すべてのステップで除算を使用してオーバーフローを回避できると考えました。つまり、nの値から始めます（この場合、nは6です）。n を減分し、前の値で乗算します (したがって、これは 6*5 になります) 分母で除​​算を実行し、それを減分します ( 6*5 /2 および分母 2 は 1 になります) n が 2 つの分母の最大値よりも小さくなるまで、手順を繰り返します同じ反復回数で除数 (分母の最小値は 1 になります)

   int count(int n,int r)
   {int maxDen=r>(n-r)?r:n-r;      //larger number in the denominator
    int minDen=n-maxDen;           //the smaller number in denominator
    double num=1;
    for(int j=n;j>maxDen;j--)     
     {num=j*num;              //for C(6,4) example num=6*5 and so on   
    // System.out.println("num "+num +" minDen "+minDen);
       num=num/minDen;         //divide num 6*5 in this case by 2
       minDen--;
      }
   num=num%142875;           //output the result modulo 142875
  return (int) num;
}

しかし、より多くの除算が実行されるにつれて精度が失われる可能性があるため、間違った値が得られますが、一部の値に対しては正しい出力が得られます.22 17 では正しいが、24 17 では正しくない.

(22 17) = 26334 //gives Correct value

(24 17)= 60353 //wrong value correct value is 60390

(25,17)=81450 //wrong value correct value is 81576

(16 15)= 16 //gives correct value

(87 28)= 54384 //wrong value correct value is 141525

num を BigDecimal として使用しようとしましたが、その結果、すべてを BigDecimal に置き換えて操作を実行する必要がありました。出力は、上記のコードで正しい結果をもたらした入力と同じでしたが、間違った結果をもたらした入力の場合は、プログラムは例外をスローします

 Exception in thread "main" **java.lang.ArithmeticException: Non-terminating   decimal  expansion; no exact representable decimal result.**
at java.math.BigDecimal.divide(Unknown Source)
at Combination.NcRcount2.count(NcRcount2.java:16)
at Combination.NcRcount2.main(NcRcount2.java:37)

16 行目は num=num.divide(minDen); です。//以前に使用された num/minDen の代わりに、num と minDen の両方がこの場合 BigDecimal です

数値が正確な 10 進数表現を持たない場合でも、BigDecimal の任意の精度を考えると、例外がスローされなければ、結果のエラーは最小限に抑えられます。** float または double の除算の結果が正確な 10 進表現を持たない場合、例外がスローされないのはなぜですか?**

動的計画法のアプローチで BigDecimal を使用して結果を検証しました。

   C(n,r)=C(n-1,r-1)+C(n-1,r)

私には見えるように、これはすべての場合に正しく機能しますが、より良い方法があるはずです

  BigDecimal Comb (int n, int k)
   {  if(k>n-k)
       k=n-k;
       BigDecimal B[][]=new BigDecimal[n+1] [k+1];

    for (int i = 0; i <= n; i++)
   { int min;
     if(i>=k)
      min=k;
    else
     min=i;
   for (int j = 0; j <= min; j++)
    { if (j == 0 || j == i)
           B[i][j] =new BigDecimal(1);
       else{ 
           if(j>i-j)
            B[i][j]=B[i][i-j];
            else
            B[i][j] = B[i - 1][j - 1].add(B[i - 1] [j]);
          }
    }
 }
BigDecimal div=new BigDecimal(142857);
return B[n][k].remainder(div);
}

BigDecimal を使用せずにこれを行うより良い方法を提案してください

4

4 に答える 4

2 
public class Solution {

public static void main(String arg[]) {
    Scanner s = new Scanner(System.in);
    List<BigInteger> ar = new ArrayList<BigInteger>();
    int tot = Integer.parseInt(s.nextLine());
    BigInteger max = BigInteger.ZERO;
    for (int i = 0; i < tot; i++) {
        String str[] = s.nextLine().split(" ");
        Long n1 = Long.parseLong(str[0]);
        Long r1 = Long.parseLong(str[1]);
        Long nr1 = n1 - r1;
        BigInteger n = BigInteger.valueOf(n1);
        BigInteger r = BigInteger.valueOf(r1);
        BigInteger nr = BigInteger.valueOf(nr1);
        ar.add(n);
        ar.add(r);
        ar.add(nr);
        if (n.compareTo(max)==1) {
                max=n;
        }
        if (r.compareTo(max)==1) {
            max=r;
        }
        if (nr.compareTo(max)==1) {
            max=nr;
        }

    }
    HashMap<BigInteger,BigInteger> m=new HashMap<BigInteger,BigInteger>();
    m.put(BigInteger.ZERO, BigInteger.ONE);
    BigInteger fact=BigInteger.ONE;
for(BigInteger i=BigInteger.ONE;i.compareTo(max.add(BigInteger.ONE))==-1;i=i.add(BigInteger.ONE)){
    fact=fact.multiply(i);
    if(ar.contains(i)){
        m.put(i, fact);
    }
}

for(int i=0;i<ar.size();i=i+3){
    BigInteger n=m.get(ar.get(i));
    BigInteger r=m.get(ar.get(i+1));
    BigInteger nr=m.get(ar.get(i+2));
    BigInteger rem=r.multiply(nr);
    BigInteger act=n.divide(rem);
    BigInteger res=act.remainder(BigInteger.valueOf(142857));
    System.out.println(res);
}

}

}

このコードが役立つと思います。

于 2013-12-25T20:58:52.497 に答える
1

かなり単純な実装:

public long combinations(int n, int k) {
    BigInteger factorialN = factorial(n);
    BigInteger factorialK = factorial(k);
    BigInteger factorialNMinusK = factorial(n - k);
    return factorialN.divide(factorialK.multiply(factorialNMinusK)).longValue();;
}

private BigInteger factorial(int n) {
    BigInteger ret = BigInteger.ONE;
    for (int i = 1; i <= n; ++i) ret = ret.multiply(BigInteger.valueOf(i));
    return ret;
}
于 2014-08-02T21:32:07.393 に答える
0

BigDecimal コードの例外に関する質問の部分は明確ではないため、コメントしません。

nCr を計算するための一連の乗算と除算に関して、wikipediaは実装が簡単な式を示しています。質問のコードの最初のセクションは、それと同等である可能性があります。これは、すぐ下の Python コードの一部である可能性があります。64 ビット整数演算を使用して最大 61C30 を計算します。62C31 には、もう 1 つか 2 つ必要です。

def D(n, k):
    c, j, k = 1, n, min(k,n-k)
    for i in range(1,k+1):
        c, j = c*j/i, j-1
    return c

すべての除算が正確な除算であるこの計算順序が機能する理由は、いくつかの代数nC(j+1) = nCj * (n-j)/(j+1)から簡単に検証できるからです。nCj = n!/j!(n-j)!つまり、小数点以下の桁数を必要とせずに、完全に整数演算nCrで大規模な計算を行うことができます。nr

仮定しK=142857ます。K を法とする中間項の簡約は問題を引き起こし、実行不可能な場合があることに注意してください。分子が K を法として減らされると、一部の除算は通常の算術では正確になりません。K が素数の場合、拡張 GCD アルゴリズムを使用して、すべての数値について K を法とする逆数を見つけることができます。しかし、K=3*9*11*13*37 および K を法とする逆数は、ベズーの補題といくつかの剰余代数の結果として、3、11、13、または 37 の倍数である数には存在しません。

于 2012-11-06T03:12:39.363 に答える