1. 首頁
  2. 問答
  3. n在java中使用n和k的整數類型選擇k

n在java中使用n和k的整數類型選擇k

2011-07-20 46 views
1

我已經給出了一個需要使用n和k來計算n選擇k問題的任務。 我擁有的條件是我不能使用int以外的其他數據類型。 我無法使用這個包，例如BigInteger。
int n和k可以是低於200的任何數字。 如何避免數量增長過大？因爲程序吹時n > 20。
謝謝。n在java中使用n和k的整數類型選擇k

維基百科："n Choose k" or "Binomial coefficient"

來源

2011-07-20 Jeff

+0

你不行。英特爾不能擁有那麼大的數字，如果這就是你可以使用的所有數字，就是這樣。如果你可以使用整數數組，它將是可行的，但是一個PITA。整數集合會更好地工作，但它們在技術上不是整數。在第二個想法中，你可以簡單地輸出n的表示式，用階乘公式輸出k。但這可能不是教練的意圖。 – bdares

+0

這是功課嗎？ –

+0

@曼努埃爾塞爾瓦顯然是 –

回答

1

我認爲這個問題需要你創建自己的數據結構，可容納龐大的數字或alteast代表龐大的數字。一旦完成，剩下的就是微不足道的。您可能想看看BigInteger的源代碼，看看它們是如何實現的。

來源

2011-07-20 08:39:10

+0

這也是我的想法，但他指出，他不允許使用任何東西，除了整數。這是非常具體的，不允許對象類型。 – bdares

3

使用遞歸關係式：（N，K）=（N-1，K-1）+（N-1，K）

基例：（N，0）= 1; （0，k）= 0

來源

2011-07-20 08:41:01

+0

@abh這將導致大數字 –

+1

+1的溢出，這是保持解決方案儘可能低的簡單方法。如果最終解決方案比int.MaxValue大，則沒有解決方案。 –

+0

@ Scorpi0：是的，作業可能只是爲了學習遞歸。一種方法是打印出字面上的加法：（200,100）= 1 + 0 + 0 + 1 + 0 + ...並讓它溢出控制檯:)） –

相關問題

 相關問題