请选择 进入手机版 | 继续访问电脑版

【工程数学——北航青岛研究院版】数学题集(运筹学+组合数学)

[复制链接]
卓小兔 发表于 2020-12-31 19:00:04 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
文章目次



前言



  • √是会的水平,越多越会;
  • ×说明我不会做
一、课程中出现的例题:

1 化规范性√√



  • 注意,岂论是标准型还是规范性,我们目标函数都是要求Min最小值。

2 化标准型√√



3 图解法 线性规划√√



4 图解法 线性规划√√


5 图解法 线性规划√√


6 单纯形法三大定理一定会考据明×√√

看这篇博客:
https://blog.csdn.net/qq_30154571/article/details/111815751
7 整数规划 图解法√√




  • 注意,图解法界整数线性规划,貌似只能去试点。

类似的还有:

8 整数规划 分支定界法√√




9 动态规划 最优化原理 ×



  • 货郎问题、背包问题?这俩在树上老师都没出例题,我先过,我赌他的枪里没有子弹。
10 最优化原理 解 非线性规划×



  • 就下面的非线性规划问题,讨论最优化原明确题思想,并详细求解该题




  • 说实话,我看完这道题之后我都不知道他想说什么。。。
11 排工问题×√(这个老师总结终点的时候没提他)




  • 我就不懂N1和N2是啥?题干上明显也没说啊!
  • 似乎是指,举例子,第一个工件和第二个工件,这是两个详细的工件。




12 平凡圆排列 √√




  • 换句话说,圆排列就是全排列再除以一个你去出来的数
  • 好比:一般的全排列是                                             A                            5                            5                                       A_5^5                  A55​                                   =                         5                         !                              = 5!                  =5!但是你现在是5个人做成圆桌,那么排列个数就是                                             A                            5                            5                                  /                         5                         =                         4                         !                              A_5^5/5 = 4!                  A55​/5=4!。
再举个例子:



  • 首先,看到【没有任何一对夫妇相邻周】,就应该想到容斥原理了。
  • 注意,因为是圆排列,所以最后还要再除以一个10,也就变成了9!
  • 在注意一下,这个                                                   Q                               9                               9                                            Q_9^9                     Q99​是8!;
  • 之所以圆排列之后还要再乘以一个2,是因为第一开始,我们把夫妇看作一个元素,但是夫妇内部也可以交换位置:



  • 但是!!!这个C51、C52这都是怎么来的??
13 有限可重复排列(用我自己的方法)√

https://www.bilibili.com/video/BV1Nb411j7i6?p=2

也就是书上所说的:

例题:




  • 这个P(r,k)貌似就便是A(r,k)吧,对
  • 这道题可以这样明确,咱们先把所有的k个小球线性排列,因为有k1个A1颜色,k2个A2颜色,所以根据有限可重聚集的最根本的结论,一共是有k!/(k1! * k2! * k3! … * kn!) 种大概。
  • 之后再乘上一个                                        C                            (                            r                            ,                            k                            )                                  C(r,k)                     C(r,k) = r! / (r-k)! * k!,之后就把分子上的k!消掉了,就是最终的答案。
  • 因为,我们将k的小球已经做过排序了,所以在将他们放到r个盒子的时候,就不需要对盒子再排序了,我们现在只需要从r个盒子中,选出来k个盒子用来放小球,至于没选上的盒子,将会变成空盒子,不消管,所以是乘上以一个C(r,k)。
14 组合的根本公式 √√




  • 实际上,就是                                              C                            n                            r                                       C_n^r                  Cnr​ 的计算公式。
15 放小球 组合问题 (和13题有点关系)√√




  • 首先,                                   n                         >                         r                              n>r                  n>r,所以第一步是把箱子选出最终能成小球的箱子,这才有了第一步排列。
  • 有点类似于13题的最后部门,需要注意
  • 因为小球都是一样的,所以我们在选箱子的时候,就直接取出和小球一样的箱子数即可,因为要最多一个盒子盛放一个,所以空下的就放一边就好,和13题背面的思路很相近。
16 问题转化——放小球 组合问题 √√√



17 选数字问题 √√√



18 正因子 √√√




  • 注意,素数分解我们先从最小的素数2开始分解,                                        =                            2                            ∗                            2                            ∗                            2                            ∗                            5                            ∗                            5                            ∗                            7                                  =2* 2* 2*5*5*7                     =2∗2∗2∗5∗5∗7(从小往大拆,就只有一种情况。

19 一堆人进车站 插板儿/分点心问题 ×√√

m个人从n个入口进入车站,有多少种进站方式?



  • n个入口,实在就是                                   n                         −                         1                              n-1                  n−1个插板,分成n份就行;
  • 之后我们现在有m个人,                                   n                         −                         1                              n-1                  n−1个插板,一共是                                   m                         +                         n                         −                         1                              m+n-1                  m+n−1个元素,我们举行全排列;
  • 但是插板自己都是相同的,所以我们除掉插板儿个数全排列                                   (                         n                         −                         1                         )                         !                              (n-1)!                  (n−1)!
20 数字整除问题√√




  • 由10000至99999这90000个五位数中, 99999/3-9999/3=30000个。共有30000个能被3整除的数
先求五位数中不含有6且能被3整除的个数:


  • 万位数可以有(1,2,3,4,5,7,8,9)共8个选择(因为没有0嘛),
  • 千位数可以有(0,1,2,3,4,5,7,8,9)共9个选择,
  • 百位数可以有(0,1,2,3,4,5,7,8,9)共9个选择,
  • 十位数可以有(0,1,2,3,4,5,7,8,9)共9个选择,
看余数:


  • 如果万位数+千位数+百位数+十位数的和除以3的余数是0,那么个位数可以有(0,3,9)共3个选择,(因为只有这三个数自己能被3整除嘛)
  • 如果万位数+千位数+百位数+十位数的和除以3的余数是1,那么个位数可以有(2,5,8)共3个选择,
  • 如果万位数+千位数+百位数+十位数的和除以3的余数是2,那么个位数可以有(1,4,7)共3个选择,
  • 所以不管如何,个位数都是有3个选择。
  • 所以五位数中不含有6且能被3整除的个数=8 * 9 * 9 * 9 * 3= 17 496。
所以五位数中至少出现一个6且能被3整除的个数=30000-17496= 12 504

21 数字问题 正因子√√√

400的正因子有多少个?



  • 此题和18题一个类型
22 数字整除问题(和20重了…)√√

含数字6,能被3整除的5位数…
23 分组整除问题 √√



24 容斥原理-最经典 √√



  • 注意计算


错排简介(错排的根本公式使用容斥原理推出来的)

首先说明一下,根据老师pdf上面的推导公式:

  • 首先n个元素直接全排列是n!这个无可厚非,就是最根本的全排列嘛;
  • 接下来我们用容斥原理的思想:现在固定一个元素,除了个元素不动,能产生的排列有多少个——很显然是(n-1)!个(因为有一个元素压根没动,相当于不需要思量它嘛);
  • 以此类推,如果两个元素都不动位置,那么排列数就是(n-2)!个;

25 错排 √√




  • 套用上面的公式——最终排列数 =                                   5                         !                         (                                   1                                       2                               !                                            −                                   1                                       3                               !                                            +                                   1                                       4                               !                                            −                                   1                                       5                               !                                            )                         =                         44                              5!(\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}) = 44                  5!(2!1​−3!1​+4!1​−5!1​)=44
26 错排 (局部错排)√√




  • 分析,这道题和上一道题不一样的地方在于:上一道题明确说了偶数稳定换位置,咱们只动奇数。所以可以简化成为一个n = 5的错排问题。
  • 但是这道题呢!他只说这四个字母不在原来的位置上就行,至于其他的,无所谓,没有要求其他的元素位置如何排列,所以就和上一道题的做法不一样了!

  • 以上实在用到了容斥原理的公式。
  • 注意,涉及到阶乘的部门,都是从                                        8                            !                                  8!                     8!到                                        7                            !                                  7!                     7!往下依次递减的,只有涉及到组合的部门,才是已开始为4;
  • 这是因为我们现在只有四个错排,所以一共有A1A2A3A4四个项,所以C是从                                                    C                               4                               1                                            C_4^1                     C41​ 开始的。
27 错排 √√




  • 这次之所以不适用上一道题机动调解参数的方法,是因为明确说明确只有四个错排,所以可以直接简化为4个元素的错排;
  • 注意,错排问题算出来了之后没不算完,记得再根据字母之间的排列在计算一次。!!!!
28~30 鸽巢原理 √√




  • 注意,全人类的生日一共有366个。



  • 不表明

  • 这个有点饶,我不想表明…
31 鸽巢原理 √√




  • 在这2n个数中取n个,且相互间无倍数关系的唯一取法是n+1,n+2,n+3,…2n
  • 若取第n+1个数时,一定在1至n中取出,而此中每一数都在后n个数中有其倍数,由此得证。
32 鸽巢原理 ×√





  • 首先,题上问的是存在!你只要能找出一个详细的数,那就算证明确,因为只是让证明存在嘛!

  • 构造完前n项和序列之后,去讨论余数ri,首先如果余数 = 0,那简直是存在一个一连                                                   a                               n                                            a_n                     an​,是                                        m                                  m                     m的倍数(好比                                         l                            =                            1                                  l = 1                     l=1);
  • 之后讨论前n项和没有余数 = 0的时候,那么余数一共只有1~m-1共计                                        m                            −                            1                                  m-1                     m−1 种大概,然而                                        S                            1                                  S1                     S1 ~                                         S                            m                                  Sm                     Sm却一共有                                        m                                  m                     m个余数,所以在这一段S的序列中,肯定有两个S它们的余数是相同的,那么这两个数相减肯定就会出现剩下的余数 = 0的情况,则证明完毕。
33 鸽巢原理√√




  • 实在很简朴,因为一个数要么就是偶数就是偶数,就两种选择,所以三个数,肯定有两个数是同奇偶性的,所以最终一定会出现,同奇偶的数相减,那么一定就会出现偶数。
34 鸽巢原理√(是不是和32有点像)




  • 首先一旦看到问题问中间的某一段序列便是多少这种题,肯定要往【构造两个前n项和之后做差】这个方面靠了;

35 不可重复 圆排列√√




  • 也就是:因此, n 个元素的聚集 S,有P(n,r) / r个 r-循环排列
翻转循环排列:



  • 就是再除了一个r的根本上,再除一个2,因为翻转嘛;
36 有重复、圆排列(莫比乌斯见46附加题) √√




  • 说白了就是分四种情况:

  • 我们塞进去的四个元素中,有四个元素相同:1111、2222、3333、4444,共计4种;
  • 有三个元素相同:1112、1113、1114…共计3 * 4 =12种;
  • 以此类推,最终:4+12+12+36+6=70 种


  • 这题就是暴力分情况讨论。
37 母函数 汉诺塔 √




  • 友情提示,木函数地推关系求解(求通项),详细怎么上下消元的方法实在是和地推函数自己高度相关的,要注意。
    汉诺塔问题求解:
  • 设,拥有n个盘子的时候,移动次数为 h(n)
  • 规定 h1 = 1;之后,易知h2 = 3;
  • 现在假设(n-1)个盘子的转移算法已经确定,移动次数为h(n-1),那现在h(n) = ?
  • 由下图可知:递推关系为                                             h                               (                               n                               )                               =                               2                               h                               (                               n                               −                               1                               )                               +                               1                                      h(n) = 2h(n-1) + 1                        h(n)=2h(n−1)+1(因为整体从A-B是一次h(n-1),B-C又是一次,所以是二倍,最后还有一个新加的最大盘需要移动,所以是2X+1)

  • 现在我们可以推出母函数:H(x) = h1x+ h2x2+h3x3+…
  • 之后,由于我们有了递推公式,那么现在我们穷举几个h1234,看看嘛:

    • h1 = 1
    • h2 = 3
    • h3 = 7
    • h4 = 15

  • 递推公式推最终表达式的过程比力复杂:

  • 他是怎么的出来前面一大堆=                                                   x                                           1                                  −                                  x                                                       \frac{x}{1-x}                     1−xx​的?
  • 这个是级数公式:

  • 再增补一个:





  • 所以,我们最终可以解得hn=2hn-1+1 = 2(2hn-2+1)+1 = …最终 = 2n-1。
38 母函数 递推 ×(计算量太大,我以为我会了也算不出来数,gg)

出现偶数个5的n位十进制数的个数?


  • 首先设这个n位数为p1p2p3…pn
  • 除了最高位不能是0以外,剩下的都是10种选择/位,一共是                                   9                         ∗                         1                                   0                            n                                  −                         1                              9 * 10^n-1                  9∗10n−1种选择;
  • 现在先看前n-1位数,如果这个序列已经有偶数个5了,那么pn这一位数上,就有除了5以外的9种选择(显而易见嘛);
  • 但如果前n-1位数只有奇数个5,那么最后一位pn就只能是5(废话…);
  • 现在设,出现偶数个5的个数为an,出现奇数个5的十进制数的个数为bn,现在开始捣腾初始条件:
  • 当n= 1,现在就一位数时,a1 = 8;(除了0和5,共计8种) ;b1 = 1(只能是5嘛);
  • 那么则有递推式:an = 9an-1 + bn-1 因为n-1位都确定了,那么现在就看第n位数呗——无非就是如果是5,那么取法一共就是一种——bn-1种,但是如果最高位不是5呢,是不是就有9种大概了?——                                        9                            ∗                                       a                                           n                                  −                                  1                                                       9*a_{n-1}                     9∗an−1​种;
  • 同理:bn = 9bn-1+an-1,如下图:

  • 设序列{an}的母函数为 A(x),序列{bn}的母函数为 B(x)。 即:



  • 之后,开始化简、上下消元:
  • 诶呦我操我不想写了,有点复杂。。。
39 母函数 整数拆分 √√



40 母函数 整数拆分√√


41 整数拆分√√




  • 所以,一共19种重量,此中,重量为0——1种方案;重量为1——1种方案…
42 整数拆分 √√



43 整数拆分 √√



二、附加题:

44 单纯形法 √




  • 这个我看pdf吧还是…
45 网络分析 ×




  • 这个我先过了,感觉考的大概性不大,究竟例题都险些没有。
46 可重圆排列+莫比乌斯 √





  • 看来,如果给定了详细的数字,我们还可以通过暴力穷举分类来做题,但是如果设计代数式n,就不可制止的要用莫比乌斯反演了…唉
  • 注意,有个概念叫做周期d,个人明确就是你一个圆好比四个空,不是可重复嘛,有大概是1111 1111 1111这么排列组合吧,这样看成个序列,实在周期就是1(有点类似于三角函数谁人周期);
  • 再看,如果我们的序列时1212 1212 1212那么在整个序列看来,就是以2为周期;
  • 同理,1234 1234 1234或者是1122 1122 1122 就很显着就是以4为周期;
  • 但是我排不出d = 3的周期!所以在背面套用默比乌斯函数的公式的时候,没有M(3),就是因为这个原因。
46 增补 可重圆排列+莫比乌斯√

从1,2,3,4中可重复的取4个出来排成一个圆,能做成多少个不同的圆?
首先,我们想到公式如下图:



  • 注意:n是总数,m是你要取得数的个数;
之后,代入详细数字,来求T(n),如图:



  • 首先,为什么没有M(3)的原因,我在上面已经说了,涉及到一个周期d的概念;
加下来,这个详细的M(1)、M(2)、M(4)怎么求呢?看这个公式:

随后,得出三个M:



  • 注意,这个niu(x)怎么求呢?看这个公式:

增补一下这个niu的函数是啥意思:

  • 首先,如果你的d刚开始,才是1,那么你的niu也就 = 1;
  • 之后,如果你的m的次方数,只要存在大于1次方的,你的niu当场 = 0;
  • 最后,如果你的次方数 = 1呢,那就按照k次方一次取正负一;
最后吧M(1)全乡加起来就是最终答案。
三、最后的习题

47 线性规划模子√√



48 线性规划模子√√



49 图解法解线性规划√



50 整数规划√√




  • 注意,图解法界整数线性规划,貌似只能去试点。

51 非线性规划 ×


52 动态规划解决分别问题 ×


53 棋盘路径√√




54 证明 奇数偶数个数相同 √

证明:从 n 个元素中取出奇数个元素和取出偶数个元素取法数相同。



  • 他是构造了一个1+(-1),之后让它举行二项式分解。
  • 增补-什么是二项式分解。

55 证明nn-2棵树√




  • 证明:n个有标点的极点,可以大概成nn-2棵不同的树!!!!!!!!!!!!!!!!!!!

  • 上图证明的表明:这个序列一共有n-2个,所以树是nn-2个(这个序列是以恶个可重复序列,并不是一个标号只能出现一次,所以是nn-2,而不是(n-!))
56 重要——证明-重复组合公式(插板证明,像64题)√




  • 注意啊,是n个不同元素,总数可不是n;(像这种题就可以用插板原理)




  • 注意,6个盒子,所以有7条边,撤除最外面两条边,所以是5条边和r个小球做组合,所以是                                             C                                       n                               +                               r                               −                               1                                      r                                       C_{n+r-1}^r                  Cn+r−1r​个组合数;
增补一个别的:

57 排列生成-字典序√√

字典序法生成排列时, 135798642 是第几个排列,下一个排列是谁?



  • 至于第二个问题:是第几个排列,我再说明一下。
  • 0*8!是因为第一个数1的右边有几个比他还小的,所以是0。
  • 8!是因为第一个数的位置写(n-1)的阶乘,第二个位置就是(n-2)的阶乘,仅此而已。
  • 之后1*7!也是同理。
58 错排的界说和两种解错排的方法




  • 两种方法:容斥原理和指数型母函数
  • 错排界说:就是1、2、3、…                                   n                              n                  n 一共n个元素的全排列中,求每个元素都不在自己原来位置上的大概性有多少种。
  • 详细求解方法:




59 计算欧拉数 ×




60 鸽巢 是m的倍数×√





  • 首先,题上问的是存在!你只要能找出一个详细的数,那就算证明确,因为只是让证明存在嘛!

  • 构造完前n项和序列之后,去讨论余数ri,首先如果余数 = 0,那简直是存在一个一连                                                   a                               n                                            a_n                     an​,是                                        m                                  m                     m的倍数(好比                                         l                            =                            1                                  l = 1                     l=1);
  • 之后讨论前n项和没有余数 = 0的时候,那么余数一共只有1 ~ (m-1)共计                                        m                            −                            1                                  m-1                     m−1 种大概,然而                                        S                            1                                  S1                     S1 ~                                         S                            m                                  Sm                     Sm却一共有                                        m                                  m                     m个余数,所以在这一段S的序列中,肯定有两个S它们的余数是相同的,那么这两个数相减肯定就会出现剩下的余数 = 0的情况,则证明完毕。
61 鸽巢-证明一连若干天举行了21场比赛√√





  • 一般鸽巢原理最终都会使用前n项和作为工具来求解最终问题;
  • 现在知道,ai ~ ai+7≤12;
  • 那一共比了11周,一周最多12场,那么构建一个序列A:S1 ~ S77,这个序列的最大值就是S77——也就是                                   11                         ∗                         12                         =                         132                              11*12 = 132                  11∗12=132场。
  • 再构建一个序列B:S1                                   +                         21                              +21                  +21 ~ S77                                   +                         21                              +21                  +21,这个序列的最大值是S77+21——也就是132+21 = 153;
  • 现在再看这个序列A+B,是不是一共有                                   77                         ∗                         2                         =                         154                              77*2 = 154                  77∗2=154个元素!153和154,现在是不是能感觉到鸽巢原理谁人味儿了~
  • 现在这个序列一共154个元素,然而最大值才是153,A自己和B自己是单调递增的前n项和序列,所以肯定A和B,中间有一个元素是值相同的。
  • 所以这个元素,就是存在的那一连若干天。
62 拉姆斯着色×(实在就是66)





  • 首先,做6个人的完全图;
  • 两个人认识则这条边是红色,不认识就是蓝色;
  • 则必出现同色三角形
63 拉姆斯着色 ×




64 多项式展开之后有多少项 √×√


这个题是——可重组合:



  • 这道题能等效为,我有                                   a                         、                         b                         、                         c                         、                         d                              a、b、c、d                  a、b、c、d四种元素,一共选出来100个,所以就是                                             C                                       4                               +                               100                               −                               1                                      100                                       C_{4+100-1}^{100}                  C4+100−1100​个数。
65 莫比乌斯函数(必考)√



  • 对n举行素因数分解

    闻一知十:

66 鸽巢原理 ×√




  • 可否采取绘图法证明,认识就是红线,1不认识就是蓝线,之后看整个途中有没有同色的三角行就行。
  • 就是考试中不太好利用。

增补概念

67 序数法 ×




  • 对应的序数就是说,按照数字的巨细看起,第一位1不消看;看第二小的数字2,2的右边有1个更小的,所以序数的最左边是1…以此类推
68 迪杰斯特拉算法 √

https://www.bilibili.com/video/BV1oV411R7Yo/?spm_id_from=333.788.recommend_more_video.7

69 最小生成树 √ √

克鲁斯卡尔算法


  • 就是按照权重的巨细,举行加边法,太简朴了,我就不表明了。
普林母算法


  • 最小生成树的核心就是 最小和树;
  • 首先你是个树,不能有环;
  • 而且每个点都给联通,不能有点是孤立的;
  • 而最小,就是最短路径的意思;

https://blog.csdn.net/weixin_41423494/article/details/89920094
70 最大流问题

71 最小匹配

其他ppt泉源的题

72 组合问题求整数解




  • 这个问题实在就是:11个球扔到三个盒子。
  • 他最后不是要求都是正整数解么?那就先把每一个盒子先放一个球,满足正整数再说;
  • 之后8个球随便放,这不就是8个球塞进3个盒子的经典问题么;
  • 所以就是                                             C                                       8                               +                               3                               −                               1                                      8                                       C_{8+3-1}^{8}                  C8+3−18​个正整数解。
73 组合问题求整数解




  • 先往x1里塞两个再说。
74 组合问题求整数解


75 卡特兰数 走棋查问题


76 卡特兰数




  • 这个题和上一题一模一样
  • 卡特兰数
  • 大概性数为:                                             C                                       2                               n                                      n                                  −                                   C                                       2                               n                                                 n                               +                               1                                                 C_{2n}^{n}-C_{2n}^{n+1}                  C2nn​−C2nn+1​

来源:https://blog.csdn.net/qq_30154571/article/details/111941443
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )