《转化思想在信息学中的运用》由会员分享,可在线阅读,更多相关《转化思想在信息学中的运用(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) 的时间复杂度内 得到了很好地解决。总结问 题较简单 的问题更加简单 的问题正确的解转化再转化还是转化总结 转化要遵循问题的本质。转化后问题 的解一定是原题的解。 转化要以简化问题为目的。转化的唯 一目的是使得问题可以更加容易的被解决 。 只有做到上面的两点,转化才会给你 带来解决问题的灵感。 让我们让转化在信息学中绽放光彩。