实验四：动态规划
实验目的：理解动态规划的基本思想，理解动态规划算法的两个基本要素最优子结构性质和子问题的重叠性质。熟练掌握典型的动态规划问题。掌握动态规划思想分析问题的一般方法，对较简单的问题能正确分析，设计出动态规划算法，并能快速编程实现。
实验内容：编程实现讲过的例题：最长公共子序列问题、矩阵连乘问题、凸多边形最优三角剖分问题、电路布线问题等。本实验中的问题，设计出算法并编程实现。
习题
1． 最长公共子序列
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X=<x1, x2,…, xm>，则另一序列Z=<z1, z2,…, zk>是X的子序列是指存在一个严格递增的下标序列 <i1, i2,…, ik>，使得对于所有j=1,2,…,k有
解答如下：
a) 最长公共子序列的结构
若用穷举搜索法，耗时太长，算法需要指数时间。
易证最长公共子序列问题也有最优子结构性质
设序列X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>的一个最长公共子序列Z=<z1, z2, …, zk>，则：
i 若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列；
ii 若xm≠yn且zk≠xm ，则Z是Xm-1和Y的最长公共子序列；
iii 若xm≠yn且zk≠yn ，则Z是X和Yn-1的最长公共子序列。
其中Xm-1=<x1, x2, …, xm-1>，Yn-1=<y1, y2, …, yn-1>，Zk-1=<z1, z2, …, zk-1>。
最长公共子序列问题具有最优子结构性质。
b) 子问题的递归结构
由最长公共子序列问题的最优子结构性质可知，要找出X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>的最长公共子序列，可按以下方式递归地进行：当xm=yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一个最长公共子序列。当xm≠yn时，必须解两个子问题，即找出Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的一个最长公共子序列。
由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如，在计算X和Y的最长公共子序列时，可能要计算出X和Yn-1及Xm-1和Y的最长公共子序列。而这两个子问题都包含一个公共子问题，即计算Xm-1和Yn-1的最长公共子序列。
我们来建立子问题的最优值的递归关系。用c[i,j]记录序列Xi和Yj的最长公共子序列的长度。其中Xi=<x1, x2, …, xi>，Yj=<y1, y2, …, yj>。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列，故c[i,j]=0。建立递归关系如下：
c) 计算最优值
由于在所考虑的子问题空间中，总共只有θ(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。
计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>作为输入。输出两个数组c[0m ,0n]和b[1m ,1n]。其中c[i,j]存储Xi与Yj的最长公共子序列的长度，b[i,j]记录指示c[i,j]的值是由哪一个子问题的解达到的，这在构造最长公共子序列时要用到。最后，X和Y的最长公共子序列的长度记录于c[m,n]中。
程序如下：
#include<stdioh>
#include<stringh>
int lcs_length(char x[], char y[]);
int main()
{
char x[100],y[100];
int len;
while(1)
{
scanf("%s%s",x,y);
if(x[0]=='0') //约定第一个字符串以‘0’开始表示结束
break;
len=lcs_length(x,y);
printf("%d\n",len);
}
}
int lcs_length(char x[], char y[] )
{
int m,n,i,j,l[100][100];
m=strlen(x);
n=strlen(y);
for(i=0;i<m+1;i++)
l[i][0]=0;
for(j=0;j<n+1;j++)
l[0][j]=0;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
if(x[i-1]==y[j-1]) //i,j从1开始，但字符串是从0开始
l[i][j]=l[i-1][j-1]+1;
else if(l[i][j-1]>l[i-1][j])
l[i][j]=l[i][j-1];
else
l[i][j]=l[i-1][j];
return l[m][n];
}
由于每个数组单元的计算耗费Ο(1)时间，算法lcs_length耗时Ο(mn)。
思考：空间能节约吗？
2． 计算矩阵连乘积
在科学计算中经常要计算矩阵的乘积。矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数。若A是一个p×q的矩阵，B是一个q×r的矩阵，则其乘积C=AB是一个p×r的矩阵。由该公式知计算C=AB总共需要pqr次的数乘。其标准计算公式为：
现在的问题是，给定n个矩阵。其中Ai与Ai+1是可乘的，i=1,2,…,n-1。要求计算出这n个矩阵的连乘积A1A2…An。
递归公式：
程序如下：
#include<stdioh>
int main()
{
int p[101],i,j,k,r,t,n;
int m[101][101]; //为了跟讲解时保持一致数组从1开始
int s[101][101]; //记录从第i到第j个矩阵连乘的断开位置
scanf("%d",&n);
for(i=0;i<=n;i++)
scanf("%d",&p[i]); //读入p[i]的值(注意：p[0]到p[n]共n+1项)
for(i=1;i<=n;i++) //初始化m[i][i]=0
m[i][i]=0;
for(r=1;r<n;r++) //r为i、j相差的值
for(i=1;i<n;i++) //i为行
{
j=i+r; //j为列
m[i][j]=m[i+1][j]+p[i-1]p[i]p[j]; //给m[i][j]赋初值
s[i][j]=i;
for(k=i+1;k<j;k++)
{
t=m[i][k]+m[k+1][j]+p[i-1]p[k]p[j];
if(t<m[i][j])
{
m[i][j]=t; //m[i][j]取最小值
s[i][j]=k;
}
}
}
printf("%d",m[1][n]);
}
3． 凸多边形的最优三角剖分
多边形是平面上一条分段线性的闭曲线。也就是说，多边形是由一系列首尾相接的直线段组成的。组成多边形的各直线段称为该多边形的边。多边形相接两条边的连接点称为多边形的顶点。若多边形的边之间除了连接顶点外没有别的公共点，则称该多边形为简单多边形。一个简单多边形将平面分为3个部分：被包围在多边形内的所有点构成了多边形的内部；多边形本身构成多边形的边界；而平面上其余的点构成了多边形的外部。当一个简单多边形及其内部构成一个闭凸集时，称该简单多边形为凸多边形。也就是说凸多边形边界上或内部的任意两点所连成的直线段上所有的点均在该凸多边形的内部或边界上。
通常，用多边形顶点的逆时针序列来表示一个凸多边形，即P=<v0 ,v1 ,… ,vn-1>表示具有n条边v0v1，v1v2，… ,vn-1vn的一个凸多边形，其中，约定v0=vn 。
若vi与vj是多边形上不相邻的两个顶点，则线段vivj称为多边形的一条弦。弦 将多边形分割成凸的两个子多边形<vi ,vi+1 ,… ,vj>和<vj ,vj+1 ,… ,vi>。多边形的三角剖分是一个将多边形分割成互不重迭的三角形的弦的集合T。如图是一个凸多边形的两个不同的三角剖分。
凸多边形最优三角剖分的问题是：给定一个凸多边形P=<v0 ,v1 ,… ,vn-1>以及定义在由多边形的边和弦组成的三角形上的权函数ω。要求确定该凸多边形的一个三角剖分，使得该三角剖分对应的权即剖分中诸三角形上的权之和为最小。
可以定义三角形上各种各样的权函数W。例如：定义ω(△vivjvk)=|vivj|+|vivk|+|vkvj|，其中，|vivj|是点vi到vj的欧氏距离。相应于此权函数的最优三角剖分即为最小弦长三角剖分。(注意：解决此问题的算法必须适用于任意的权函数)
4． 防卫导d
一种新型的防卫导d可截击多个攻击导d。它可以向前飞行，也可以用很快的速度向下飞行，可以毫无损伤地截击进攻导d，但不可以向后或向上飞行。但有一个缺点，尽管它发射时可以达到任意高度，但它只能截击比它上次截击导d时所处高度低或者高度相同的导d。现对这种新型防卫导d进行测试，在每一次测试中，发射一系列的测试导d（这些导d发射的间隔时间固定，飞行速度相同），该防卫导d所能获得的信息包括各进攻导d的高度，以及它们发射次序。现要求编一程序，求在每次测试中，该防卫导d最多能截击的进攻导d数量，一个导d能被截击应满足下列两个条件之一：
a)它是该次测试中第一个被防卫导d截击的导d；
b)它是在上一次被截击导d的发射后发射，且高度不大于上一次被截击导d的高度的导d。
输入数据：第一行是一个整数n，以后的n各有一个整数表示导d的高度。
输出数据：截击导d的最大数目。
分析：定义l[i]为选择截击第i个导d，从这个导d开始最多能截击的导d数目。
由于选择了第i枚导d，所以下一个要截击的导dj的高度要小于等于它的高度，所以l[i]应该等于从i＋1到n的每一个j，满足h[j]<=h[i]的j中l[j]的最大值。
程序如下：
#include<stdioh>
int main()
{
int i,j,n,max,h[100],l[100];
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&h[i]);
l[n-1]=1;
for(i=n-2;i>=0;i--)
{
max=0;
for(j=i+1;j<n;j++)
if(h[i]>h[j]&&max<l[j])
max=l[j];
l[i]=max+1;
}
printf("%d",l[0]);
}
5． 石子合并
在一个圆形 *** 场的四周摆放着n堆石子(n<= 100)，现要将石子有次序地合并成一堆。规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序，由文件读入堆栈数n及每堆栈的石子数(<=20)。
选择一种合并石子的方案,使得做n－1次合并,得分的总和最小；
输入数据：
第一行为石子堆数n；
第二行为每堆的石子数,每两个数之间用一个空格分隔。
输出数据：
从第一至第n行为得分最小的合并方案。第n+1行是空行从第n+2行到第2n+1行是得分最大合并方案。每种合并方案用n行表示，其中第i行(1<=i<=n)表示第i次合并前各堆的石子数(依顺时针次序输出，哪一堆先输出均可)。要求将待合并的两堆石子数以相应的负数表示。
Sample Input
4
4 5 9 4
Sample Output
－4 5 9 －4
－8 －5 9
－13 －9
22 4 －5 －9 4
4 －14 －4
－4 －18
22
6． 最小代价子母树
设有一排数，共n个，例如：22 14 7 13 26 15 11。任意2个相邻的数可以进行归并，归并的代价为该两个数的和,经过不断的归并，最后归为一堆，而全部归并代价的和称为总代价，给出一种归并算法，使总代价为最小。
输入、输出数据格式与“石子合并”相同。
Sample Input
4
12 5 16 4
Sample Output
－12 －5 16 4
17 －16 －4
－17 －20
37
7． 商店购物
某商店中每种商品都有一个价格。例如，一朵花的价格是2 ICU(ICU 是信息学竞赛的货币的单位）；一个花瓶的价格是5 ICU。为了吸引更多的顾客，商店提供了特殊优惠价。特殊优惠商品是把一种或几种商品分成一组。并降价销售。例如：3朵花的价格不是6而是5 ICU；2个花瓶加1朵花是10 ICU不是12 ICU。
编一个程序，计算某个顾客所购商品应付的费用。要充分利用优惠价以使顾客付款最小。请注意，你不能变更顾客所购商品的种类及数量，即使增加某些商品会使付款总数减小也不允许你作出任何变更。假定各种商品价格用优惠价如上所述，并且某顾客购买物品为：3朵花和2个花瓶。那么顾客应付款为14 ICU因为：
1朵花加2个花瓶优惠价：10 ICU
2朵花正常价：4 ICU
输入数据：第一个文件INPUT．TXT描述顾客所购物品（放在购物筐中）;第二个文件描述商店提供的优惠商品及价格（文件名为OFF ER．TXT）。 两个文件中都只用整数。
第一个文件INPUT．TXT的格式为:第一行是一个数字B（0≤B≤5），表示所购商品种类数。下面共B行，每行中含3个数C，K，P。 C 代表商品的编码（每种商品有一个唯一的编码），1≤C≤999。K代表该种商品购买总数，1≤K≤5。P 是该种商品的正常单价（每件商品的价格），1≤P≤999。请注意，购物筐中最多可放55＝25件商品。
第二个文件OFFER．TXT的格式为:第一行是一个数字S（0≤S≤9 9），表示共有S 种优惠。下面共S行，每一行描述一种优惠商品的组合中商品的种类。下面接着是几个数字对（C，K），其中C代表商品编码，1≤C≤9 99。K代表该种商品在此组合中的数量，1≤K≤5。本行最后一个数字P（1≤ P≤9999）代表此商品组合的优惠价。当然， 优惠价要低于该组合中商品正常价之总和。
输出数据：在输出文件OUTPUT．TXT中写 一个数字（占一行），该数字表示顾客所购商品（输入文件指明所购商品）应付的最低货款。
8． 旅游预算
一个旅行社需要估算乘汽车从某城市到另一城市的最小费用，沿路有若干加油站，每个加油站收费不一定相同。旅游预算有如下规则：
若油箱的油过半，不停车加油，除非油箱中的油不可支持到下一站；每次加油时都加满；在一个加油站加油时，司机要花费2元买东西吃；司机不必为其他意外情况而准备额外的油；汽车开出时在起点加满油箱；计算精确到分（1元=100分）。编写程序估计实际行驶在某路线所需的最小费用。
输入数据：从当前目录下的文本文件“routedat”读入数据。按以下格式输入若干旅行路线的情况：
第一行为起点到终点的距离（实数）
第二行为三个实数，后跟一个整数，每两个数据间用一个空格隔开。其中第一个数为汽车油箱的容量（升），第二个数是每升汽油行驶的公里数，第三个数是在起点加满油箱的费用，第四个数是加油站的数量。（〈=50）。接下去的每行包括两个实数，每个数据之间用一个空格分隔，其中第一个数是该加油站离起点的距离，第二个数是该加油站每升汽油的价格（元/升）。加油站按它们与起点的距离升序排列。所有的输入都有一定有解。
输出数据：答案输出到当前目录下的文本文件“routeout”中。该文件包括两行。第一行为一个实数和一个整数，实数为旅行的最小费用，以元为单位，精确到分，整数表示途中加油的站的N。第二行是N个整数，表示N个加油的站的编号，按升序排列。数据间用一个空格分隔，此外没有多余的空格。
Sample Input
5163 3809 1
157 221 2087 3 2
1254 1259
2979 1129
3452 0999
Sample Output
3809 1
2
9． 皇宫看守
太平王世子事件后，陆小凤成了皇上特聘的御前一品侍卫。皇宫以午门为起点，直到后宫嫔妃们的寝宫，呈一棵树的形状；某些宫殿间可以互相望见。大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。可是陆小凤手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。
请你编程计算帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。
输入数据：输入数据由文件名为intputtxt的文本文件提供。输入文件中数据表示一棵树，描述如下：
第1行 n，表示树中结点的数目。
第2行至第n+1行，每行描述每个宫殿结点信息，依次为：该宫殿结点标号i（0<i<=n），在该宫殿安置侍卫所需的经费k，该边的儿子数m，接下来m个数，分别是这个节点的m个儿子的标号r1，r2，，rm。
对于一个n（0 < n <= 1500）个结点的树，结点标号在1到n之间，且标号不重复。
输出数据：输出到outputtxt文件中。输出文件仅包含一个数，为所求的最少的经费。
如右图的输入数据示例：
Sample Input
6
1 30 3 2 3 4
2 16 2 5 6
3 5 0
4 4 0
5 11 0
6 5 0
Sample Output
25
10． 游戏室问题
有一个游戏室里有多个游戏室，并且这每个游戏室里还有多个游戏室，每个游戏室里面还有游戏室，依此类推。进入每个游戏室都可得到一定的快乐，每个游戏室的门票价格都大于等于0，都有一个快乐值，并且只有进入了一个游戏室，才可以进入它内部的游戏室，小明现在有n元钱，问最大能得到多少的快乐。
11． 基因问题
已知两个基因序列如s：AGTAGT；t：ATTAG。现要你给序列中增加一些空格后，首先使得两个序列的长度相等，其次两个串对应符号匹配得到的值最大。基因只有四种分别用A、G、C、T表示，匹配中不允许两个空格相对应，任意两符号的匹配值由下表给出：
A G C T 〕
A 5 -2 -1 -2 -4
G -2 5 -4 -3 -2
C -1 -4 5 -5 -1
T -2 -3 -5 5 -2
〕 -4 -2 -1 -2
提示：定义问题l[i][j]为取第一个序列的前i项，和第二个序列的前j项，这两个序列加空格匹配的最大值。它的最优值与三个子问题有关，l[i-1][j-1]、l[i][j-1]、l[i-1][j]。
建立递归公式如下：
其中m[0][t[j]表示表中空格和t[j]匹配的对应值。
思考：本问题的初始化。
12． 田忌赛马
田忌与齐王赛马，双方各有n匹马参赛（n<=100），每场比赛赌注为1两黄金，现已知齐王与田忌的每匹马的速度，并且齐王肯定是按马的速度从快到慢出场，现要你写一个程序帮助田忌计算他最好的结果是赢多少两黄金（输用负数表示）。
分析：先排序，齐王的马的速度放在数组a中，田忌的马的速度放在数组b中。本问题应用的算法是动态规划和贪心算法相结合解决的。从两人的最弱的马入手：
若田忌的马快，就让这两匹马比赛；
若田忌的马慢，干脆就让他对付齐王最快的马；
若两匹马的速度相等，这时有两种选择方案，或者它俩比赛，或者对付齐王最快的马。
定义子问题：l(i，j)为齐王的从第i匹马开始的j匹马与田忌的最快的j匹马比赛，田忌所获得的最大收益。
则：
程序具体实现时，为了适合c数据从0开始，稍加变动，定义子问题：l(i，j)为齐王的从第i匹马开始到第i＋j匹马共j+1匹马与田忌的最快的j+1匹马比赛，田忌所获得的最大收益。初始化时：l[i][0]表示齐王的第i匹马与田忌最快的马比赛的结果。
程序如下：
#include<stdioh>
void readdata();
void init();
int n,a[100],b[100],l[100][100];
int main()
{
int i,j;
readdata();
init();
for(i=n-2;i>=0;i--)
for(j=1;j<n-i;j++)
if(a[i+j]<b[j])
l[i][j]=l[i][j-1]+1;
else if(a[i+j]>b[j])
l[i][j]=l[i+1][j-1]-1;
else if(l[i+1][j-1]-1>l[i][j-1])
l[i][j]=l[i+1][j-1]-1;
else
l[i][j]=l[i][j-1];
printf("%d",l[0][n-1]);
}
void readdata()
{
int i;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n;i++)
scanf("%d",&b[i]);
}
void init()
{
int i;
// qsort(a,n); //略
for(i=0;i<n;i++)
{
if(a[i]<b[0])
l[i][0]=1;
else if(a[i]==b[0])
l[i][0]=0;
else
l[i][0]=-1;
}
}如M1={{1,2},{2,1}};
M2={{2,3},{4,5}}
矩阵点积，直接用“”就可以了
M1M2
返回{{10, 13}, {8, 11}}
天津大学能源动力考研经验分享
说明一下本人的考研情况：
做出考研这个决定后，你会面对很多的问题：专业的选择（专业的难易程度、喜好程度、就业前景等等）、院校的选择（是否是985/211院校、是否跨校跨地区等等）、考研时间安排诸如此类的问题。针对这些问题，每个人的情况都是不一样的，需要我们自己小心谨慎的选择，我的建议就是向考上你意向学校的学长学姐或者专业课老师咨询，他们往往都可以给出合理的建议，然后再结合自己的实际情况选择。再者就是资料搜集这一块，大家可以到考研文库里面看看，很多学长学姐的血泪经验，非常具有参考价值！
初试经验：
考试科目：
1思想政治理论
2英语二或203日语
3301数学一
4801力学综合或803机械原理与机械设计或806测控技术基础或812自动控制理论或829热力学或863高分子化学与物理或901数据结构与程序设计
专业课参考书目（901数据结构与程序设计）：
数据结构：
1、 《数据结构》C 语言版，严为敏 吴伟民编，清华大学出版社，2009
2、 《数据结构》 (用面向对象方法与 C++描述)，殷人昆等，清华大学出版社，2007
程序设计：
1、 《C++程序设计》，Y Daniel Liang 著，王刚 刘晓光 刘璟译，机械工业出版社
2、 《C++编程思想(两卷合订本) 》埃克尔(Bruce Eckel)、Chuck Allison、刘宗田、 袁兆山
机械工业出版社
3、 《C++程序设计语言(特别版 o 十周年中文纪念版)》
斯特朗斯特鲁普(Bjarne Stroustrup)、
裘宗燕 机械工业出版社
复试科目：
传热学与燃烧学
历年复试分数线（年份/政治/英语/专业课1/专业课2/总分）：
2021/50/50/75/80/320
2020/50/50/75/80/315
2019/50/50/80/80/310
往年招生情况：
天津大学2021年机械工程学院统招全日制411人（含推免生198人）；
天津大学2020年机械工程学院统招全日制 404 人（含推免生 210 人）；
天津大学2019年机械工程学院统招全日制 374 人（含推免生 180 人）。
复习经验：
学复习我基本全程跟着宇哥的复习课进行复习，比较省心，教材也是配套买的，后期补充了各种考前模拟题和冲刺题，补充知识点和做题方法。不过每个老师都各有特点，有的老师也跟什么汤家凤，于炳森，李永乐之类的。不过劝大家一定不要相信小众的牛鬼蛇神，比较坑人！
1)参考书目：
张宇高等数学三十讲、
十八讲、张宇概率论九讲、张宇真题、
各种考前模拟题、冲刺题。
2）备考过程：
3-6月：第一遍基础。基础阶段就是《张宇基础30讲》，
跟着视频过然后笔记本上做笔记（一般是一些总结性的知识点），这个工作建议前期做好！搭好框架最重要。这个时候除了完成课后习题还可以配套做张宇的《1000 题》。（这个习题基础阶段可以开始做a,b组）
6-9月：第二遍强化。强化阶段用张宇的18+9+9讲，也是跟着视频过了一遍，其实建议强化部分重点看或者提早开始，因为基础班的知识真是少了很多！除非你在本科阶段并没有怎么好好学数学，可以从基础班打好基础。这个阶段张宇的《1000题》
a、b组没做完的继续做完，c组题可以适当做起来，工作量其实还是很大的，我也会看一些重点章节的习题讲解视频。这时候数学得要加大强度，我一般安排了整个早上8：30到12点，建议匹配好考研的时间，中午留足够时间休息。（我用的是老版本的分了abc组的1000题）
注：强化阶段得做好错题总结并且定时复习；习题一定要动手算切忌眼高手低；草稿纸养成规划使用的习惯，因为考试是一张一张地拿；不懂的习题要当天就解决不然之后会遗忘；张宇1000题C组有些题十分靠技巧，可以适当放掉。
9-11月：第三遍真题与模拟。这个阶段首要任务就是用真题进行模拟。目的是串联前后知识点以及模拟考场做题的感觉。我一开始是用05年-09年的真题（这几年真题的题目结构还是老版的）进行知识点串联，不卡时间做，熟悉真题的解题感觉，错题还是继续总结起来。之后做 10年-20年的真题，这时候得卡时间做，25h左右完成一份，然后一定要检查检查检查！自己准备好草稿纸和答题纸，用早上的时间模拟数学考试，真题数量有限所以得好好用起来！！做完后自己计算好分数，做好错题总结和试卷总结。21年改了题型，这一年重点拿来模拟，保证熟悉整个做题的时间分配。时间充裕的话可以做第二轮真题（我时间不太够了所以第二轮基本上是过的错题，没有做整套）
11 月到考前：模拟题和冲刺题以及知识巩固。因为改了题型和分值，所以做模拟题变得重要了，基于真题已经通透的基础上就可以着手做模拟题。模拟题可以选做李林、张宇8套、合工大、李永乐等等，我当时基本都有做了，觉得李林出得比较像真题，李永乐比较重计算，张宇和合工大的就偏难一点，但思路都值得借鉴。选做1-2种模拟题和冲刺题即可。另外还有一件重要的事就是进行知识框架的巩固，这时候就用到基础阶段的 那些总结性的笔记，当然在复习过程中是不断完善的。另外若还有时间可以再看看错题，差不多就可以去考试了。考试那天一定要放轻松啊！！！把该拿的分拿到就是胜利~我当时就和一个大题较上劲了，不但没做出来而且没有时间检查，白白丢掉了简单题的分。
英语二：
英语二比英语一要简单，不管你是考英语一还是英语二，都是要背单词的，这是第一步，用的是百词斩软件，此外还广泛地阅读外文作品，读外文作品主要是提高了自己阅读的速度，要复习阅读理解部分，我还用了《阅读理解150篇》
也听了唐迟的讲解视频，视频很赞，我已经替你们体验了一下，还有就是真题，真题我起码做了两遍，真题很宝贵，大家要完全利用起来，《张剑历年英语二真题解析》等资料也很差不错。最后我觉得作文有必要分析一下，作文里面有几个好的句子自己写得独一无二的好句子，那会是作文的亮点，三段式的作文，批改时间短，卷面整洁也很重要，还有就是大家平时练过的作文也可以放到网上去帮你修改的，互联网的资源需要充分利用。
数学一：
数学的复习二李（李永乐和李正元）的复习全书，再就是习题集，有一本习题集就够了，
《660题》必备，《接力题典1800》补充，习题集之间会有很多重合所以没必要本本都买来去做，跟高考数学一样，考研数学也有基础分，考研数学满分150基础分也有7/80%，120分的基础，你不要计算失误，不要出现基本错误，把课本上复习全书上面讲义上的定义、定理搞明白这是最最最基本的，视频可以把汤家凤和张宇的结合起来，
强强联手，两个老师都会教你一些计算技巧和方法，可以好好学一学，最后9月底到12月一直都在刷题，《张宇八套卷》、《绝对考场8套卷》，这些试卷穿插做更好些，有些试卷简单有些试卷难，自己心态不要崩溃就好。最后数学有些吃力不讨好的部分我属于半放弃的状态，不强求这个分数的得失。
政治：
政治为什么放在数学和英语后面说呢因为政治完全没必要花英语和数学那么长时间，我复习政治的时间就是我娱乐消遣的时间，穿插在英语和数学的复习过程中，我所有的政治资料包括了精讲精练、1000题、徐涛视频、肖秀荣四套卷还有石磊的预测。精讲精练用于刷完1000的溯源，就是增强一下自己的记忆，视频我没有选择肖秀荣的是因为肖秀荣不怎么讲课了，都是其他人讲课，没什么生动乐趣可言，所以我最后看了徐涛的强化课程，最后背了肖秀荣4套卷，学校书店早早就出了肖四套卷的盗版，跟正版没错误区别，毕竟还是跟正版的对比了一下。
专业课：
首先学习专业课要早，不能与本专业的同学相比，没有基础或者基础差就应该早点开始学习，901的基础就是数据结构和C++程序设计
3-5月份 大约从三月份开始跟着b站的视频笼统的学知识点，不论考不考都要学，因为这是你计算机专业素养的建立，把地基打好才能产生更好的编程算法体系
6-8月份 开始过王道或者天勤的数据结构，一边过考研常考知识点，同步做课后习题这段时间C++也不能落下，建议每天做几道oj题（从最简单的入手即可）我开始用的是hdoj（杭州电子科技大学oj，可以去百度然后注册个账号进行答题，讨论里面有各种大神的解答 ，多看看别人写的代码）
9-11月份 开始跟着901的考研辅导资料进行专门考点学习（我买的是500块钱的资料，感觉很贵但是质量没得说，归纳得非常好，我现在研究生同学好像都是用的这个，所以我保存了电子版）
首先花一个多月的时间把这个辅导资料上的笔记过完，其中有很多算法题，程序设计题可能会很难上手，不过慢慢来总会理解的
然后再把辅导资料的习题完成，这上面的习题的题型跟最后考试的题型是差不多的，把习题上的知识点，题目弄懂了 问题不大
再就是到10月下旬开始做上面的真题（现在更新到2020年的了，也就是我们这一年的）自己在做真题的时候一定要学会总结，看看出题的规律和形势
到11月中下旬开始做预测题，总共有八套预测题，可以先做六七套，留个一两套到考试前模拟做最重要的就是要学会总结，901会考数据结构的算法题和C++的程序设计题 平时一定要学会自己做题，不要太依赖答案，锻炼自己的算法思想，做题方法！
真题回忆：
数据结构应用题，大概记得如下：
1、 给出一段堆排序 *** 作的代码，让你证明把完全二叉树调整为一个二叉堆为什么时间复杂度为O(n)。（参考书出现过，以前也有这个类似的题目）
2、 哈夫曼树的构造，要求写出详细构造过程，并计算节省了多少位编码。（求散列的编码和正常差多少，参考书上面出现过）。
3、 给出一个中缀表达式，要求用栈转化成后缀表达式，（参考书原题）
4、 一棵近似满二叉树若第6层(第一层高度算1)有8个叶子节点，问该树最多含有多少个节点
5、 给出parent[e]的意义:若e点为所在树的根，那么parent[e]就是该树的节点总数的相反数。若e点不是所在树的根节点，则paren[e]为e点所在树的根结点。（参考书上练习过的题目，主要就是考察并查集了。考试之前叶神有提起过几次，所以印象比较深）
6、 AVL树，如果v节点是分支节点，若把v删除以后新形成了一棵AVL树B,问若把V点再加入B中，是否会变成A。若会请证明，不会请举反例。（参考书和最后六套卷练习几次），还有一个就是将无相连通图变成最小生成树，无向图的最小边一定在生成树中。（两个都是否，也是常规题）
算法题：
1、砍木桩（拿到卷子的时候笑了一天，感觉天大的命题老师还是有点萌），喜欢从短的到长的砍，木桩按照重量从小到大排序，每次排序时只能对相邻的木桩进行交换，求最少交换次数。（冒泡排序改进问题吧，参考书本说过）
2、有n个股票经纪，彼此之间有的可以互相通信，有的无法通信，其中任何两个人通信所需的时间不同。求选取哪一个经纪人可以保证其与其余任意一个经纪人通信耗时最短。（单源路径最短问题，个人感觉可以用prim，克鲁斯卡尔，弗洛伊德算法）
3、在X轴上水平放置着 N 个条形图，这 N 个条形图就组成了一个柱状图，每个条形图都是一个矩形，每个矩形都有相同的宽度，均为1单位长度，但是它们的高度并不相同。计算柱状图中以X轴为底边的最大矩形的面积（王晓东老师课本原原本本的题目，一字不改。考前群里有说过这个，应该是矩阵连乘问题）
总的来说，今年天大计算机专业课难度不高，大家考完都还是比较激动，我们那个考场有几个提前半个小时就交卷了。这个倒是出乎以前对天大专业课的认识。
关于复试准备
2021年复试情况依然采取网络复试，只要你的分数线能通过学校的院线，按照1:12的原则，你就可以进入到复试阶段，所以，当你知道自己的分数之后，你要做的就是结合北工大前两年的复试人数及录取分数线，进行准备，假如你能进入复试，那就请看下面我说的。
你要好好准备自己的简历，把自己在学校期间获得的荣誉，尽量能写得都写上，然后就是英语六级很重要，因为，老师会高看你一眼最起码选你的几率比较答，以后看文献，英语的重要性可想而知了吧。
复试就是专业课和英语，在复试的时候，等老师回复你邮件时，你就去找天大上届的学长学姐购买面试复习题，如果找不到，就去网上买。
在英语方面就是翻译一段文献，如果有生词的话，就先跳过，如果老师问你意思，你就委婉地说不会，下去学，不能跟老师顶嘴，老师就算说你也不会说的太过分。这个就放心吧。
最后寄语
考研选择非常重要，切勿好高骛远。最后我希望各位学弟学妹们既然做好了选择，就向前方勇敢地去乘风破浪，柳暗花明一直在前方，祝大家一战成硕！
#include <stdafxh>
void Matrix_ABC(double a,double b, double c,double result,int m, int n, int p, int q);
void main()
{
int m=3,n=2,p=2,q=4;
double a[]={1,0,1,0,1,0};
double b[]={2,3,2,3};
double c[]={3,1,3,1,0,0,0,0};
double result;
result=new double[mq];
int i,j;
printf("A\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
printf("%f\t",a[in+j]);
printf("\n");
}
printf("B\n");
for(i=0;i<n;i++)
{
for(j=0;j<p;j++)
printf("%f\t",b[ip+j]);
printf("\n");
}
printf("C\n");
for(i=0;i<p;i++)
{
for(j=0;j<q;j++)
printf("%f\t",c[iq+j]);
printf("\n");
}
printf("\n");
Matrix_ABC(a,b,c,result,m,n,p,q);
printf("ABC\n");
for(i=0;i<m;i++)
{
for(j=0;j<q;j++)
printf("%f\t",result[iq+j]);
printf("\n");
}
delete [] result;
}
void Matrix_ABC(double a,double b, double c,double result,int m, int n, int p, int q)
{
int i,j,k;
double temp;
temp=new double[mp];
for(i=0;i<m;i++)
for(j=0;j<p;j++)
{
temp[ip+j]=0;
for(k=0;k<n;k++)
temp[ip+j]+=a[in+k]b[nk+j];
}
for(i=0;i<m;i++)
for(j=0;j<q;j++)
{
result[iq+j]=0;
for(k=0;k<p;k++)
result[iq+j]+=temp[ip+k]c[qk+j];
}
delete [] temp;
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）