用计算机解决问题一般步骤.docx
《用计算机解决问题一般步骤.docx》由会员分享，可在线阅读，更多相关《用计算机解决问题一般步骤.docx（10页珍藏版）》请在冰点文库上搜索。
用计算机解决问题一般步骤
引言
用计算机解决问题一般步骤：
一般来讲，用计算机解决一个具体问题时，大致通过以下几个步骤：
首先要从具体问题抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编出程序进行测试调整知道的到最终解答。
寻求数学模型的实质就是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。
三种经典的数学模型
图书书目自动检索系统——线性关系
博弈问题——树
城市道路问题——图
数据结构（datastructure）
简单的解释：
彼此之间存在一种或多种特定关系的数据元素的集合。
数据间的联系有逻辑关系、存储联系，通常的数据结构指的是逻辑结构。
前面提到的三种经典的数学模型表现了数据结构的大体结构，数据结构通常有如下四种关系：
（1）集合结构
（2）线性结构（3）树形结构（4）图状结构
☆线性表
（一）
N个数据元素的有限序列
存储结构：
顺序存储结构、链式存储结构
（1）
（2）
（3）
（4）
（5）
（6）
（7）
（8）
12
13
15
22
34
38
43
20
当需要在顺序存储的线性表中插入一个数据元素时，需要顺序移动后续的元素以“腾”出某个适合的位置放置新元素。
删除元素呢？
☆线性表
（二）
链式存储
插入新元素的时候只需要改变指针所指向的地址。
☆二维数组与线性表
若是某一线性表，它的每一个数据元素别离是一个线性表，这样的二维表在数据实现上通常利用二维数组。
二维数组的一个形象比喻——
多个纵队形成的方块m*n
☆数组地址计算问题
题目描述：
已知N*（N+1）/2个数据，按行的顺序存入数组b[1],b[2],…中。
其中第一个下标表示行，第二个下标表示列。
若aij（i>=j,j=1,2,…,,n）存于b[k]中，问：
k,i,j之间的关系如何表示？
给定k值，写出能决定相应i,j的算法。
答案
①K=i*（i-1）/2+j
②Read（k）;
Fori:
=1tokdo
forj:
=1toido
ifk=（trunc（I*（I-1）/2）+j）thenwriteln（k,’对应的i,j为：
‘,i,’,’,j）
☆栈
特殊的线性表
操作特点：
后进先出（LastInFirstOut）
栈顶——表尾
栈底——表头
空栈
☆栈（考题分析）
（1998）栈S初始状态为空，现有5个元素组成的序列{1，2，3，4，5}，对该序列在栈S上一次进行如下操作（从序列中的1开始，出栈后再也不进栈）：
进栈、进栈、进栈、出栈、进栈、出栈、进栈。
问出栈的元素序列是______D
（A）{5,4,3,2,1}（B）{2,1}（C）{2,3}（D）{3,4}
☆队列
先进先出
允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。
☆循环队列
头指针指向队列中队头元素的前一个位置，尾指针指示队尾元素在队列中的当前位置。
（R-F+N）modN
☆树
根、叶子、子树
结点的度：
结点拥有的子树数
二叉树
☆二叉树
特点：
每一个结点最多只有二棵子树，而且二叉树的子树有左右之分。
第i层最多有2i-1个结点（i>=1）
深度为K的二叉树最多有2k-1个结点（K>=1）
☆二叉树的遍历
先（根）序遍历
ABDFGCEH
中（根）序遍历
BFDGACHE
后（根）序遍历
FGDBHECA
☆例题分析
给出一棵二叉树的中序遍历：
DBGEACHFI与后序遍历：
DGEBHIFCA，画出此二叉树。
☆图
☆图的存储结构
邻接矩阵
有向图、无向图、带权图的邻接矩阵
☆排序
冒泡排序
选择排序
快速排序
希尔排序
一、插入排序（InsertionSort）
1.大体思想：
每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列仍然有序；直到待排序数据元素全数插入完为止。
2.排序进程：
【示例】：
[初始关键字][49]38659776132749
J=2（38）[3849]659776132749
J=3（65）[384965]9776132749
J=4（97）[38496597]76132749
J=5（76）[3849657697]132749
J=6（13）[133849657697]2749
J=7（27）[13273849657697]49
J=8（49）[1327384949657697]
ProcedureInsertSort（VarR:
FileType）;
N]按递增序进行插入排序,R[0]是监视哨.,R[n]大体思想：
每一趟从待排序的数据元素当选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全数待排序的数据元素排完。
2.排序进程：
【示例】：
初始关键字[4938659776132749]
第一趟排序后13［38659776492749]
第二趟排序后1327［659776493849]
第三趟排序后132738[9776496549]
第四趟排序后13273849[49976576]
第五趟排序后1327384949[979776]
第六趟排序后132738494976[7697]
第七趟排序后13273849497676[97]
最后排序结果1327384949767697
ProcedureSelectSort（VarR:
FileType）;N]进行直接选择排序N]当选最小的元素R[K]大体思想：
两两比较待排序数据元素的大小，发现两个数据元素的顺序相反时即进行互换，直到没有反序的数据元素为止。
2.排序进程：
假想被排序的数组R［1..N］垂直竖立，将每一个数据元素看做有重量的气泡，按照轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违背本原则的轻气泡，就使其向上"漂浮"，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。
【示例】：
4913131313131313
3849272727272727
6538493838383838
9765384949494949
7697654949494949
1376976565656565
2727769776767676
4949497697979797
ProcedureBubbleSort（VarR:
FileType）大体思想：
在当前无序区R[1..H]中任取一个数据元素作为比较的"基准"（不妨记为X），用此基准将当前无序区划分为左右两个较小的无序区：
R[1..I-1]和R[I+1..H]，且左侧的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即R[1..I-1]≤≤R[I+1..H]（1≤I≤H），当R[1..I-1]和R[I+1..H]均非空时，别离对它们进行上述的划分进程，直至所有无序子区中的数据元素均已排序为止。
2.排序进程：
【示例】：
初始关键字[4938659776132749］
第一次互换后［2738659776134949］
第二次互换后［2738499776136549］
J向左扫描，位置不变，第三次互换后［2738139776496549］
I向右扫描，位置不变，第四次互换后［2738134976976549］
J向左扫描［2738134976976549］
（一次划分进程）
初始关键字［4938659776132749］
一趟排序以后［273813］49［76976549］
二趟排序以后［13］27［38］49［4965］76［97］
三趟排序以后1327384949［65］7697
最后的排序结果1327384949657697
各趟排序以后的状态
ProcedureParttion（VarR:
FileType;L,H:
Integer;VarI:
Integer）;
T]快速排序T]为空或只有一个元素是无需排序T]做划分T]大体思想：
堆排序是一树形选择排序，在排序进程中，将R[1..N]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。
2.堆的概念:
N个元素的序列K1,K2,K3,...,Kn.称为堆，当且仅当该序列知足特性：
Ki≤K2iKi≤K2i+1（1≤I≤[N/2]）
六、几种排序算法的比较和选择
1.选取排序方式需要考虑的因素：
（1）待排序的元素数量n；
（2）元素本身信息量的大小；
（3）关键字的结构及其散布情况；
（4）语言工具的条件，辅助空间的大小等。
2.小结：
（1）若n较小（n<=50），则可以采用直接插入排序或直接选择排序。
由于直接插入排序所需的记录移动操作较直接选择排序多，因此当记录本身信息量较大时，用直接选择排序较好。
（2）若文件的初始状态已按关键字大体有序，则选用直接插入或冒泡排序为宜。
（3）若n较大，则应采历时间复杂度为O（nlog2n）的排序方式：
快速排序、堆排序或归并排序。
快速排序是目前基于比较的内部排序法中被以为是最好的方式。
（4）在基于比较排序方式中，每次比较两个关键字的大小以后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定进程，由此可以证明：
当文件的n个关键字随机散布时，任何借助于"比较"的排序算法，至少需要O（nlog2n）的时间。
（5）当记录本身信息量较大时，为避免花费大量时间移动记录，可以用链表作为存储结构。
升级会员 