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