冬令营解题报告猜数guess_第1页
冬令营解题报告猜数guess_第2页
冬令营解题报告猜数guess_第3页
全文预览已结束

下载本文档

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

文档简介

1、猜数解题浙江问题简述本题是一个交互式的题目，会有重复的数字。的目标是猜若干个长度为 Len 的数，并且保证这个数不可以与库进行交互，每次可以猜一个各位不同的数，库会将猜的数与进行比较，并以整数 P 和整数 Q 来回答，其中 P 表示所猜的数字和位置都是对的数的个数，Q表示不管位置对还是不对，所猜的数字与被猜的数字有几个数字是相同的。的目标就是用最少的次数猜出设定的。题目中给出了 10 个测试点的信息：算法分析这个问题在冬令营师的课上已经有了相当详细的，那么这里直接师课上的成果。算法即为筛法。假设要猜的数的长度为 Len，则有测试点12345678910Len234567891010被猜数的数目

2、100100100100100202020120可以发现，仅仅随机猜数就可以得到 95100 的高分。二、估价函数法的目标是使得猜了这个数之后候选的规模收敛的尽量快。用函数猜测次数1532521543587666220得分情况9109109109109101010101010将 Y 附值给 X。通过若干次调整，就可以得到一个 P = Len 的 X，也就是直接这么做需要猜的次数相当大，这里有两个优化：了。优化一：针对第一步：如果位置 p 上的数字 Xp换成了 k 之后得到的 Q，如果满足 Q = Q + 1，则 Xp必然不出现在中，而 k 必然出现在中。同样，如果满足 Q = Q 1，则 Xp

3、必然在中，而 k 肯定不在。这样一来就可以得到一些信息，以后随机位置的时候就不需要选择位置 k 了，随机数字也不用去随机那些被确定为肯定不在中的数字，这样便减少了猜测次数。优化二：针对第二步：跟优化一是一样的，就是把那些能确定的位置就确定下来。不妨设当前交换了 i 位置和 j 位置后得到 P。如果 P = P + 2，那么交换后 i 位置和 j 位置上的数字都与吻合；同样，如果 P = P 2，则交换前的i 位置和 j 位置都与吻合。其中的原因是显而易见的。这样就确定了 i 位置和 j 位置，以后就不需要选择这些位置了，也减少了猜测次数。本算法时间复杂度不好估计，但经测试，实际运行速度相当快。小结筛选，是解决问题的一种。在本题中，应用这一，不断将候选的规模缩小，从而猜得目标。对问题进行拓

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

温馨提示

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

最新文档

评论

0/150

提交评论