转化思想在信息学中的运用.ppt

转化思想在信息学中的运用,柯桥中学 刘飞,引例,有一个n*m的表格，有一个人要从这张表格的作上角走到表格的右下角。每次只能向右走或者向下走。求所有的走法。 建立递推模型，用f(i,j)表示从左上角走到第(i,j)所有的走法,则有： 算法时间复杂度o(n*m)。 如果n,m比较大呢？,引例,转化： 如果我们将向下走定义为A，向右走定义为B，那么对于一种方案，显然有A=n-1,B=m-1。两种不同方案实质就是A,B的顺序问题。于是问题转化为计算有n-1个A，m-1个B的排列数。这个计算的时间复杂度是o(1)的。,引例小结,从上面一个简单的例子，我们已经感受到了转化思想的重要性。 世间万物皆离不开转化，我们摄入的食物转化成为能量，光合作用将太阳能转化成为化学能。 总而言之，没有了转化，世界将是黑白的。如果信息学中没有了转化，我们将寸步难移。,例1,简单的模型转化。 Problem A(a.*(pas,c,cpp) 靖仇和小雪要找玉儿，来到条船上。 几经调查，发现玉儿不在船上。虽然玉儿不在船上，但是出于人道主义，他们决定营救船上其他女孩子。 船为N*M的矩形，有些格子中关了女孩；而有些格子则是陷阱。在船上每走一步需要1个单位时间。如果走入陷阱，就需要打开机关，会耽搁1个单位时间。 由于情况紧急，靖仇和小雪还要去找玉儿和神农鼎，所以请你写个程序帮助他们最快地救出所有女孩子。注意：救女孩子不需要额外的时间。 时限：5s,例1,输入：(a.in) 第一行包含两个整数N和M（1N, M30），给出了船的大小。 接下来是N行M列的字符矩阵，是地图信息：“S”代表出发地点，”.”代表空地；”*”代表墙，不可走过；”m”代表女孩子；”T”代表陷阱。 输入数据保证，“S”只出现一次，”m”最多出现16个。 输出：(a.out) 救出所有女孩子的最短时间。如果无法救出所有mm，输出”pity”。,例1,Sample Input: 3 6 m*m T*. S.T. Sample Output: 14,例1,先看一个简单的问题，从一个点到另一个点的最短长度。这个问题可以用宽度优先搜索来解决。时间复杂度o(n*m)。 本问题难点在于女孩不只一个。但是因为同一个地方可以重复走，所以拯救是不相互影响的。也就是整个过程是分阶段的。问题就转化成为确定一个拯救顺序。 对于这个问题算法就是搜索+最短路，思路不是很清晰，处理比较复杂。,例1,如果进一步转化模型： 将女孩看成是图的顶点，两个女孩之间的距离看成是边长。问题就转化为求一张无向图的哈密尔顿路。 转化成TSP模型之后思路顺，处理简单。而且可以选择的算法也多起来了，动态规划，搜索，以及近似解算法等等。,例2,数学转化之补集转化： 补集转化的基础：容斥原理。,例2,通俗的讲就是容易求得的量表示那些比较棘手的量。 树的果实 森林中生长着许多奇特的果树，它们不仅外形独特，其果实更是可口。这天，两只小虫Nileh和Nixed决定一起分享一颗果树。他们从早晨一直辛勤工作到下午，终于把这颗果树锯倒。他们观察着这颗果树，果树开始端是露出地面的根部，接着像其他果树一样，有着诸多分叉（如图所示就是一颗果树），在每个分叉处生长着果实，自然Nileh和Nixed的食物就是这些果实了！他们准备,例2,把果树分成两部分，每个虫虫得到各自的一部分，而分果树的方法就是选择一个分叉点，虫虫将他们咬断（自然分叉点上的果实也被扔掉了），这样果树就变成了两个部分（每个部分不一定是连在一起的）：分叉点上面的部分和分叉点下面的部分。Nileh和Nixed就会各自选一个部分吃啦！比如对于左边这颗果树，如果他们咬掉蓝色的果子，那么就被分为红色和黄色的两个部分。,例2,考虑到被咬掉的果子会被浪费，他们想尽可能的减少浪费，于是虫虫给每个果子一个美味值，对于每个果子，他们决定计算如果咬掉这个果子，上面部分、下面部分和从树根到这个分叉点的路径中比这个果子更美味的果子各有多少个。他们以此来选择最终要被咬掉的果子是哪一个。遗憾的是果树可能很庞大，而小虫几乎是不会计算的，身为程序员的你帮帮他们吧。,例2,【输入格式】 输入文件第一行一个整数n（n=105）表示树的分叉数（包括树根）。 输入文件的第i(2=i=n)行一个数pi，表示分叉i的上一级分叉的编号（pii）。（1号分叉即树根，它没有上级分叉点） 输入文件的第n+i(1=i=n)行一个正整数ai，表示生长在i号分叉点上的果实的美味值。（每个果子的美味值不相等）,例2,【输出格式】 输出共n行，每行三个数，分别表示咬掉第i个果实后上面部分、下面部分、从树根到这个分叉点的路径中比它美味的果实数。 【示例】 tree.in ,例2,tree.out 2 0 0 0 0 0 0 3 1 0 1 1 我们不妨设上面部分的数目为fa,下面部分的数目为fb，设路径上的数目为fc。,例2,比较简单的是求fc。我们可以DFS遍历+线段树解决，DFS到某个果子的时候将这个果子插入线段树，fc就是这时线段树中比某个果子大的数目，如果以某个果子为根的子树已经完全遍历，就将他从线段树中删除。 第一问就这样解决了，如果先对数据进行离散化，时间复杂度是o(nlogn)。,例2,对于fa和fb我们需要进行一定的转化。 如果我们设fri为顺序DFS序列中比第i个果子大的果子的个数，fli为从左往右逆序DFS中比第i个果子大的果子的个数,然后再用sumi表示整棵树中比第i果子大的果子的个数。,fli,fri,fci,fai,综合一下，我们可以得到,fli,fri,fci,fai,从上图可以看出 : fri+fli=sumi+fci-fai 还有一个潜在的关系: fai+fbi = sumi,求解fr,fl可以用类似求fc的方法求解，sum可以通过排序然后统计解决。所以这道题目在o(n log n) 的时间复杂度内得到了很好地解决。,总结,问题,较简单的问题,更加简单的问题,正确的解,转化,再转化,还是转化,总结,转化