总结数位DP算法

第一篇：总结数位DP算法

数位dp是一种计数用的dp，一般就是要统计一个区间[le,ri]内满足一些条件数的个数。比如，[1,10000] 中统计不含有4的数。

所谓数位dp，字面意思就是在数位上进行dp咯。就是对数字每一位每一位递推

此类题目最基本的暴力方法：

1.for(int i=le;i<=ri;i++)

2.if(Check(i))ans++;

而数位DP就是从最低(高)位起，一位一位的放数字，然后记忆化一下，累加一下

有两种方法，一是递推，二是记忆化搜索

一，记忆化搜索：

思路来自： 数位dp总结之从入门到模板 假设题目要求是不含有62的数

状态定义：d[pos][pre] 表示当前枚举到pos位置，且pos+1位的数字是pre，此时满足题意的数字的个数(也即是pre==6时，pos该位置不能放2)还要个数组a[i]保存第i位的数字，如213，a[0]=3，注意是从右往左数

有个问题是枚举第pos位数时，此位置放数字的范围要判断一下，比如题目给出在[1,894] 枚举的时候要判断是否在894以内

比如，213，第一位放了2，那么第二位就只能放0~1，所以模板中用了个limit判断pos前的几位数字是否与n一样，true的话只能枚举0~a[pos]，false就是0~9，不然比题目要求的213大了

还有个问题是前导0的问题，假如枚举5位数，你放的时候前2位都是00，那数字不变成3位了嘛，所以需要个lead保存前几位是否都是0，当然这是看题意的，有时候题目不要求，可以直接省去

好了，看模板：

1.typedef long long ll;2.int a[20];

3.ll dp[20][state];//不同题目状态不同

4.ll dfs(int pos,/*state变量*/,bool lead/*前导零*/,bool limit/*数位上界变量*/)//不是每个题都要判断前导零

5.{

6.//递归边界，既然是按位枚举，最低位是0，那么pos==-1说明这个数我枚举完了

7.if(pos==-1)return 1;/*这里一般返回1，表示你枚举的这个数是合法的，那么这里就需要你在枚举时必须每一位都要满足题目条件，也就是说当前枚举到pos位，一定要保证前面已经枚举的数位是合法的。不过具体题目不同或者写法不同的话不一定要返回1 */ 8.//第二个就是记忆化(在此前可能不同题目还能有一些剪枝)

9.if(!limit &&!lead && dp[pos][state]!=-1)return dp[pos][state];10./*常规写法都是在没有限制的条件记忆化，这里与下面记录状态是对应，具体为什么是有条件的记忆化后面会讲*/

11.int up=limit?a[pos]:9;//根据limit判断枚举的上界up;这个的例子前面用213讲过了

12.ll ans=0;13.//开始计数

14.for(int i=0;i<=up;i++)//枚举，然后把不同情况的个数加到ans就可以了

15.{

16.if()...17.else if()...18.ans+=dfs(pos-1,/*状态转移*/,lead && i==0,limit && i==a[pos])//最后两个变量传参都是这样写的

19./*这里还算比较灵活，不过做几个题就觉得这里也是套路了

20.大概就是说，我当前数位枚举的数是i，然后根据题目的约束条件分类讨论

21.去计算不同情况下的个数，还有要根据state变量来保证i的合法性，比如题目

22.要求数位上不能有62连续出现,那么就是state就是要保存前一位pre,然后分类，23.前一位如果是6那么这意味就不能是2，这里一定要保存枚举的这个数是合法*/

24.}

25.//计算完，记录状态

26.if(!limit &&!lead)dp[pos][state]=ans;

27./*这里对应上面的记忆化，在一定条件下时记录，保证一致性，当然如果约束条件不需要考虑lead，这里就是lead就完全不用考虑了*/

28.return ans;29.}

30.ll solve(ll x)31.{

32.int pos=0;

33.while(x)//把数位都分解出来

34.{

35.a[pos++]=x%10;//个人老是喜欢编号为[0,pos),看不惯的就按自己习惯来，反正注意数位边界就行

36.x/=10;37.}

38.return dfs(pos-1/*从最高位开始枚举*/,/*一系列状态 */,true,true);//刚开始最高位都是有限制并且有前导零的，显然比最高位还要高的一位视为0嘛

39.}

40.int main()41.{

42.ll le,ri;

43.while(~scanf(“%lld%lld”,&le,&ri))44.{

45.//初始化dp数组为-1,这里还有更加优美的优化,后面讲 46.printf(“%lldn”,solve(ri)-solve(le-1));47.} 48.}

注意：

那个if(!limit &&!lead &&dp[pos][state]!=-1)return dp[pos][state];limit 的数字必须要枚举，不能直接返回，每次都要算

虽然这会导致重复，但这可以解决状态冲突，而且重复计算的数字也很少 举例如下：

题目：不能出现连续的11(11、112、211都是不合法的)那么我们开始枚举：

要枚举3位数，已经枚举了两位01_，要枚举最后一位，此时状态为d[0][1] 即：在枚举个位，且前一位为1，那么显然得出d[0][1]=9 开始新的一轮枚举，枚举到11_，此时状态也是d[0][1] 因为已经有9这个值了，所以返回了，但很明显答案是0，是错的 当然可以多开一维防止状态冲突

可以看看数位DP模板题： HDU 2089 不要62 数位DP.二，递推方法

思路来自：初探数位dp

状态定义：d[i][j] 有i位数字，且第一位为j，在 0~j-1 + 000....999的符合题意的个数，如 d[4][3] 就是在 3000~3999 的符合题意的个数

还要个数组a[i]保存第i位的数字，如213，a[1]=3，注意是从右往左数（下面是从1开始数起了）

这样状态定义的能更加方便，可以预处理，因为当一个数字的第一位比题目要求的第一位小后，后面的几位能000..~999..如4269，如果第一位枚举 3 _ _ _，那么后三位可以任取

模板如下：

1.for(int i=1;i<=7;i++)//枚举位数

2.{

3.for(int j=0;j<10;j++)//枚举第i位可能出现的数

4.{

5.for(int k=0;k<10;k++)//枚举第i-1位可能出现的数

6.{

7.if(j!=4&&!(j==6&&k==2))//符合题意的条件

8.dp[i][j] += dp[i-1][k];9.} 10.} 11.}

以HDU 2089，解释怎么算出答案（不含4，62的数字）

1.#include

2.#include 3.#include

4.#include

5.using namespace std;6.int d[10][10],digit[10];

7.//d[i][j] 表示有i位数字，且第一位是j的数字的 满足题意的数量

8.void init()9.{

10.d[0][0]=1;

11.for(int i=1;i<=7;i++)12.for(int j=0;j<=9;j++)13.for(int k=0;k<=9;k++)14.if(j!=4&&!(j==6&&k==2))15.d[i][j]+=d[i-1][k];16.}

17.int solve(int x)// [0,x)

18.{

19.int len=0;20.while(x){

21.digit[++len]=x%10;22.x/=10;23.}

24.digit[len+1]=0;25.int ans=0;

26.for(int i=len;i>=1;i--){

27.for(int j=0;j

28.if(j!=4&&!(j==2&&digit[i+1]==6))29.ans+=d[i][j];30.31.if(digit[i]==4||(digit[i+1]==6&&digit[i]==2))32.break;33.}

34.return ans;35.}

36.int main(int argc, char const *argv[])37.{

38.int n,m;39.init();

40.while(cin>>n>>m,n+m)41.cout<

42.return 0;43.}

假设一个数3229 得出

0000~0999 的个数 1000~1999 的个数 2000~2999 的个数 000~099 的个数 100~199 的个数 00~99 的个数 10~19 的个数 0~8 的个数 累加就是答案了

所以该区间是[0,n)是取不到的n的，注意计算的时候要加一个1

下面是一些题目：

HDU 2089 不要62和4 HDU 3555 含49的数

HDU 3652 含13且可以被13整除

codeforces 55d A 一个数字可以被它所有非零数整除的个数 POJ 3252 Round Numbers HDU 4734 F(x)HDU 3709 Balanced Number HYSBZ 1799 self 同类分布

URAL 1057 Amount of Degrees * HDU 4507 吉哥系列故事——恨7不成妻 *

总结：

可能要用到的数位DP的题目类型：

1~10^18，求某区间（很大），有特定要求的数字的个数 如求mod，求和，可以整除各位数，不出现某些数...框架：

int DFS(intpos,......)//DFS一位一位放数字，求出答案，函数的参数保存题目要求的状态

int solve(int n)//把n一位一位拆分，求出[1,n] 的符合要求的值

难点：定义好状态！

1.dp状态要找好，不要出现状态重叠现象，注意前导0有没有影响

2.题目有求和sum，可能会很大，但可以转化为保存sum对一个数求mod的值 3.有时候dp状态定义不好可能要求每次DFS都要memset一下，换换思路想想通用的状态定义，如sum从加法改为减法

第二篇：算法总结

算法分块总结

为备战2005年11月4日成都一战，特将已经做过的题目按算法分块做一个全面详细的总结，主要突出算法思路，尽量选取有代表性的题目，尽量做到算法的全面性，不漏任何ACM可能涉及的算法思路。算法设计中，时刻都要牢记要减少冗余，要以简洁高效为追求目标。另外当遇到陌生的问题时，要想方设法进行模型简化，转化，转化成我们熟悉的东西。

图论模型的应用

分层图思想的应用：

用此思想可以建立起更简洁、严谨的数学模型，进而很容易得到有效算法。重要的是，新建立的图有一些很好的性质： 由于层是由复制得到的，所以所有层都非常相似，以至于我们只要在逻辑上分出层的概念即可，根本不用在程序中进行新层的存储，甚至几乎不需要花时间去处理。由于层之间的相似性，很多计算结果都是相同的。所以我们只需对这些计算进行一次，把结果存起来，而不需要反复计算。如此看来，虽然看起来图变大了，但实际上问题的规模并没有变大。层之间是拓扑有序的。这也就意味着在层之间可以很容易实现递推等处理，为发现有效算法打下了良好的基础。

这些特点说明这个分层图思想还是很有潜力的，尤其是各层有很多公共计算结果这一点，有可能大大消除冗余计算，进而降低算法时间复杂度。二分图最大及完备匹配的应用： ZOJ place the robots: 二分图最优匹配的应用：

最大网络流算法的应用：典型应用就求图的最小割。最小费用最大流的应用：

容量有上下界的最大流的应用：

欧拉路以及欧拉回路的应用：主要利用求欧拉路的套圈算法。最小生成树：

求最小生成树，比较常用的算法有Prim算法和Kruskal算法。前者借助Fibonacci堆可以使复杂度降为O(Vlog2V+E)，后者一般应用于稀疏图，其时间复杂度为O(Elog2V)。最小K度限制生成树：

抽象成数学模型就是：

设G=(V,E,ω)是连通的无向图，v0 ∈V是特别指定的一个顶点,k为给定的一个正整数。首先考虑边界情况。先求出问题有解时k 的最小值：把v0点从图中删去后，图中可能会出 现m 个连通分量，而这m 个连通分量必须通过v0来连接，所以，在图G 的所有生成树中 dT(v0)≥m。也就是说，当k

首先，将 v0和与之关联的边分别从图中删去，此时的图可能不再连通，对各个连通分量，分别求最小生成树。接着，对于每个连通分量V’，求一点v1，v1∈V’,且ω(v0,v1)=min{ω(v0,v’)|v’∈V’}，则该连通分量通过边(v1,v0)与v0相连。于是，我们就得到了一个m度限制生成树，不难证明，这就是最小m度限制生成树。这一步的时间复杂度为O(Vlog2V+E)我们所求的树是无根树，为了解题的简便，把该树转化成以v0为根的有根树。

假设已经得到了最小p度限制生成树，如何求最小p+1 度限制生成树呢？在原先的树中加入一条与v0相关联的边后，必定形成一个环。若想得到一棵p+1 度限制生成树，需删去一条在环上的且与v0无关联的边。删去的边的权值越大，则所得到的生成树的权值和就越小。动态规划就有了用武之地。设Best(v)为路径v0—v上与v0无关联且权值最大的边。定义father(v)为v的父结点，动态转移方程：Best(v)=max(Best(father(v)),(father(v),v))，边界条件为Best[v0]=-∞，Best[v’]=-∞|(v0,v’)∈E(T)。

状态共|V|个，状态转移的时间复杂度O(1)，所以总的时间复杂度为O(V)。故由最小p度限制生成树得到最小p+1度限制生成树的时间复杂度为O(V)。1 先求出最小m度限制生成树；

2由最小m度限制生成树得到最小m+1度限制生成树;3 当dT(v0)=k时停止。

加边和去边过程，利用动态规划优化特别值得注意。

次小生成树：

加边和去边很值得注意。

每加入一条不在树上的边，总能形成一个环，只有删去环上的一条边，才能保证交换后仍然是生成树，而删去边的权值越大，新得到的生成树的权值和越小。具体做法：

首先做一步预处理，求出树上每两个结点之间的路径上的权值最大的边，然后，枚举图中不在树上的边，有了刚才的预处理，我们就可以用O(1)的时间得到形成的环上的权值最大的边。如何预处理呢？因为这是一棵树，所以并不需要什么高深的算法，只要简单的BFS 即可。

最短路径的应用：

Dijkstra 算法应用： Folyed 算法应用：

Bellman-Ford 算法的应用：

差分约束系统的应用：

搜索算法

搜索对象和搜索顺序的选取最为重要。一些麻烦题，要注意利用数据有序化，要找一个较优的搜索出发点，凡是能用高效算法的地方尽量争取用高效算法。基本的递归回溯深搜，记忆化搜索，注意剪枝： 广搜（BFS）的应用： 枚举思想的应用： ZOJ 1252 island of logic A*算法的应用：

IDA*算法的应用，以及跳跃式搜索探索： 限深搜索，限次： 迭代加深搜索：

部分搜索+高效算法（比如二分匹配，动态规划）： ZOJ milk bottle data: 剪枝优化探索：

可行性剪枝，最优性剪枝，调整搜索顺序是常用的优化手段。

动态规划

动态规划最重要的就是状态的选取，以及状态转移方程，另外还要考虑高效的预处理（以便更好更快的实现状态转移）。最常用的思想就是用枚举最后一次操作。

状态压缩DP，又叫带集合的动态规划：题目特点是有一维的维数特别小。类似TSP问题的DP：

状态划分比较困难的题目： 树形DP：

四边形不等式的应用探索：四边形不等式通常应用是把O(n^3)复杂度O(n^2)

高档数据结构的应用

并查集的应用：

巧用并查集中的路径压缩思想： 堆的利用： 线段树的应用：

总结用线段树解题的方法

根据题目要求将一个区间建成线段树，一般的题目都需要对坐标离散。建树时，不要拘泥于线段树这个名字而只将线段建树，只要是表示区间，而且区间是由单位元素(可以是一个点、线段、或数组中一个值)组成的，都可以建线段树；不要拘泥于一维，根据题目要求可以建立面积树、体积树等等

树的每个节点根据题目所需，设置变量记录要求的值

用树形结构来维护这些变量：如果是求总数，则是左右儿子总数之和加上本节点的总数，如果要求最值，则是左右儿子的最大值再联系本区间。利用每次插入、删除时，都只对O(logL)个节点修改这个特点，在O(logL)的时间内维护修改后相关节点的变量。

在非规则删除操作和大规模修改数据操作中，要灵活的运用子树的收缩与叶子节点的释放，避免重复操作。

Trie的应用：；

Trie图的应用探索： 后缀数组的应用研究：

在字符串处理当中，后缀树和后缀数组都是非常有力的工具，其中后缀树了解得比较多，关于后缀数组则很少见于国内的资料。其实后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也不太逊色，并且，它比后缀树所占用的空间小很多。

树状数组的应用探索：；

计算几何

掌握基本算法的实现。凸包的应用：；

半平面交算法的应用：；

几何+模拟类题目：几何设计好算法，模拟控制好精度。扫描法：；

转化法：ZOJ 1606 将求所围的格子数，巧妙的转化为求多边形的面积。离散法思想的应用：；

经典算法：找平面上的最近点对。

贪心

矩形切割

二分思想应用

活用经典算法

利用归并排序算法思想求数列的逆序对数：

利用快速排序算法思想，查询N个数中的第K小数：

博弈问题

博弈类题目通常用三类解法：第一类推结论； 第二类递推，找N位置，P位置； 第三类SG函数的应用。第四类极大极小法，甚至配合上αβ剪枝。最难掌握的就是第四类极大极小法。

第一类：推结论。典型题目： 第二类：递推。典型题目：

比如有向无环图类型的博弈。在一个有向图中，我们把选手I有必胜策略的初始位置称为N位置(Next player winning)，其余的位置被称为P位置(Previous player winning)。很显然，P位置和N位置应该具有如下性质：

1． 所有的结束位置都是P位置。

2． 对于每一个N位置，至少存在一种移动可以将棋子移动到一个P位置。3． 对于每一个P位置，它的每一种移动都会将棋子移到一个N位置。

这样，获胜的策略就是每次都把棋子移动到一个P位置，因为在一个P位置，你的对手只能将棋子移动到一个N位置，然后你总有一种方法再把棋子移动到一个P位置。一直这样移动，最后你一定会将棋子移动到一个结束位置（结束位置是P位置），这时你的对手将无法在移动棋子，你便赢得了胜利。

与此同时，得到了这些性质，我们便很容易通过倒退的方法求出哪些位置是P位置，哪些位置是N位置，具体的算法为：

1． 将所有的结束位置标为P位置。

2． 将所有能一步到达P位置的点标为N位置。

3． 找出所有只能到达N位置的点，将它们标为P位置。

4． 如果在第三步中没有找到新的被标为P位置的点，则算法结束，否则转到步骤2。这样我们便确定了所有位置，对于题目给出的任一初始位置，我们都能够很快确定出是选手I获胜还是选手II获胜了。第三类：SG函数的应用。

关于SG函数的基本知识：对于一个有向图(X, F)来说，SG函数g是一个在X上的函数，并且它返回一个非负整数值，具体定义为

g(x)min{n0,ng(y)对于所有yF(x)}

1． 对于所有的结束位置x，g(x)= 0。

2． 对于每一个g(x)≠ 0的位置x，在它可以一步到达的位置中至少存在一个位置y使得g(y)= 0。

3．对于每一个g(x)＝ 0的位置x，所有可以由它一步到达的位置y都有g(y)≠ 0。

定理 如果g(xi)是第i个有向图的SG函数值，i = 1,…,n，那么在由这n个有向图组成的状态的SG函数值g(x1,…xn)= g(x1)xor g(x2)xor … xor g(xn)

第四类：极大极小法。

典型题目：ZOJ 1155：Triangle War

ZOJ 1993：A Number Game

矩阵妙用

矩阵最基本的妙用就是利用快速乘法O（logn）来求解递推关系（最基本的就是求Fibonacci数列的某项）和各种图形变换，以及利用高斯消元法变成阶梯矩阵。典型题目：

数学模型举例

向量思想的应用：

UVA 10089：注意降维和向量的规范化 ；

利用复数思想进行向量旋转。

UVA 10253：

递推

数代集合

数代集合的思想：

ACM ICPC 2002-2003, Northeastern European Region, Northern Subregion 中有一题：Intuitionistic Logic 用枚举+数代集合思想优化，注意到题中有一句话：“You may assume that the number H = |H| of elements of Hdoesn't exceed 100”，这句话告诉我们H的元素个数不会超过100，因此可以考虑用一个数代替一个集合，首先把所有的运算结果都用预处理算出来，到计算的时候只要用O(1)的复杂度就可以完成一次运算。

组合数学

Polya定理则是解决同构染色计数问题的有力工具。

补集转化思想

ZOJ 单色三角形：

字符串相关

扩展的KMP算法应用：；最长回文串； 最长公共子串； 最长公共前缀；

填充问题

高精度运算

三维空间问题专题

无论什么问题，一旦扩展到三难空间，就变得很有难度了。三维空间的问题，很考代码实现能力。

其它问题的心得

解决一些判断同构问题的方法：同构的关键在于一一对应，而如果枚举一一对应的关系，时间复杂度相当的高，利用最小表示，就能把一个事物的本质表示出来。求最小表示时，我们一定要仔细分析，将一切能区分两个元素的条件都在最小表示中体现，而且又不能主观的加上其他条件。得到最小表示后，我们往往还要寻求适当的、高效的匹配算法（例如KMP字符匹配之类的），来比较最小表示是否相同，这里常常要将我们熟悉的高效算法进行推广

第三篇：算法总结

算法分析与设计总结报告

71110415 钱玉明

在计算机软件专业中，算法分析与设计是一门非常重要的课程，很多人为它如痴如醉。很多问题的解决，程序的编写都要依赖它，在软件还是面向过程的阶段，就有程序=算法+数据结构这个公式。算法的学习对于培养一个人的逻辑思维能力是有极大帮助的，它可以培养我们养成思考分析问题，解决问题的能力。作为IT行业学生，学习算法无疑会增强自己的竞争力，修炼自己的“内功”。

下面我将谈谈我对这门课程的心得与体会。

一、数学是算法的基础

经过这门课的学习，我深刻的领悟到数学是一切算法分析与设计的基础。这门课的很多时间多花在了数学公式定理的引入和证明上。虽然很枯燥，但是有必不可少。我们可以清晰的看到好多算法思路是从这些公式定理中得出来的，尤其是算法性能的分析更是与数学息息相关。其中有几个定理令我印象深刻。

①主定理

本门课中它主要应用在分治法性能分析上。例如：T(n)=a*T(n/b)+f(n)，它可以看作一个大问题分解为a个子问题，其中子问题的规模为b。而f(n)可看作这些子问题的组合时的消耗。这些可以利用主定理的相关结论进行分析处理。当f(n)量级高于nlogba时，我们可以设法降低子问题组合时的消耗来提高性能。反之我们可以降低nlogba的消耗，即可以扩大问题的规模或者减小子问题的个数。因此主定理可以帮助我们清晰的分析出算法的性能以及如何进行有效的改进。

②随机算法中的许多定理的运用

在这门课中，我学到了以前从未遇见过的随机算法，它给予我很大的启示。随机算法不随机，它可通过多次的尝试来降低它的错误率以至于可以忽略不计。这些都不是空穴来风，它是建立在严格的定理的证明上。如素数判定定理是个很明显的例子。它运用了包括费马小定理在内的各种定理。将这些定理进行有效的组合利用，才得出行之有效的素数判定的定理。尤其是对寻找证据数算法的改进的依据，也是建立在3个定理上。还有检查字符串是否匹配也是运用了许多定理：指纹的运用，理论出错率的计算，算法性能的评价也都是建立在数学定理的运用上。

这些算法都给予了我很大启发，要想学好算法，学好数学是必不可少的。没有深厚的数学功力作为地基，即使再漂亮的算法框架，代码实现也只能是根底浅的墙上芦苇。

二、算法的核心是思想

我们学习这门课不是仅仅掌握那几个经典算法例子，更重要的是为了学习蕴含在其中的思想方法。为什么呢？举个例子。有同学曾问我这样一个问题：1000只瓶子装满水，但有一瓶有毒，且毒发期为1个星期。现在用10只老鼠在一个星期内判断那只瓶子有毒，每只老鼠可以喝多个瓶子的水，每个瓶子可以只喝一点。问如何解决？其实一开始我也一头雾水，但是他提醒我跟计算机领域相关，我就立马有了思路，运用二进制。因为计算机的最基本思想就是二进制。所以说，我们不仅要学习算法，更得学习思想方法。

①算法最基本的设计方法包括分治法，动态规划法，贪心法，周游法，回溯法，分支定界法。我们可利用分治法做快速排序，降低找n个元素中最大元和最小元的量级，降低n位二进制x和y相乘的量级，做Strassen矩阵乘法等等。它的思想就是规模很大的问题分解为规模较小的独立的子问题，关键是子问题要与原问题同类，可以采取平衡法来提高性能。

动态规划法是把大问题分解为子问题，但是子问题是重复的，后面的问题可以利用前面解决过的问题的结果。如构造最优二叉查找树，解决矩阵连乘时最小计算次数问题，寻找最长公共子序列等等。

贪心法就是局部最优法，先使局部最优，再依次构造出更大的局部直至整体。如Kruscal最小生成树算法，求哈夫曼编码问题。

周游法就是简单理解就是采取一定的策略遍历图中所有的点，典型的应用就是图中的深度优先搜索(DFS)和广度优先搜索(BFS)。

回溯法就是就是在满足一定的条件后就往前走，当走到某步时，发现不满足条件就退回一步重新选择新的路线。典型的应用就是8皇后问题，平面点集的凸包问题和0-1背包问题。

分支定界法：它是解决整数规划问题一种最常用的方法。典型应用就是解决整数规划问题。

②评价算法性能的方法如平摊分析中的聚集法，会计法和势能法。聚集法就是把指令分为几类，计算每一类的消耗，再全部叠加起来。会计法就是计算某个指令时提前将另一个指令的消耗也算进去，以后计算另一个指令时就不必再算了。势能法计算每一步的势的变化以及执行这步指令的消耗，再将每一步消耗全部累计。

这几种方法都是平摊分析法，平摊分析的实质就是总体考虑指令的消耗时间，尽管某些指令的消耗时间很大也可以忽略不计。上述三种方法难易程度差不多，每种方法都有属于它的难点。如聚集法中如何将指令有效分类，会计法中用什么指令提前计算什么指令的消耗，势能法中如何选取势能。因此掌握这些方法原理还不够，还要学会去应用，在具体的问题中去判断分析。

三、算法与应用紧密相关

我认为学习算法不能局限于书本上的理论运算，局限于如何提高性能以降低复杂度，我们要将它与实际生活联系起来。其实算法问题的产生就来自于生活，设计出高效的算法就是为了更好的应用。如寻找最长公共子序列算法可以应用在生物信息学中通过检测相似DNA片段的相似成分来检测生物特性的相似性，也可以用来判断两个字符串的相近性，这可应用在数据挖掘中。快速傅立叶变换（FFT）可应用在计算多项式相乘上来降低复杂度，脱线min算法就是利用了Union-Find这种结构。还有图中相关算法，它对于解决网络流量分配问题起了很大的帮助，等等。

这些应用给了我很大的启发：因为单纯讲一个Union-Find算法，即使了解了它的实现原理，遇到具体的实际问题也不知去如何应用。这就要求我们要将自己学到的算法要和实际问题结合起来，不能停留在思想方法阶段，要学以致用，做到具体问题具体分析。

四、对计算模型和NP问题的理解

由于对这部分内容不是很理解，所以就粗浅的谈一下我的看法。

首先谈到计算模型，就不得不提到图灵计算，他将基本的计算抽象化，造出一个图灵机，得出了计算的本质。并提出图灵机可以计算的问题都是可以计算的，否则就是不可计算的。由此引申出一个著名论题：任何合理的计算模型都是相互等价的。它说明了可计算性本身不依赖于任何具体的模型而客观存在。

NP问题比较复杂，我认为它是制约算法发展的瓶颈，但这也是算法分析的魅力所在。NP问题一般可分为3类，NP-C问题，NP-hard问题以及顽型问题。NP-C它有个特殊的性质，如果存在一个NP-C问题找到一个多项式时间的解法，则所有的NP-C问题都能找到多项式时间解法。如哈密顿回路问题。NP-hard主要是解决最优化问题。它不一定是NP问题。这些问题在规模较小时可以找出精确解，但是规模大时，就因时间太复杂而找不到最优解。此时一般会采用近似算法的解法。顽型问题就是已经证明不可能有多项式时间的算法，如汉诺塔问题。

最后谈谈对这门课程的建议

①对于这门算法课，我认为应该加强对算法思想方法的学习。所以我建议老师可不可以先抛出问题而不给出答案，讲完一章，再发课件。让我们先思考一会儿，或者给出个奖励机制，谁能解决这个问题，平时成绩加分。这在一定程度上会将强我们思考分析问题的能力。因为我感觉到，一个问题出来，未经过思考就已经知晓它的答案，就没什么意思，得不到提高，而且也不能加深对问题的思考和理解。下次遇到类似的问题也就没有什么印象。而且上课让我们思考，点名回答问题可以一定程度上有效的防止不认真听课的现象。

②作业安排的不是很恰当。本门课主要安排了三次作业，个人感觉只有第一次作业比较有意思。后面两次作业只是实现一下伪代码，没有太多的技术含量。而且对于培养我们的解决问题的能力也没有太多的帮助，因为这间接成为了程序设计题，不是算法设计题。

③本门课的时间安排的不太恰当，因为本学期的课程太多，压力太大。没有太多的时间去学习这门课程。因为我相信大家都对它感兴趣，比较重视，想花功夫，但苦于没时间。所以可不可以将课程提前一个学期，那时候离散数学也已经学过，且课程的压力也不是很大。错开时间的话，我觉得应该能够更好提高大家算法分析设计的能力。

第四篇：认识数位

认识数位

教学目标：

知识与技能：。通过计数器使学生认识个位，十位、百位，了解个位、十位上数表示含义，会正确读、写100以内的数。

过程与方法：。通过动手操作、观察，直观体验数的意义，数的读、写法的过程方法。

情感态度、价值观：在学习中建立数感，能积极参与学习，形成独立思考和合作学习的习惯。

学习方式：动手操作，自主合作交流探究。

教学准备：每人一个计数器，（学具）幻灯片（分片）数位、数字卡片。

教学过程：

环节 学生活动 教师活动 设计意图

创设情境 生答 出示计数器

同学们你们认识这是什么学具吗？

（生如果不认识，师直接点出，这是计数器，是用来学习数用的）。

激发学生强烈的学习欲望。

探

究

与

体

验 自由读，在计数器上标出个、十、百位。

从右边数第一位是个位，第二位是十位，第三位是百位。

指生读，齐读。

学生动手拨

读作二十四，写作24。

因为十位拨的是2，个位拨的是4，所以就是24。

24中的2表示2个十，4表示4个一。

自己在计数器上拨数

读一读、说一说、写一写。

汇报：

读作四十二，写做42。因为4在十位上表示4个十，2在个位上表示2个一。所以写做42。

学生动手拨数、读数

说意义，“十位上的5表示5个十，个位上的5表示5个一”。

学生看图，照样子拨珠，同桌交流，汇报：计数器的十位上的数是6，表示6个十，个位上没有珠，表示一个也没有用零表示。这个计数器上的珠子表示60。

1、认识计数器上的数位。

幻灯片出示。

同学们，从右边数第一位、第二位、第三位各是什么位？（若学生回答不出来，教师讲解）。从右边数第一位是个位，第二位是十位，第三位是百位。

2、拨数，写数、读数。

（1）教师说数学生拨。

在计数器的十位上拨2，个位上拨4。这个数读作多少？该怎样写出来？你们试着拨一拨、说一说。你是怎么知道的？

（2）写法及数表示的意义：

十位上是2，就在十位上写2，表示2个十。个位上是4，就在个位上写4，表示4个一。读作二十四。板书24。

同桌同学互相说一说24中2和4各表示什么？

1、练习拨一拨、读一读。

教师说数，在十位上拨4

在个位上拨2，读读、写写、说说你是怎么知道的？

让学生在计数器上拨出55。

（让学生说说这两个5的意义有什么不同）

4、出示图片（试一试）

照样子拨珠再写数，并读出来

重点引导：第2个计数器，个位上没珠，怎么办？写几表示

引导学生归纳写数的方法。

计数器的十位上是几就在十位上写几，计数器的个位上是几就在个位上写几。通过自己利用计数器拨数、读数、写数等多种形式调动学生的多种感官参与学习活动，使学生对数的写法、读法以及数位有了进一步的体验和感悟，对数的意义也有了初步的了解。

在学生操作的同时，注重让学生用语言表达数的意义，这样学生对数的读法、写法、数位理解的就更加深刻了。

巩

固

与

应

用

1、题：独立完成 集体订正。

2、题同桌互读

指生读

3、题在计数器上拨一拨，然后写出来。

4、题：同桌交流，填空。完成练习1、2、3、4题数字游戏。

4题：指导第1图

1个〇是十，4个〇是多少？

1个△是一5个△是多少？

4个十5个一合起来是多少？

数字游戏：分组进行：一人说数一人在数位表上拨。多种形式的练习，巩固加深理解了所学知识，同时也激发了学生学习数学的热情。

第五篇：web 算法总结

1.去掉超链接的下画线： 在 //添加这句就行。 2.格式为：你需要添加下画线的文字 3.获取时间

我们可以通过使用DataTime这个类来获取当前的时间。通过调用类中的各种方法我们可以获取不同的时间：如：日期（2008-09-04）、时间（12：12：12）、日期+时间（2008-09-04 12：11：10）等。

//获取日期+时间

DateTime.Now.ToString();

// 2008-9-4 20:02:10 DateTime.Now.ToLocalTime().ToString();

// 2008-9-4 20:12:12 //获取日期

DateTime.Now.ToLongDateString().ToString();

// 2008年9月4日 DateTime.Now.ToShortDateString().ToString();

// 2008-9-4 DateTime.Now.ToString(“yyyy-MM-dd”);

// 2008-09-04 DateTime.Now.Date.ToString();

// 2008-9-4 0:00:00 //获取时间 DateTime.Now.ToLongTimeString().ToString();

// 20:16:16 DateTime.Now.ToShortTimeString().ToString();

// 20:16 DateTime.Now.ToString(“hh:mm:ss”);

// 08:05:57 DateTime.Now.TimeOfDay.ToString();

// 20:33:50.7187500 //其他

DateTime.ToFileTime().ToString();

// ***000 DateTime.Now.ToFileTimeUtc().ToString();

// ***750 DateTime.Now.ToOADate().ToString();

// 39695.8461709606 DateTime.Now.ToUniversalTime().ToString();

// 2008-9-4 12:19:14 DateTime.Now.Year.ToString();

获取年份

// 2008 DateTime.Now.Month.ToString();

获取月份

// 9 DateTime.Now.DayOfWeek.ToString();获取星期

// Thursday DateTime.Now.DayOfYear.ToString();获取第几天

// 248 DateTime.Now.Hour.ToString();

获取小时

// 20 DateTime.Now.Minute.ToString();

获取分钟

// 31 DateTime.Now.Second.ToString();

获取秒数

// 45 //n为一个数,可以数整数,也可以事小数 dt.AddYears(n).ToString();

//时间加n年 dt.AddDays(n).ToString();

//加n天 dt.AddHours(n).ToString();

//加n小时 dt.AddMonths(n).ToString();

//加n个月 dt.AddSeconds(n).ToString();

//加n秒 dt.AddMinutes(n).ToString();

//加n分 SQL语句使用时间和日期的函数

getdate():获取系统当前时间

dateadd(datepart,number,date):计算在一个时间的基础上增加一个时间后的新时间值,比如：dateadd(yy,30,getdate())datediff(datepart,startdate,enddate):计算两个时间的差值,比如：datediff(yy,getdate(),'2008-08-08')dataname(datepart,date):获取时间不同部分的值，返回值为字符串 datepart(datepart,date):和datename相似，只是返回值为整型 day(date):获取指定时间的天数 month(date):获取指定时间的月份 year(date):获取指定时间的年份 select year(getdate())：当前年份