两个题目何民春.ppt

普及组复赛模块 常用数据结构（堆栈、队列、字符串、链表、树、图） 查找、排序（选择、冒泡、插入、快速、归并、计数） 数学在信息学竞赛中的应用 高精度加法、乘法 递归递推 穷举、回溯、有哪些信誉好的足球投注网站优化 模拟法 分治与贪心算法 动态规划  思考题 例8.2一矩形阵列由数字0-9组成，数字1-9代表细胞，细胞的定义是沿细胞数字上下左右如果还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。 如阵列： 4 10 0234500067 1034560500 2045600671 0000000089 解决四个问题 怎样来存储 如何统一探索方向均为四个 如何记录踪迹 如何防止重复探索 * 简单类型 整型、实型、字符型、布尔型 静态数据类型 构造类型 数组、记录、集合、字符串 文件、指针 动态数据的类型 线性结构 数组、栈、队列、链表、串 非线性结构 树、图 编一个程序，找出一条通过迷宫的路径。在任何一个格子中，可以向8个方向前进，这里有兰色方块的单元表示走不通，将从入口处经过迷宫到出口处的最短的一条通路打印出来。　　 例4迷宫问题 入口 出口 分析（1）怎样来存储迷宫？将它变成0，1二维数组。这样上述迷宫可转化为： 0 1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 0 1 0 0 1 0 1 0 1 0 1 1 1 1 0 1 1 1 0 （2）在迷宫中怎样探索路径？有几个方向可以探索呢？ *只有三个探索方向的位置。如mg[1,1] *有五个探索方向的位置。如mg[3,1] *有八个探索方向的位置。如mg[3,2] 思考：能否都转化为八个方向的探索呢？ 这样存储的迷宫数组就转化成： 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 0 1 0 0 1 0 1 0 1 0 1 1 1 1 0 1 1 1 0 因此，数组定义为: Mg:array[0..m+1,0..n+1] of integer; 而探索方向则变成了统一的情况，都探索8个方向： （x-1,y+1） （x,y） （x-1,y） （x+1,y） （x,y+1） （x+1,y+1） （x-1,y-1） （x,y-1） （x+1,y-1） Dx Dy 0 1 1 1 1 0 1 -1 0 -1 -1 -1 -1 0 -1 1 这样可以定义一个二维数组记录探索方向。 （3）如何才能记录踪迹，并把探索的踪迹记忆下来呢？ 踪迹一般应包括来处和当前位置，可以需要用记录类型 Node=record X,y:integer; Pre:0..r; End; 用一个对队列记忆探索的踪迹： Sqtype=array[1..r] of node; 例如：从（1，1）入口到达（6，8），往下探索时队列的情况 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 0 1 0 0 1 0 1 0 1 0 1 1 1 1 0 1 1 1 0 （4）如何防止重复探索：将迷宫中的0替换为-1 procedure Qini(var sQ:sqtype); begin sQ[1].x:=1;sq[1].y:=1; Sq[1].pre:=0 F:=0;r:=1;mg[1,1]:=-1; end; 具体程序见mg2.pas 思考：与上面的迷宫问题有什么异同点？ 参考程序 著名的瑞士计算机科学家沃思（N.Wirth)教授提出 数据结构 +算法=程序