C语言编程：输入正整数n(<=1000),输出组合数C(2n,n)？

Python016

C语言编程：输入正整数n(<=1000),输出组合数C(2n,n)？,第1张

令C(m,n)表示从m个数中选取n个数的组合个数

则有递推关系：C(m,n)=C(m-1,n-1)+C(m-1,n)

可采用二维数组dp[m][n]保存C(m,n)的结果，然后从小到大递推计算即可

但注意到m维的结果只和m-1维有关，因此可以用一维数组进行简化

令dp[n]表示当前为止，选出n个数的组合个数，注意外层遍历m次，内层要逆序遍历

最后由于n可能取到1000，结果会很大，一般取余表示防止溢出

C语言代码如下所示：

#include <stdio.h>

long long dp[1001]// 结果可能很大，用长整型

// 但长整型最大也只能表示到C(66,33) = 7219428434016265740

// 因为输入n最大为1000，所以结果可取余表示

const int MOD = 1e9 + 7// 10^9+7，用于结果取余表示

int main() {

  int n

  scanf("%d", &n)

  int m = 2 * n

  dp[0] = 1// 初始化，C(m,0)=1

  for (int i = 0i <m++i) { // 外层遍历m次

      for (int j = nj >= 1--j) { // 内存要倒序遍历

          //dp[j] = dp[j] + dp[j - 1]// 若不取余，长整型最大只能表示到n=33

          dp[j] = (dp[j] + dp[j - 1]) % MOD// 取余显示，防止结果溢出

      }         

  }

  printf("C(%d,%d) = %lld\n", m, n, dp[n])

  return 0

}

结果如图：

编译通过，示例如上，C(6,3)=20，结果正确，望采纳~

#include<stdio.h>

int main()

{

int i,n

float sum=0

printf("请输入n：\n")

scanf("%d",&n)

for(i=1i<=ni++)

sum+=(float)1/i

printf("前n项和为sum=%.4f\n",sum)

return 0

}

K&R C

起初，C语言没有官方标准。1978年由美国电话电报公司(AT&T）贝尔实验室正式发表了C语言。布莱恩·柯林汉（Brian Kernighan） 和 丹尼斯·里奇（Dennis Ritchie） 出版了一本书，名叫《The C Programming Language》。这本书被 C语言开发者们称为K&R，很多年来被当作 C语言的非正式的标准说明。人们称这个版本的 C语言为K&R C。

K&R C主要介绍了以下特色：

结构体（struct）类型

长整数（long int）类型

无符号整数（unsigned int）类型

把运算符=+和=-改为+=和-=。因为=+和=-会使得编译器不知道使用者要处理i = -10还是i =- 10，使得处理上产生混淆。

即使在后来ANSI C标准被提出的许多年后，K&R C仍然是许多编译器的最 准要求，许多老旧的编译器仍然运行K&R C的标准。

可以通过除法运算符( / )和求余运算符( % )结合循环来实现分别输出一个整数的每位数字。 具体实现方法可以参考如下程序及注释说明： #includevoid main(){ int dataint tempprintf("请输入一个整数：")scanf("%d", &data)//