Pascal高级教程-算法篇

Pascal高级教程-算法篇82111668_2012出品[e-mail]@126.com目录•前言•预备算法•数据结构•穷举与贪心•动态规划•程序设计的基本思路与算法评价•后记前言预备算法-目录•高精度（上）•高精度（下）•排序（上）•排序（中）•排序（下）高精度•引入：•读入两个数（n,m），输出和。•10100=n,m=10200•思想：•将数字以字符串方式读入，转为数字数组，模拟正常竖式计算。排序•插入排序•基数排序（桶排序）•快速排序快速排序数据结构-目录•队列•栈•二叉树•图（上）•图（下）•延伸：搜索与剪枝队列•FIFO•顺序队列•链表队列队列标准定义typequeue=objectconstmaxn=1000;data:array[1..maxn]ofinteger;front,rear:integer;functionfull():boolean;functionempty():boolean;procedureadd(n:integer);proceduredel();procedureprintf();end;栈顺序栈指针栈栈的标准定义typestack=objectconstmaxn=1000;data:array[1..maxn]ofinteger;bottom,top:Integer;functionfull():boolean;functionempty():boolean;procedurepop();procedurepush(n:integer);end;二叉树数组模拟（2种）指针模拟先序中序后序宽度先序遍历procedurefirst(p:point);beginifp=nilthenexit;writeln(p^.data);first(p^.left);first(p^.right);end;中序遍历proceduremiddle(p:point);beginifp=nilthenexit;middle(p^.left);writeln(p^.data);middle(p^.right);end;后序遍历procedurelast(p:point);beginifp=nilthenexit;last(p^.left);last(p^.right);writeln(p^.data);end;宽度遍历图论•有向图•无向图•连通图•带权图•图用Pascal实现与深度搜索(DFS)•宽度搜索(BFS)与迪杰斯特拉(Dijkstra)连通无向图图•邻接矩阵表示法•邻接表表示法•邻接矩阵优势：简单•邻接表优势：节省空间•DFS(DepthFirstSearch)邻接矩阵表示法邻接表表示法深度优先搜索图论(2)•BFS(BreadthFirstSearch)•Dijkstra宽度优先搜索DijkstraV1V2V3V4V5V6V70103040∞60∞∞∞50搜索与剪枝•走迷宫101000001111110101000100101011111001111100001110000010110111111111穷举与贪心•穷举（上）•穷举（下）•贪心算法介绍•部分背包问题•哈夫曼树穷举•在找不到解决问题的规律时对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从中找出那些符合要求的候选解作为问题的解。•穷举（1）•穷举（2）穷举(1)•求100以内所有素数programex(input,output);vari:integer;functionfac(n:integer):boolean;vari:integer;beginfori:=2totrunc(sqrt(n))doifnmodI=0thenexit(false);exit(true);end;beginfori:=2to100doiffac(i)thenwrite(I,’’);writeln();readln();end.穷举(1)•求1000以内所有水仙花数穷举(2)a:arrayofinteger;n:integer;fillchar(a,sizeof(a),1);repeati:=1;whilea[i]=11dobegina[i]:=1;inc(a[i+1]);inc(i);end;{执行的语句}inc(a[1]);untila[n+1]=2;N皇后问题•题目来源于国际象棋的玩法，因为皇后所在的位置可以纵向、横向、两个斜向四个方向的“捕捉”，所以8皇后问题就是要求如何布置8个皇后在8*8的棋盘上而使他们互相无法“捕捉”。也就是说不存在两个皇后同行或同列，或在同一斜线上。而N皇后问题就是如何布置N个皇后在N*N棋盘里使不存在两个皇后在同行同列和同一斜线上。因为8皇后问题可以归为N皇后问题，所以下面按照N皇后问题来进行讨论。N皇后问题算法（穷举）N皇后贪心算法•贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。贪心算法•局部最优导致全局最优•e.g.贪心算法缺点找出从第一层到最后一层的一条路径，使之的权值之和最大或最小。背包问题•部分背包问题——贪心•完全背包问题（0/1背包问题）——穷举/动态规划部分背包问题•给定一个最大载重量为M的卡车和N种食品，有食盐，白糖，大米等。已知第i种食品的最多拥有Wi公斤，其商品价值为Vi元/公斤，编程确定一个装货方案，使得装入卡车中的所有物品总价值最大。部分背包问题哈夫曼树•给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffmantree)。•建立哈夫曼树哈夫曼树应用•电码：传输数据越小越好•各字母使用次数：azefgnisxm521374810316动态规划•从贪心到动态规划•砍价问题（线性动归）•统计单词个数（区域动归）•数字三角形（树形动规）•0/1背包问题（背包动归）•动规与递归•习题：过河卒问题从贪心到动态规划•贪心缺点：•当局部最优不代表着全局最优时，贪心算法不能得到最优解。动态规划•动态规划(dynamicprogramming)是运筹学的一个分支，是求解决策过程(decisionprocess)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistepdecisionprocess)的优化问题时，提出了著名的最优化原理(principleofoptimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。动态规划动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。动态规划•多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。动态规划•重点：•记忆化（将时间转成内存）•e.g.•快速排序优于选择排序砍价问题（线性动归）步步高升（StepbyStep）问题描述：春节的时候TENSHI去逛花市。她来到一个卖盆竹的摊位，看到一盆叫做“步步高升”的盆竹。“步步高升，步步高升……”学习就是要一步一步来，不能急，要打好基础。在稳固的基础上才谈得上步步高升！TENSHI若有所思。她看到这盆东西好意头，于是想买下。谁知一问价钱，“不贵不贵，才2**RMB。”TENSHI差点没昏倒，囊中羞涩嘛。但是TENSHI还是很想买下来，于是她就在一旁观察。观察了一段时间，她发现这个卖盆竹的人和别人杀价很有规律。设此人第i次报价为Wi元，那么他第i+1次报的价格为Wi－A或Wi－B。到了最后，TENSHI以Z元成交，高高兴兴的回家去了。任务：求TENSHI把盆竹的价格由W元杀到Z元的方法总数。输入格式：输入文件第一行有两个正整数W，Z。第二行有两个正整数A和B。它们满足条件：10≤W≤106，1≤Z≤106，ZW2≤A、B≤10000，A≠B输出格式：将方法总数输出，只有一行。注意：结果不超过MAXLONGINT统计单词个数(区域动归)Description输入一串英文句子，统计该英文句子中英文单词的个数，并将单词个数输出。Input只有一行：一英文句子（单词分隔符中只有空格、逗号、冒号、句号）Output只有一行且只有一个正整数：句子中单词的个数SampleInputThisisabook.SampleOutput4Source数字三角形（树形动规）数字三角形0/1背包问题背包问题(Knapsackproblem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？它是在1978年由Merkel和Hellman提出的。例题数据•有五个物品，其重量分别是{2,2,6,5,4}，价值分别为{6,3,5,4,6}，背包容量为10，求装入背包的物品和获得最大价值。012345678910000000000000W1=2V1=61W2=2V2=32W3=6V3=53W4=5V4=44W5=4V5=650066666666006699999900669999990066999991300669912121515691414150/1背包动归与递归•e.g.•兔子数列（斐波那契数列，黄金分割数列，FibonacciSequence）•1,1,2,3,5,8,13,21,34,55,89,144,...•f(0)=1;f(1)=1;•f(n)=f(n-1)+f(n-2)（n=2，n∈N*）递归/动归程序functionfac(n:integer):integer;beginifn=1thenfac:=1;elsefac:=fac(n-1)+fac(n-2);end;sz[0]:=1;sz[1]:=1;fori:=2tondosz[i]:=sz[i-1]+sz[i-2];过河卒问题马拦过河卒问题内容：棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。棋盘用坐标表示，A点(0,0)、B点(n,m)(n,m为不超过13的整数)，同样马的位置坐标是需要给出的。要求计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。fori:=1to8doforj:=1to4doifsz[i,j]-1thensz[i,j]:=sz[i-1,j]+sz[i,j-1]e