台东县网站建设_网站建设公司_SSG_seo优化

第1关：组合数学之排列问题

任务描述
本关任务：盒子里有n个不同数字的球，从中取出k个排成一排，每个球最多被选择一次，请通过编程计算出有多少种排列方案。例如盒子里有3个球，选出其中2个球排成一列，共6种排列方案：(1,2)，(1,3)，(2,1)，(2,3)，(3,1)，(3,2)。

相关知识
为了完成本关任务，你需要掌握：1.乘法原理，2.阶乘运算符。

乘法原理
做一件事，假设有n个步骤，第i个步骤有p
i
​
种方案，则完成这件事总共有p
1
​
×p
2
​
×..×p
n
​
种方案，这种计数方法称之为乘法原理。

对于本关任务，将排列方案的种数记P(n,k)，由乘法原理可得，每个步骤选择一个球，第1步有n中选择，不管第1步选择了什么，第2步都有(n−1)种选择，以此类推，第k步有(n−k+1)种选择，所以最终的方案数为：

P(n,k)=n×(n−1)×(n−2)×..×(n−k+1)

阶乘运算符
阶乘是一种数学运算符号，一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，符号记为!，例如自然数n的阶乘写作n!，特别的记0的阶乘为0!=1，用数学公式表示：

n!=1×2×3×..×n

另外也可以用递归方式表达：

0!=1

n!=(n−1)!×n

回顾本关的答案为P(n,k)，也可以通过阶乘表示：

P(n,k)=n!/(n−k)!

特别的，P(n,n)=n!。

编程要求
本关的编程任务是补全右侧代码片段Factorial和Permutation中Begin至End中间的代码，具体要求如下：

在Factorial中，根据阶乘的定义直接计算n的阶乘或通过递归表达式计算n的阶乘，并返回结果。

在Permutation中，根据乘法原理，计算本关卡排列问题的答案P(n,k)，并返回结果。

测试说明
平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。

以下是平台的测试样例：

测试输入：4 3
预期输出：Permutation(4,3)=24

输入格式：n k
输出格式：Permutation(n,k)=P(n,k)

开始你的任务吧，祝你成功！

附加知识点：
做一件事，假设有n个办法，第i个办法有p
i
​
种方案，则完成这件事总共有p
1
​
+p
2
​
+..+p
n
​
种方案，这种计数方法称之为加法原理。

#include <iostream> typedef long long int64; int64 Factorial(int64 n) { // 请在这里补充代码，完成本关任务 /********* Begin *********/ if (n == 0) { return 1; // 0的阶乘为1 } return n * Factorial(n - 1); // 递归计算阶乘 /********* End *********/ } int64 Permutation(int64 n, int64 k) { // 请在这里补充代码，完成本关任务 /********* Begin *********/ // 排列数公式：P(n,k) = n! / (n-k)! return Factorial(n) / Factorial(n - k); /********* End *********/ } int main(int argc, const char * argv[]) { int64 n, k; scanf("%lld %lld", &n, &k); int64 p = Permutation(n, k); printf("Permutation(%lld,%lld)=%lld\n", n, k, p); return 0; }

第2关：组合数学之组合问题

任务描述
本关任务：盒子里有n个不同数字的球，从中取出k个形成一个组合，也就是与顺序无关，每个球最多被选择一次，请通过编程计算出有多少种选择方案。例如盒子里有3个球，选出其中2个球排成一列，共3种排列方案：(1,2)，(1,3)，(2,3)。

相关知识
为了完成本关任务，你需要掌握：1.组合计数原理，2.组合计数性质。

组合计数原理
回顾上一个关卡，将从n个球中有顺序的选择k个球的排列方案的种数记为P(n,k)。本关卡中，将从n个球中无顺序的选择k个球的选择方案的种数记为C(n,k)。那么，把n选k的有顺序的排列问题P(n,k)看成两个步骤：

Step1：从n里面无顺序的选择k个球，C(n,k)；

Step2：把这k个球进行全排列，P(k,k)。

由乘法原理知P(n,k)=C(n,k)×P(k,k)，通过左右移位可得：

C(n,k)=P(n,k)/P(k,k)=(n!/(n−k)!)/(k!)

组合计数性质
C(n,k)在组合计数中有着极其重要的作用和地位，一些常用的性质如下：

性质一：C(n,0)=C(n,n)=1，从n个里面选0个和选n个都只有一种选法，也就是不选和全选；

性质二：C(n,k)=C(n,n−k)，从n个里面选k个的方案种数等于选n−k个方案种数，因为选了k个以后剩下的数恰好有n−k个，因此选k个和选n−k个的方案一一对应；

性质三：C(n,k)+C(n,k+1)=C(n+1,k+1)，这是组合计数的递推公式，常用于预处理。原因是从n+1个数里选k+1个数有两种办法：要么选第1个数，要么不选第1个数。如果选择第1个数，则问题转换为从n个数里选择k个数C(n,k)；如果不选择第1个数，则问题转换为从n个数里选择k+1个数C(n,k+1)。这两种办法是不重复无遗漏的，通过加法原理即可得到C(n+1,k+1)=C(n,k)+C(n,k+1)。

编程要求
本关的编程任务是补全右侧代码片段Factorial和Combination中Begin至End中间的代码，具体要求如下：

在Factorial中，直接计算n的阶乘或通过递归表达式计算n的阶乘，并返回结果。

在Combination中，根据组合计数原理及其性质，计算本关卡组合问题的答案C(n,k)，并返回结果。

测试说明
平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。

以下是平台的测试样例：

测试输入：4 3
预期输出：Combination(4,3)=4

输入格式：n k
输出格式：Combination(n,k)=C(n,k)

开始你的任务吧，祝你成功！

#include <iostream> typedef long long int64; int64 Factorial(int64 n) { // 请在这里补充代码，完成本关任务 /********* Begin *********/ if (n == 0) { return 1; // 0的阶乘为1 } return n * Factorial(n - 1); // 递归计算阶乘 /********* End *********/ } int64 Combination(int64 n, int64 k) { // 请在这里补充代码，完成本关任务 /********* Begin *********/ // 处理边界条件：选0个或选n个，只有1种方案 if (k == 0 || k == n) { return 1; } // 利用组合性质：C(n,k) = C(n, n-k)，减少计算量（可选优化） if (k > n - k) { k = n - k; } // 组合数公式：C(n,k) = n! / (k! * (n-k)!) return Factorial(n) / (Factorial(k) * Factorial(n - k)); /********* End *********/ } int main(int argc, const char * argv[]) { int64 n, k; scanf("%lld %lld", &n, &k); int64 c = Combination(n, k); printf("Combination(%lld,%lld)=%lld\n", n, k, c); return 0; }

第3关：二项式展开与杨辉三角

任务描述
本关任务：了解杨辉三角与二项式定理之间的关系，并计算(a+b)
n
展开式的各项系数，例如(a+b)
2
=a
2
+2ab+b
2
，系数分别为1，2，1。

相关知识
为了完成本关任务，你需要掌握：1.杨辉三角，2.二项式定理。

杨辉三角
为了方便在数学公式中描述组合数C(n,k)，将组合数即为C
n
k
​
。组合数在数学中占据重要地位，与组合数相关的最重要的两个内容就是杨辉三角和二项式定理。

杨辉三角作为中国古代数学的杰出研究成果之一，它把二项式展开的系数图形化，并且把组合数内在的一些代数性质直观地在图形中体现出来，是一种离散型的数与形的结合，形如下图：

可以看出，杨辉三角是非常有规律的一些数据，具有很多重要的性质：

性质一：除了最外层的数为1之外，每个数字等于上一行的左右两个数字之和，可用此性质写出整个杨辉三角；

性质二：每行数字左右对称，第n行的第k个数和第n−k+1个数相等。由1开始到中间位置逐渐变大，然后从中间位置开始到末尾位置逐渐变小为1；

性质三：第n行的数字有n+1项；

性质四：第n行的数字的和为2
n
；

性质五：第n行的第k个数可表示为 C(n−1,k−1)，即为从n−1个不同元素中取k−1个元素的组合数；

性质六：(a+b)
n
的展开式中的各项系数依次对应杨辉三角的第(n+1)行中的每一项。

二项式定理
二项式定理（Binomial theorem）由艾萨克·牛顿提出，因此又称之为牛顿二项式定理。该定理给出两个数之和的整数次幂展开为类似项之和的恒等式，用数学公式表示为：

(a+b)
n
=∑
k=0
n
​
C
n
k
​
×a
n−k
×b
k

当n取不同值时可以得到以下示例：

当n=0时，(a+b)
0
=1；

当n=1时，(a+b)
1
=a+b；

当n=2时，(a+b)
2
=a
2
+2ab+b
2
；

当n=3时，(a+b)
3
=a
3
+3a
2
b+3ab
2
+b
3
；

当n=4时，(a+b)
4
=a
4
+4a
3
b+6a
2
b
2
+4ab
3
+b
4
。

可以发现，系数正好与杨辉三角一致，通过运用杨辉三角的性质递推求解出各项系数，但是这个递推算法的时间复杂度为O(n
2
)。特别的，利用组合数学的一个重要性质（如下）可以直接以O(n)的时间复杂度计算出第n层的各项系数，而不需要借助第n−1层的各项系数。根据组合数的定义有如下两个公式：

C(n,k+1)=n×(n−1)×..×(n−k)/(k+1)!

C(n,k)=n×(n−1)×..×(n−k+1)/(k)!

通过第一式子除以第二个式子，得到：

C(n,k+1)/C(n,k)=(n−k)/(k+1)

左右移动变换为以下递推式：

C(n,k+1)=C(n,k)×(n−k)/(k+1)

由此一来，就可以直接从第1项系数递推求解出第2项系数，以此类推，在O(n)的时间复杂度内计算出最后第n+1项系数。

编程要求
本关的编程任务是补全右侧代码片段Combination_Table和InOrder中Begin至End中间的代码，具体要求如下：

在Combination_Table中，根据杨辉三角的递推性质，计算出第n层的各项系数（第n=0层，各项系数为1），并存入参数C中（C[n][k]=C
n
k
​
）。

在Combination_Only中，根据组合数性质C(n,k+1)=C(n,k)×(n−k)/(k+1)求解(a+b)
n
的二项式展开系数，并存入参数C中（C[k]=C
n
k
​
）。

测试说明
平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。

以下是平台的测试样例：

测试输入：4
预期输出：1 4 6 4 1

输入格式：n
输出格式：C
n
0
​
C
n
1
​
C
n
2
​
..C
n
n
​

开始你的任务吧，祝你成功！

#include <iostream> typedef long long int64; const int maxn = 101; void Combination_Table(int64 C[maxn][maxn], int n) { // 请在这里补充代码，完成本关任务 /********* Begin *********/ // 初始化杨辉三角，所有位置先置0 for (int i = 0; i <= n; ++i) { C[i][0] = 1; // 第0列全为1 C[i][i] = 1; // 对角线全为1 } // 递推计算杨辉三角的每个值 for (int i = 2; i <= n; ++i) { // 从第2行开始（i=2对应n=2） for (int j = 1; j < i; ++j) { // 中间的数，j从1到i-1 C[i][j] = C[i-1][j-1] + C[i-1][j]; } } /********* End *********/ } void Combination_Only(int64 C[maxn], int n) { // 请在这里补充代码，完成本关任务 /********* Begin *********/ C[0] = 1; // 初始化C(n,0)=1 for (int k = 0; k < n; ++k) { // 递推计算C(n,k+1) C[k+1] = C[k] * (n - k) / (k + 1); } /********* End *********/ } int main(int argc, const char * argv[]) { int n; scanf("%d", &n); int64 C1[maxn][maxn]; Combination_Table(C1, n); int64 C2[maxn]; Combination_Only(C2, n); bool flag = true; for (int i=0; i<=n; i++) { if (C1[n][i]!=C2[i]) { flag = false; break; } } if (flag) { printf("%lld", C1[n][0]); for (int i=1; i<=n; i++) { printf(" %lld", C1[n][i]); } printf("\n"); } else{ printf("implement error\n"); } return 0; }