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

《转化思想在信息学中的运用.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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简单的模型转化。ProblemA(a.*(pas,c,cpp))靖仇和小雪要找玉儿，来到条船上。几经调查，发现玉儿不在船上。虽然玉儿不在船上，但是出于人道主义，他们决定营救船上其他女孩子。船为N*M的矩形，有些格子中关了女孩；而有些格子则是陷阱。在船上每走一步需要1个单位时间。如果走入陷阱，就需要打开机关，会耽搁1个

3、单位时间。由于情况紧急，靖仇和小雪还要去找玉儿和神农鼎，所以请你写个程序帮助他们最快地救出所有女孩子。注意：救女孩子不需要额外的时间。时限：5s例1输入：(a.in)第一行包含两个整数N和M（1≤N,M≤30），给出了船的大小。接下来是N行M列的字符矩阵，是地图信息：“S”代表出发地点，”.”代表空地；”*”代表墙，不可走过；”m”代表女孩子；”T”代表陷阱。输入数据保证，“S”只出现一次，”m”最多出现16个。输出：(a.out)救出所有女孩子的最短时间。如果无法救出所有mm，输出”pity”。例1SampleInp

4、ut:36m****mT****.S...T.SampleOutput:14例1先看一个简单的问题，从一个点到另一个点的最短长度。这个问题可以用宽度优先搜索来解决。时间复杂度o(n*m)。本问题难点在于女孩不只一个。但是因为同一个地方可以重复走，所以拯救是不相互影响的。也就是整个过程是分阶段的。问题就转化成为确定一个拯救顺序。对于这个问题算法就是搜索+最短路，思路不是很清晰，处理比较复杂。例1如果进一步转化模型：将女孩看成是图的顶点，两个女孩之间的距离看成是边长。问题就转化为求一张无向图的哈密尔顿路。转化成TSP模型之

5、后思路顺，处理简单。而且可以选择的算法也多起来了，动态规划，搜索，以及近似解算法等等。例2数学转化之补集转化：补集转化的基础：容斥原理。例2通俗的讲就是容易求得的量表示那些比较棘手的量。树的果实森林中生长着许多奇特的果树，它们不仅外形独特，其果实更是可口。这天，两只小虫Nileh和Nixed决定一起分享一颗果树。他们从早晨一直辛勤工作到下午，终于把这颗果树锯倒。他们观察着这颗果树，果树开始端是露出地面的根部，接着像其他果树一样，有着诸多分叉（如图所示就是一颗果树），在每个分叉处生长着果实，自然Nileh和Nixed的食

6、物就是这些果实了！他们准备例2把果树分成两部分，每个虫虫得到各自的一部分，而分果树的方法就是选择一个分叉点，虫虫将他们咬断（自然分叉点上的果实也被扔掉了），这样果树就变成了两个部分（每个部分不一定是连在一起的）：分叉点上面的部分和分叉点下面的部分。Nileh和Nixed就会各自选一个部分吃啦！比如对于左边这颗果树，如果他们咬掉蓝色的果子，那么就被分为红色和黄色的两个部分。例2考虑到被咬掉的果子会被浪费，他们想尽可能的减少浪费，于是虫虫给每个果子一个美味值，对于每个果子，他们决定计算如果咬掉这个果子，上面部分、下面部分和

7、从树根到这个分叉点的路径中比这个果子更美味的果子各有多少个。他们以此来选择最终要被咬掉的果子是哪一个。遗憾的是果树可能很庞大，而小虫几乎是不会计算的，身为程序员的你帮帮他们吧。例2【输入格式】输入文件第一行一个整数n（n<=105）表示树的分叉数（包括树根）。输入文件的第i(2<=i<=n)行一个数pi，表示分叉i的上一级分叉的编号（pi

8、n行，每行三个数，分别表示咬掉第i个果实后上面部分、下面部分、从树根到这个分叉点的路径中比它美味的果实数。【示例】tree.in４１１２２４１３例2tree.out200000031011我们不妨设上面部分的数目为fa,下面部分的数目为fb，设路径上的数目为fc。例2比较简单的是求fc。我们可以DFS遍历+线段树解决，DFS到某个