9只钟表排成33的方阵_第1页
9只钟表排成33的方阵_第2页
9只钟表排成33的方阵_第3页
9只钟表排成33的方阵_第4页
9只钟表排成33的方阵_第5页
已阅读5页，还剩6页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、The ClocksIOI94,Day 1,Problem 2贾晔 July 5,20031The Clocks9只钟表排成3*3的方阵，每只钟表只能指向上、下、左、右四个位置9种作用方式，每种使一些钟表的指针右转90使用这9种作用，使得所有钟表都指向正上方 (记为状态0)求使得总作用次数最少的策略2Sample3Input Data3*3矩阵，元素为0，1，2或3，分别表示钟表指向上，右，下，左3 3 02 2 22 1 24钟表矩阵的有限性由于矩阵结构及其元素取值范围相当有限，故可能出现的钟表矩阵也是很有限的，即49=262144种由此有限性可以考虑搜索解法5广度优先搜索从状态0开始搜索搜

2、索过程：标记可以通过一次作用达到此状态的所有状态为已搜索，然后搜索新标记的状态。搜索过程中保存使用的作用方式每个状态用一个32位整数的低18位表示,可将结果存在长度为262144的数组中6广度优先搜索1291557启发广度优先搜索的可行意味着作用次数的相当有限注意到作用的结果与作用的顺序无关，则显然每种作用最多只需使用3次于是，问题简化为求解同余方程组8同余方程组把钟表和作用分别从1到9标号，则同余方程组可写为C(i) +E(i,j) * M (j) mod 4= 0 (i=1.9)其中C(i),M(j),E(i,j)分别表示第i个钟表的初始状态，第j种作用的次数，第j种作用是否拨动第i个钟表9同余方程组写成矩阵的形式 ( C + E M ) mod 4 = 0 (*) 我们所求为M的最小非负解M0=M mod 4显然，当k足够大时，方程 C + E M = 4 * k 的解也是 (*) 式的解，故 M0 =M mod 410同余方程组由于E是与输入无关的系数矩阵，所以我们可以事先求出其逆矩阵E ，则M 可以写成 M =( E ( 4 * k C ) ) mod 4这样，我

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论