转化思想在信息学中的运用.ppt
《转化思想在信息学中的运用.ppt》由会员分享,可在线阅读,更多相关《转化思想在信息学中的运用.ppt(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,通俗的讲就是容易求得的量表示那些比较棘手的量。 树的果实 森林中生长着许多奇特的果树,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 转化 思想 信息学 中的 运用
链接地址:https://www.31doc.com/p-2096763.html