本周学习了数学专题

今天整理剩下的

特殊计数

Catalan 数是一种序列，增长速度快，但其中有组合计数。
实际问题：
1.hdu2067小兔棋盘

hdu2067

就沿对角线的那一串数字

该题直接计算数很大，找到规律用递推把下三角的数都计算下来

#include <iostream> #include <cstring> using namespace std;long long dp[40][40];int main() {int n;int t=1;for(int i=1;i<=36;i++)dp[i][0]=1;for(int i=1;i<36;i++){for(int j=1;j<36;j++){if(i==j) dp[i][j]=dp[i][j-1];elsedp[i][j]=dp[i-1][j]+dp[i][j-1];}}while(cin>>n&&n!=-1){cout<<t++<<" "<<n<<" ";cout<<2*dp[n][n]<<endl;}return 0; }

2.括号问题:
用n个左括号和n个右括号组成的一串字符串有多少种合法组合?定义左括号为0，右括号为1。问题转化为n个0和n个1组成的序列，在任意前k个序列中0的数量都大于1的数量。

n对括号排列，左括号看做是在棋盘沿着 x 方向走， 右括号看做是在棋盘沿着 y 方向走.
前面的任意k个括号，左括号的数 >= 右括号的数。相当于在棋盘走，没有超过 y = x 这条线。这也就是卡特兰数的定义。
3.出栈序列问题:
给定一个字符串形式表示的入栈顺序，求出一共多少种可能的出栈顺序？比如1,2,3进栈，则出栈顺序一共5种，即123，132，213，231，321。

hdu5184

4.二叉树问题：
hdu1130、hdu3240
题目大意：
n个结点所能构成的多少种不同的搜索二叉树。（竟然是卡特兰数）

卡特兰数：(令F(0)=1,F(1)=1)

① 递推式：F(n)= F(0)*F(n-1)+F(1)F(n-2) + … + F(n-1)F(0) (n>=2)
通项式：F(n)=C(2n,n) / (n+1) (n=0,1,2,…)
② 递推式：F(n)=F(n-1)(4n-2)/(n+1);
通项式：F(n)=C(2n,n)-C(2n,n-1) (n=0,1,2,…）

package ac;import java.math.BigInteger; import java.util.Scanner;public class l1 {public static void main(String[] args) {BigInteger[] c=new BigInteger[1000+1];c[1]=BigInteger.ONE;for(int i=2;i<=1000;i++){c[i]=c[i-1].multiply(BigInteger.valueOf(4*i-2)).divide(BigInteger.valueOf(i+1));}Scanner cin=new Scanner(System.in);while(cin.hasNextInt())System.out.println(c[cin.nextInt()]);}}

（Java处理）

#include <iostream> #include <string> #include <cstring> using namespace std;const int b=10000; const int N=100+2; int k[N][N];int main() {k[1][1]=1;k[2][1]=2;k[3][1]=5;for(int i=4;i<=100;i++){for(int j=1;j<100;j++)//大数乘法{k[i][j]+=k[i-1][j]*(4*i-2);k[i][j+1]+=k[i][j]/b;//进位k[i][j]%=b;}int t;for(int j=100;j>0;j--)//大数除法{t=k[i][j]%(i+1);k[i][j-1]+=t*b;k[i][j]/=(i+1);}}int n;while(cin>>n){int i=100;while(k[n][i]==0)i--;cout<<k[n][i--];while(i>0)cout<<k[n][i--];cout<<endl;}return 0; }

（卡特兰数，高精度大数）

5.编程计算Catalan数：
(令F(0)=1,F(1)=1)
(1).F(n)= F(0)*F(n-1)+F(1)F(n-2) + … + F(n-1)F(0) (n>=2)
(2).F(n)=F(n-1)(4n-2)/(n+1);
(3)F(n)=C(2n,n) / (n+1) (n=0,1,2,…)
从（2）可以知道，当n很大的时候，Fn/Fn-1约等于4.所以卡特兰数是以约4ⁿ递增的，增长极快。

这三个公式应用场合不同，（1）适用于：当n比较小时，100以内的卡特兰数时。不过这时数也很大，但（2）比（1）更容易溢出。此时用（1）比较好。对于更大的卡特兰数，需要进行精度计算。
（2）（3）适用于：n非常大的时候，需要取模运算。不过，（2）（3）都有大除法，对大数做除法会损失精度，所以需要逆元，然后再取模。（3）算阶乘同时也要对阶乘取模，在公式计算。

Stirling数

第一类Stirling数s(n,k)：
把n个不同的元素分配到k个圆排列里，圆不能空。问有多少种分法。

数学期望

具有线性性质。由于线性性质和Dp状态转移思想相似。所以常用Dp来实现。

巴什游戏与P-position,N-position

1.巴什游戏（Bash Game）
2.P-position,N-position与动态规划

尼姆游戏

图游戏与Sprague-Grundy函数

1.图游戏
2.Sprague-Grundy函数
3.用Sprague-Grundy函数求巴什游戏
4.用Sprague-Grundy函数求尼姆游戏

总结

以上是生活随笔为你收集整理的2021-10-02的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。