1. 首页
  2. 问答
  3. n在java中使用n和k的整数类型选择k

n在java中使用n和k的整数类型选择k

2011-07-20 45 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 + ...并让它溢出控制台:)） –

相关问题

 相关问题