- 1、本文档共30页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
蓝桥杯 计算机学院 王燕 格子刷油漆(递归算法、动态规划) 网络寻路(构图、递归算法、度的计算) 大臣的旅费(最短路径、深度优先遍历) 城市建设(构图,最小生成树) 幸运数(筛除) 历届试题 算法分析 格子刷油漆 PREV-15 问题描述: X国的一段古城墙的顶端可以看成 2*N个格子组成的矩形,现需要把这些格子刷上保护漆。 a c e b d f 城墙宽度总是2格,长度未知,此时为3 可以从任意一个格子刷起,刷完一格, 可以移动到和它相邻的格子(对角相邻也算数) 不能移动到较远的格子(因为油漆未干不能踩) a d b c e f 就是合格的刷漆顺序。 c e f d a b 是另一种合适的方案。 当已知 N 时,求总的方案数。当N较大时,结果会迅速增大,请把结果对 1000000007 (十亿零七) 取模 算法分析: 两个动态规划数组 a c e b d f a[i]:在2i的格子下,从最边缘一列的一个角 的格子出发,遍历全部的种数 b[i]:在2i的格子下,从一个角的格子出发, 遍历全部回到相对的格子 说明:相对的格子,a相对的是b,b相对的是a c相对的是d,d相对的是c 计算a:出发点在角上,有3种可能 先去相对的格子,再往下一列 先遍历其余格子,再回到相对的位置 经第二列转折,到第三列的一个角进行遍历 a[i]= 2*a[i-1] + b[i] + 4*a[i-2] 计算b:考虑到回来的路径,因此除出发点外,每一列只能有2种选择 b[i] = 2*b[i-1] 求总和: sum = 4a[n] i-1 i n-i 四个角 从2~n-1列所有中间的走法 sum += 2*( 2*b[i-1]*2*a[n-i] + 2*b[n-i]*2*a[i-1]) 先遍历左边部分 先遍历右边部分 初值: a[1]=1 a[2]=6 abcd, abdc acbd, acdb adbc, adcb b[1]=1 a c b d 算法代码: ………… int main() { ………… for(i=2;i=n;i++) b[i]=(2*b[i-1])%NUM; for(i=3;i=n;i++) a[i]=(2*a[i-1]+b[i]+4*a[i-2])%NUM; sum = (4*a[n])%NUM; for(i=2;i=n;i++) { sum+=(8*b[i-1]*a[n-i])%NUM+(8*b[n-i]*a[i-1])%NUM; sum %= NUM; } ………… } 网络寻路 PREV-13 问题描述: X 国的一个网络使用若干条线路连接若干个节点。节点间的通信是双向的。某重要数据包,为了安全起见,必须恰好被转发两次到达目的地。该包可能在任意一个节点产生,我们需要知道该网络中一共有多少种不同的转发路径。 1.源地址和目标地址可以相同, 2.中间节点必须不同。 算法分析: 1 2 3 4 5 1 2 1 - 2 - 1 - 2 - 1 - 2 - 3 - 3 - 3 - 3 4 5 2 - 1 - 2 - 1 - 2 - 1 - 3 - 4 - 5 - 3 3 3 注意:输入数据保证任意两点最多只有一条边连接,并且没有自己连自己的边,即不存在重边和自环 算法分析: 1 2 3 4 5 1 2 若存在边(v1,v2),当度1的情况下,经过v1-v2,和v2-v1的路径有: (degree[v1] – 1) *(degree[v2] – 1) *2 算法代码: ………… int main() { ………… for(i=1;i=arcnum;i++) { int d1,d2,v1,v2; v1=arcs[i].start; v2=arcs[i].end; d1=degree[v1]; d2=degree[v2]; if( d1 1 d21) sum += (d1-1)*(d2-1)*2; } ………… } 大臣的旅费 PREV-9 问题描述: 很久以前,T王国空前繁荣。为了更好地管理国家,王国修建了大量的快速路,用于连接首都和王国内的各大城市。为节省经费,T国的大臣们经过思考,制定了一套优秀的修建方案,使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时,如果不重复经过大城市,从首都到达每个大城市的方案都是唯一的。J是T国重要大臣,他巡查于各大城市之间,体察民情。所以,从一个城市马不停蹄地到另一个城市成了J
文档评论(0)