白駿2407号:組み合わせ

方法

nCr=n!/(r!∗(n−r)!)nCr = n!/(r!*(n-r)!)nCr=n!/(r!∗(n−r)!).

factorial再帰関数としてのみ実施するとタイムアウトになります.

再計算ではなく、以前の値をすぐに使用する必要があります.これはDynamic Programming問題の메모이제이션でよく使われる部分で、ここでよく知ってほしいです.

正解

n,m = list(map(int,input().split(" ")))

dp = [0]*(n+1) // 이미 구한 factorial값을 저장합니다

def factorial(n):
    #0!은 1입니다
    if n == 0:
        dp[0] = 1
        return 1
    #1!은 1입니다
    if n == 1:
        dp[1] = 1
        return 1
    #factorial(n)값이 이전에 계산해서 dp에 저장되어 있다면
    if dp[n] !=0:
        return dp[n] #저장된 값을 그대로 씁니다
    else: #저장되어진 값이 없다면
        dp[n] = n*factorial(n-1) #재귀를 통해 새롭게 구합니다
        return dp[n]
print((factorial(n)//factorial(m)//factorial(n-m)))        

その他

単純除算が正しくない

#둘의 결과는 다릅니다.
print((factorial(n)/factorial(m)/factorial(n-m))) 
#결과: 1.9564640595300215e+28
print((factorial(n)//factorial(m)//factorial(n-m))) 
#결과: 19564640595300216439731236256

どうして結果が違うの?

부동소수점.浮動小数点の定義は次のとおりです.

コンピュータ上でエラーを近似表示する場合、小数点の位置を固定するのではなく、その位置を表す数字を単独で記入します.
簡単に言えば、私たちが書いた5.0は、私たちのコンピュータが4.999999999999の値で格納されていることを示しています.
factorial(n)は整数、factorial(m)も整数ですが、デフォルトではPythonは意外にも区切り値を返します.
これらの相違が非常に大きな値に適用される場合、結果は異なる場合があります.

浮動小数点の問題を解決する方法は次のとおりです.

第一.シェアを表す//を使用して除算を実行

第二.Decimalソフトウェアパッケージと関数を使用します.

Decimal(5.0)は、4.9999999999ではなく5.0を正しく格納します.

どうしてこんな不便な浮動小数点を使うのですか.

小数点を正確に計算するには、1/3=0.333333333...無限長、メモリ不足.

計算が正確で良いのですが、メモリを考慮してこの値を切り捨てる必要があるところもあるので、これが浮動小数点導入の原因だと思います.(これは私の推測ではありません)