下载

1下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 典型试题分析

典型试题分析.doc

典型试题分析

faint
2018-09-07 0人阅读 举报 0 0 暂无简介

简介:本文档为《典型试题分析doc》,可适用于工程科技领域

安阳一中信息学奥赛辅导资料资源分配问题解析题:机器分配(assignedpas)【问题描述】总公司拥有高效设备M台准备分给下属的N个分公司。各分公司若获得这些设备可以为国家提供一定的盈利。问:如何分配这M台设备才能使国家得到的盈利最大?求出最大盈利值。其中M≤N≤。分配原则:每个公司有权获得任意数目的设备但总台数不超过设备数M。输入数据文件格式为:第一行有两个数第一个数是分公司数N第二个数是设备台数M。接下来是一个N*M的矩阵表明了第I个公司分配J台机器的盈利。【输入样例】assignedin{个分公司分台机器}【输出样例】assignedout{最大盈利值为}{第一分公司分台}{第二分公司分台}{第三分公司分台}【算法分析】按照公司的顺序来分配机器即按照公司的顺序划分阶段第一个阶段把M台设备分给第一个公司记录下来获得的各个盈利值然后把M台设备分给前两个公司和第一个阶段比较记录下来更优的各个盈利值一直到第N个阶段把M台机器全部分给了N个公司就可以得到最优解下面来讨论两个阶段之间的关系设数组FI,J表示前I个公司分配J台机器的最大盈利数组FI,K表示前I个公司分配K台机器的最大盈利(≤I≤N,≤J≤M,≤K≤J),,用ValvuI,J表示第I个公司分配J台机器的盈利,则FI,J可以由下面的式子中取最大值获得:FI,ValueI,J{前I公司分配台机器最大盈利第I个公司分配J台的机器的盈利}FI,ValueI,J{前I公司分配台机器最大盈利第I个公司分配J台的机器的盈利}FI,ValueI,J{前I公司分配台机器最大盈利第I个公司分配J台的机器的盈利}FI,JValueI,{前I公司J分配台机器最大盈利第I个公司分配台的机器的盈利}FI,JValueI,{前I公司分配J台机器最大盈利第I个公司分配台的机器的盈利}在这里用机器数用做每个阶段的状态由于ValueI,J的值为定值要使前面每个式子的值最大就必须使第i阶段的各个状态的值最大阶段i的状态只能由阶段i中的状态通过状态转移方程求得与其他状态没有关系。由此可见该问题具备了最优子结构和无后效性原则适宜使用动态程序设计方法求解。状态转移方程为:FI,J=MAX{FI,KValueI,JK}(≤I≤N,≤J≤M,≤K≤J)初始值:F,=Fn,m的值即为所求最大盈利值。【参考程序】programdissignedvarm,n:integerI,j,k,max:longintF,value:array,oflongintprocedureshow(i,j:longint){输出各分公司分配情况}vark:longintbeginifi=thenexitfork:=tojdoifmax=fi,kvaluei,jkthenbeginmax:=fi,kshow(i,k)writeln(i,'',jk)exitendendBEGINassign(input,'assignedin')reset(input)assign(output,'assignedout')rewrite(output)readln(n,m)forI:=tondoforj:=tomdoread(valuei,j)fori:=tondoforj:=tomdobeginmax:=fork:=tojdoiffi,kvaluei,jk>maxthenmax:=fi,kvaluei,jkfi,j:=maxendwriteln(fn,m){输出最大盈利值}show(n,m)close(input)close(output){输出分配情况}END题:马棚问题(stablepas)【问题描述】每天小明和他的马外出然后他们一边跑一边玩耍。当他们结束的时候必须带所有的马返回马棚小明有K个马棚。他把他的马排成一排然后跟随它走向马棚因为它们非常疲劳小明不想让他的马做过多移动。因此他想了一个方法:将马按照顺序放在马棚中后面的马放的马棚的序号不会大于前面的马放的马棚序号。而且他不想他的K个马棚中任何一个空置也不想任何一匹马在外面。已知共有黑、白两种马而且它们相处的并不十分融洽。如果有I个白马和J个黑马在一个马棚中那么这个马棚的不愉快系数将是i*j。所有K个马棚的不愉快系数的和就是系数总和。确定一种方法把n匹马放入k个马棚使得系数总和最小。【输入格式】stablein在第一行有两个数字:N(〈=N〈=〉和K(〈=K〈=N〉。在接下来N行是N个数。在这些行中的第I行代表队列中的第I匹马的颜色:意味着马是黑色意味着马是白色。【输出格式】stableout只输出一个单一的数字代表系数总和可能达到的最小值。【输入样例】 {6匹马3个马棚}{第1匹马为黑马}{第3匹马为白马}【输出样例】{最小系数总和}【算法分析】从样例上看首先把两匹马放在第一个马棚这个马棚的不愉快系数为接下来把匹马放在第个马棚这个马棚的不愉快系数为(两匹白马匹黑马)最后一个放在第三个马棚这个马棚的不愉快系数为可得到最小系数总和为。一看此题有人可能会想到搜索按马棚的顺序枚举每个马棚放马的个数求最小的系数总和。这个算法的正确性是没有问题的问题是当数据量比较大时程序很难在秒内出解。究其原因是搜索时会遇到大量的重复子问题。于是我们想到了用动态规划。顺着搜索法的思路可以以马棚划分阶段。于是得到了状态表示:fi,j表示前i个马棚放入j匹马所能达到的最小系数总和值。然后便有了状态转移方程:f,j=x,j{第个马棚放前j匹马的最小系数总和等于第匹马到第J匹马放到第个马棚时得到的不愉快系数}fi,j=min{fi,uxu,j}(<i<=u<j){前i个马棚放前j匹马的最小系数总和等于第匹马到第u匹马放到前i个马棚时得到的系数总和值加上第u匹马到第j匹马放到一个马棚的不愉快系数的值取最小}xi,j为将第i匹马到第j匹马放到一个马棚时得到的不愉快系数。则fk,n即为所求的解。算法空间复杂度为O(n^)因为每一阶段的结果只与上一个阶段有关因此可以用滚动数组。即用fa代替fI,fb代替fI计算过程中不断用fb的值更新fa再用fa的值推出fb。空间复杂度降为O(n)。为了减少算法时间复杂度减少重复计算:在计算xI,j时没有必要用一个itoj的循环而是可以直接由xI,j或xI,j推出。优化后算法时间复杂度为O(k*n^)这是可以在秒之内算出结果的。【参考程序】programstableconstmaxn=varc:arraymaxnofshortintfa,fb:arraymaxnoflongint  {为了减低空间复杂度用两个一位数组做滚动数组}n,k,i,j,u::integerx:arrayoflongintbeginreadln(n,k)     {n匹马k个马棚}fori:=tondoreadln(ci)     {读入第i匹马的颜色}fillchar(x,sizeof(x),)fori:=tondobegininc(xci)    {累加前i匹马两种颜色的个数白色个数存在x中黑色个数存在x中} fai:=x*x      {计算前i匹马放到一个马棚时的不愉快系数}endfori:=tokdobeginfillchar(fb,sizeof(fb),)      {数组初始化为}forj:=itondo     {从第i匹马到第n匹马}beginfbj:=faj      {fb数组首先继承前j匹马放到马棚的最小系数总和值}fillchar(x,sizeof(x),)     {数组初始化为}foru:=jdowntoido    {从第j匹马倒推到第i匹马}begininc(xcu)     {累加第u匹马到第j匹马两种颜色的个数}iffaux*x<fbjthen 如果前u匹马放到马棚的最小系数总和值加上第u匹马到第j匹马放到一个马棚的不愉快系数小于前j匹马放到马棚的最小系数总和值则更新据}fbj:=faux*x      {更新数据}endendfa:=fb    {当前阶段完成后把当前阶段得到的最优值保存在fa数组中     再进行下一个阶段的推导fa数组和fb数组在此起滚动数组的作用}endifk=thenwriteln(fan)    {输出结果时讨论只有一个马棚时的情况和非一个马棚时的情况}elsewriteln(fbn)end题、花店橱窗布置问题(FLOWERPAS)【问题描述】假设你想以最美观的方式布置花店的橱窗。现在你有F束不同品种的花束同时你也有至少同样数量的花瓶被按顺序摆成一行。这些花瓶的位置固定于架子上并从至V顺序编号V是花瓶的数目从左至右排列则最左边的是花瓶最右边的是花瓶V。花束可以移动并且每束花用至F间的整数唯一标识。标识花束的整数决定了花束在花瓶中的顺序如果I<J则令花束I必须放在花束J左边的花瓶中。例如假设一束杜鹃花的标识数为一束秋海棠的标识数为一束康乃馨的标识数为所有的花束在放入花瓶时必须保持其标识数的顺序即:杜鹃花必须放在秋海棠左边的花瓶中秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目。则多余的花瓶必须空置且每个花瓶中只能放一束花。每一个花瓶都具有各自的特点。因此当各个花瓶中放入不同的花束时会产生不同的美学效果并以美学值(一个整数)来表示空置花瓶的美学值为零。在上述例子中花瓶与花束的不同搭配所具有的美学值如下表所示。花瓶花束(杜鹃花)(秋海棠)(康乃馨)例如根据上表杜鹃花放在花瓶中会显得非常好看但若放在花瓶中则显得十分难看。为取得最佳美学效果你必须在保持花束顺序的前提下使花束的摆放取得最大的美学值。如果有不止一种的摆放方式具有最大的美学值则其中任何一直摆放方式都可以接受但你只要输出任意一种摆放方式。、假设条件≤F≤其中F为花束的数量花束编号从至F。F≤V≤其中V是花瓶的数量。≤Aij≤其中Aij是花束i在花瓶j中的美学值。、输入输入文件是flowerin。第一行包含两个数:FV。随后的F行中每行包含V个整数Aij即为输入文件中第(i)行中的第j个数。、输出输出文件必须是名为flowerout的正文文件文件应包含两行:第一行是程序所产生摆放方式的美学值。第二行必须用F个数表示摆放方式即该行的第K个数表示花束K所在的花瓶的编号。、例子flowerin:––flowerout:【解法一】【算法分析】问题实际就是给定F束花和V个花瓶以及各束花放到不同花瓶中的美学值要求你找出一种摆放的方案使得在满足编号小的花放进编号小的花瓶中的条件下美学值达到最大。将问题进行转化找出问题的原型。首先看一下上述题目的样例数据表格。将摆放方案的要求用表格表现出来则摆放方案需要满足:每行选且只选一个数(花瓶)摆放方案的相邻两行中下面一行的花瓶编号要大于上面一行的花瓶编号两个条件。这时可将问题转化为:给定一个数字表格要求编程计算从顶行至底行的一条路径使得这条路径所经过的数字总和最大(要求每行选且仅选一个数字)。同时路径中相邻两行的数字必须保证下一行数字的列数大于上一行数字的列数。看到经过转化后的问题发现问题与“数学三角形”问题十分相似数字三角形问题的题意是:给定一个数字三角形要求编程计算从顶至底的一条路径使得路径所经过的数字总和最大(要求每行选且仅选一个数字)。同时路径中相邻两行的数字必须保证下一行数字的列数与上一行数字的列数相等或者等于上一行数字的列数加。上例中已经知道:数字三角形中的经过数字之和最大的最佳路径路径的每个中间点到最底层的路径必然也是最优的可以用动态规划方法求解对于“花店橱窗布置”问题经过转化后也可采取同样的方法得出本题同样符合最优性原理。因此可以对此题采用动态规划的方法。【参考程序】programpvara:array,ofinteger{Ai,j花束i放在花瓶j中的美学值}b:array,ofinteger{Bi,j前i束花放在前j个花瓶中的最优解}c:array,ofinteger{Ci,j在Bi,j的最优解中花束i的位置}d:arrayofintegerf,v:integer{花束和花瓶的数目}i,j,k,max:integerbeginassign(input,'flowerin')assign(output,'flowerout')reset(input)rewrite(output)readln(f,v)fori:=tofdoforj:=tovdoread(ai,j)fori:=tovfdob,i:=a,ifori:=tofdoforj:=itovfidofork:=itojdo{枚举花束i的位置}ifbi,kai,j>bi,jthenbeginbi,j:=bi,kai,j{更新当前最优解}ci,j:=kendmax:=fori:=ftovdoifbf,i>maxthenbeginmax:=bf,i{选择全局最优解}k:=i{k最后一束花的位置}endwriteln(max){打印最优解}fori:=tofdobegindi:=kk:=cfi,kendfori:=fdowntodowrite(di,'')writeln(d)close(input)close(output)end由此可看出对于看似复杂的问题通过转化就可变成简单的经典的动态规划问题。在问题原型的基础上通过分析新问题与原问题的不同之处修改状态转移方程改变问题状态的描述和表示方式就会降低问题规划和实现的难度提高算法的效率。由此可见动态规划问题中具体的规划方法将直接决定解决问题的难易程度和算法的时间与空间效率而注意在具体的规划过程中的灵活性和技巧性将是动态规划方法提出的更高要求。【解法二】【算法分析】flower一题是IOI第一天第一题该题如用组合的方法处理将会造成超时。正确的方法是用动态规划考虑角度为一束一束地增加花束假设用b(i,j)表示~i束花放在到j之间的花瓶中的最大美学值其中i<=j则b(i,j)=max(bi,kAi,k)其中i<=k<=jA(i,k)的含义参见题目。输出结果时显然使得bF,k取得总的最大美观值的第一个k值就是第F束花应该摆放的花瓶位置将总的最大美观值减去Ai,k的值即得到前k束花放在前k个瓶中的最大美观值依次使用同样的方法就可求出每一束花应该摆放的花瓶号。由于这一过程是倒推出来的所以程序中用递归程序来实现。【参考程序】programflowervara,b:array,ofintegerf,v,i,j,k,c,d,m:integerprocedureprint(i,j:integer)varn:integerbeginifi>thenbeginn:=iwhileai,n<>jdon:=nprint(i,jbi,n)write(n,'')endendbeginassign(input,'flowerin')assign(output,'flowerout')reset(input)rewrite(output)readln(f,v)fori:=tofdoforj:=tovdoread(bi,j)c:=b,fori:=tovdoifc<b,ithenbegina,i:=b,ic:=b,iendelsea,i:=cfori:=tofdoforj:=itovfidobeginc:=maxintfork:=itojdobegind:=maxintform:=ktojdoifbi,m>dthend:=bi,mifdai,k>cthenc:=dai,kendai,j:=cendc:=maxintfori:=ftovdoifaf,i>cthenc:=af,iwriteln(c)print(f,c)close(input)close(output)end第页共页

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/7

典型试题分析

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利