简单算法.ppt
《简单算法.ppt》由会员分享,可在线阅读,更多相关《简单算法.ppt(73页珍藏版)》请在三一办公上搜索。
1、ACM/ICPC程序设计,简单算法计算机学院 张淑平,模拟算法及题目枚举算法及题目贪心算法及题目综合实例,一个简单的模拟题,题目(zju1708:Robot Motion)以矩阵形式给定一张地图和机器人的初始位置。矩阵上每一点的字母代表在这一点机器人的移动方向。如果机器人按图中信息能走出的话输出需要的步数。如果机器人进入某个循环则输出循环前所走的步数和循环的长度。,Sample input and output:,Sample Input 3 6 5NEESWEWWWESSSNWWWW4 5 1SESWEEESNWNWEENEWSEN0 0 0,Sample Output 10 step(s)
2、to exit3 step(s)before a loop of 8 step(s),问题分析,我们有什么信息?地图,起点我们要什么?移动结束(走出边界或遇到以前走过的点)时,该次移动的序号。(如果是遇到以前走过的点,还需知道该点的序号)设计数据结构主要信息:int data100100;/存放地图int place;/当前序号int m,n;/矩阵大小int begin;/起始位置,方法:按照地图及初态移动机器人直到满足结束条件:下一个要经过的点(row,line)满足(row=m|line=n)或 datarowline 0.用place+标记刚走过的点。如果走出地图输出:place 1
3、step(s)to exit。否则输出:datarowline-1 step(s)before a loop of place-datarow line step(s),运行演示,运行演示,运行演示,运行演示,满足结束条件:col 0输出:10 step(s)to exit,同理Grid2结束状态为:,Robot Motion 程序,#include using namespace std;int data100100;/地图int place;/当前位置int m,n,begin;/地图大小,初始位置void move(int row,int col);/按要求移动机器人int main()
4、return 0;,Robot Motion 程序(续),int main()char ch;while(cinmnbegin)/end of main,Robot Motion 程序(续),void move(int row,int col)bool notExit=true;while(notExit/end of move,结论:一个简洁高效的算法在很大程度上依赖于数据结构的建立。这也往往是做好一个模拟题的重点。,枚举算法及举例,核心思想:通过列举所有情况然后逐一判断,从而得到结果。从本质上看,就是把问题用一定的数据结构描述,然后用某种方式遍历它,以寻求问题的解。,一个简单的例子,Zer
5、o Sum(USACO 36)问题描述:给定一个整数N(3=N=9)。在序列1N中插入,构造表达式。按字典序输出所有使得表达式为0的情况。,问题分析,在1.N中插入,一共有多少中插法?考虑最坏情况N9 时,有 38 6561 种情况 这个解空间比较小,这就意味着我们可以列举所有情况看它是否满足“使得表达式为0”,选择变量:string digital=11223344556677889;int n;思路:输入n后把digital中2*n 1 后剔除,并在奇数位置按字典序枚举各种插入情况。对每种情况如果表达式值为0,则输出之。,Zero Sum 的枚举法实现,#include#include#i
6、nclude using namespace std;ifstream fin(zerosum.in);Ofstream fout(zerosum.out);string digital=11223344556677889;int n;/问题规模int check();/检查表达式是否为0void proc(int t);/确定第t处应插入什么字符int main()finn;/输入问题规模digital.resize(2*n-1);/剔除2*n-1后边的元素proc(0);return 0;,Zero Sum 的枚举法实现,void proc(int t)if(t=n-1)/已经插入完毕 i
7、f(check()=0)/如果和为0则输出 foutdigitalendl;return;/确定要插入字母在digital中的位置int i=2*t+1;digitali=;/插入(依字母序)proc(t+1);/在下一个位置插入digitali=+;proc(t+1);digitali=-;proc(t+1);,Zero Sum 的枚举法实现,int check()/*去处插入字符后digital中的,并存入teamp中*/string teamp;for(int i=0;i*/istringstream ssin(teamp);,int sum;ssin sum;char ch;while
8、(ssinch)int t;ssint;if(ch=-)sum-=t;else sum+=t;return sum;,枚举的特点,枚举的特点简明但低效 只要有合适的搜索规则,就能设计出枚举算法,就可以解决几乎所有的问题。这是一种普遍适用的解题策略。枚举算法的普遍性换来的代价是低效,由于它要考虑所有可能的情况,如果问题的规模很大,情况很多,算法难免耗时过长。如果对算法进行优化,精简枚举范围,就有可能在可接受的时间内得出结果。,重点提示,虽然枚举在理论上可以解决绝大部分优化问题,然而当问题规模较大时其速度是相当差的。然而枚举法的用处比我们想象的要大。在问题毫无头绪的情况下,枚举往往可以为我们打开一
9、个缺口。,贪心算法及应用,贪心法的基本思想是每次选择一个局部最优策略来实施,而不考虑对今后的影响,一般来说,其时间复杂度较低。对很多题目,用贪心法并不能得到最优解,该方法的另一个难点是比较难以证明其最优性。但是,如果能证明当前策略至少不比其他策略差,就可以继续做下去。,贪心法的基本要素,贪心选择性质所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。最优子结构性质当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。,Mixing Milk(usaco76),问题描述 某商人欲从M个农民那里购买N公斤牛奶。给定整数M,N及若干个农民拥有牛奶的价格和总量。问他最少
10、需要多少钱可以购买N公斤牛奶。INPUT FORMATLine 1:Two integers,N and M.The first value,N,(0=N=2,000,000)is the amount of milk that Merry Milk Makers want per day.The second,M,(0=M=5,000)is the number of farmers that they may buy from.Lines 2 through M+1:The next M lines each contain two integers,Pi and Ai.Pi(0=Pi=1
11、,000)is price in cents that farmer i charges.Ai(0=Ai=2,000,000)is the amount of milk that farmer i can sell to Merry Milk Makers per day.,Sample Input 100 5 5 20 9 40 3 10 8 80 6 30 Output 630,问题分析,用贪心法的关键是找到最优的度量标准既然本题要求花钱最小,我们就可以选择牛奶的价格为度量标准。思考:该问题的最优子结构性质和贪心选择性质?,解题方法:对每个农民按其牛奶价格进行排序,每次选择价格最低的。如果
12、还没有买够就向该农民购买。,Mixing Milk 实例,问题:N 100,M 5,price 5,9,3,8,6,num=20,40,10,80,30,20公斤,30公斤,40公斤,实现代码,#include#include#includeusing namespace std;ifstream fin(milk.in);ofstream fout(milk.out);struct IntPairIntPair(int a=0,int b=0)first=a,second=b;int first,second;,/比较谓词bool small(IntPair i1,IntPair i2)re
13、turn i1.first,实现代码续,int cost(vector/end of cost,贪心算法的抽象化控制机制,Procedure GREEDY(A,n)solution NULLfor i 1 to n dox select(A)if feasible(solution,x)then solution UNION(solution,x)endifrepeatEnd GREEDY,枚举贪心,“在问题毫无头绪的情况下,枚举往往可以为我们打开一个缺口,使得其他算法可以成功。”下面看一个例子:,Extended Lights Out(zju 1354),有一个5行6列的按钮阵列,每个按钮有
14、一盏灯,当它被按下,它和它相邻四个(上下左右)的灯状态改变一次(亮-灭 或灭-亮)现在给出了这个阵列的初始亮灭状态,找一种操作让灯全灭。,分析,显然按键是顺序无关的,而且最多按一次(按两次相当于不按)。最直接的想法:30个按键,每个有两种操作选择,总共要枚举230 1073741824种方案。本题时限1秒,此方法行不通。,进一步分析,考虑如图所示的操作:,点击第2行第2列,进一步分析,考虑如图所示的操作:,X,X,点击第2行第2列,点击第2行第3列,进一步分析,考虑如图所示的操作:,X,X,X,点击第2行第2列点击第2行第3列,点击第2行第5列,X,X,X,进一步分析,考虑如图所示的操作:,点
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 简单 算法
链接地址:https://www.31ppt.com/p-5332695.html