解決二項函數的Python函數

我需要一個函數可以解決以下問題：對於二項函數nCr = k，給定r和k找到n。在數學nCr = n！/ r！（n-r）！我嘗試了以下，但它並沒有解決它。例如8C6 = 28，對於我的函數輸入是6和28，我想找到8.這可能沒有確切的整數，所以我想找到一個x> = n。解決二項函數的Python函數

""" 
I am approaching it this way, i.e. find the solution of a polynomial function iteratively, hope there is a better way""" 
"""I am approaching it this way, i.e. find the solution of a polynomial function iteratively, hope there is a better way""" 
def find_n(r,k): 
    #solve_for_n_in(n*(n-1)...(n-r)=math.factorial(r)*k 
    #in the above example solve_for_n(n*(n-1)(n-2)(n-3)(n-4)(n-5)=720*28) 

    sum=math.factorial(r)*k 
    n=r 
    p=1 
    while p<sum: 
     p=1 
     for i in range(0,r+2): 
      p*=(n-i+1) 
     n+=1 
    return n

謝謝。

來源

2016-03-03 white_chick

只是做數學題正確...你的想法顯然是存儲n /（nr）！在「sum」中並將其與r！k進行比較，但「sum」計算錯誤。（n-1）^ 2，則（n-2）^ 2 *（n-1）等等... – jomuel

可能的重複[對於二項函數nCr = k，給定r和k找到n]（http://stackoverflow.com/questions/35753215/for-binomial-function-ncr-k-given-r-and-k-find-n） –

嗨@jomuel我修改它和但有時候不會得到結果。 –

我在代碼中發現一個錯誤。

sum=n

你設置總和爲n 然後，

while sum<factorial(r)*k: 
    sum*=n

你再次ñ相乘之和。所以現在sum = n ** 2。這會更好：

while sum<factorial(r)*k: 
    n+=1 
    sum*=n

來源

2016-03-03 11:21:26 junoon53

沒問題。很高興能提供幫助:) – junoon53

這僅僅是這個問題如何可以走近的想法，同時保持高度的可讀性。

nCr = n!/{{r!}{n-r}!} = n(n-1)...(n-r+1)/{r!} 右側是一些值k。

開始於n = 2*(r+1)。

nCr < RHS => n是太小=>上升ň

nCr > RHS => n過大=>減少ň

nCr == RHS =>找到ň

... ... 繼續這樣做直到找到n或出現問題。

import math 

def find_n(r,k): 

    if k==1: 
     return r   # RHS is 1 when n and r are the same 

    RHS = math.factorial(r) * k 

    possible_n = 2 * r; 
    possible_numerator = math.factorial(possible_n) 
    possible_denom = math.factorial(possible_n - r) 

    while True: 
     # current n is too small 
     if (possible_numerator // possible_denom) < RHS: 
      # try possible_n + 1 
      possible_n = possible_n + 1 
      possible_numerator = math.factorial(possible_n) 
      possible_denom = math.factorial(possible_n - r) 

     elif (possible_numerator // possible_denom) > RHS: 
      # try possible_n - 1 
      possible_n = possible_n - 1 
      possible_numerator = math.factorial(possible_n) 
      possible_denom = math.factorial(possible_n - r) 

     elif (possible_n == r): 
      print ("***n smaller than r***"); 
      sys.exit(0); 

     elif (possible_numerator // possible_denom) == RHS: 
      return possible_n 





print(find_n(6, 28))  # should print 8 

print(find_n(6, 462))  # should print 11 

print(find_n(6, 3003))  # should print 14 

print(find_n(5, 3003))  # should print 15

來源

2016-03-03 21:42:04

如果性能受到關注，請開始緩存映射或數組中的階乘值。 –

謝謝，當你提到'x> = n'時，你選擇n = 2 *（r + 1） –

的理由是什麼？現在，從'r + 1'開始搜索並沒有太多的意義，因爲如果你開始在地圖中緩存值，這將不會有太大的幫助。如果'r'很小，'2 * r + 1'並不重要，但隨着'r'的大小增長，階乘會變得昂貴，並且緩存可以讓您基本上得到階乘O（1）。這似乎是最簡單的方法，牢記可讀性。 –

我使用的計算二項式係數的函數來實現該功能nCr的

def binomial(n,k): 
    return 1 if k==0 else (0 if n==0 else binomial(n-1, k) + binomial(n-1, k-1)) 

def nCr(r,c): 
    n=0 
    b=binomial(n,r) 
    while b<c: 
     n=n+1 
     b=binomial(n,r) 
     if b==c: 
      return n 

    return None

nCr的（6,28）

來源

2016-05-10 11:54:18 merrais

解決二項函數的Python函數

回答

相關問題