晴神机试技巧讲解浓缩版.pdf-资料库

069bdf16-9fe5-4f2e-a658-a41d9fae5591.pdf-第1页.png

第1页 / 共12页

069bdf16-9fe5-4f2e-a658-a41d9fae5591.pdf-第2页.png

第2页 / 共12页

069bdf16-9fe5-4f2e-a658-a41d9fae5591.pdf-第3页.png

第3页 / 共12页

069bdf16-9fe5-4f2e-a658-a41d9fae5591.pdf-第4页.png

第4页 / 共12页

069bdf16-9fe5-4f2e-a658-a41d9fae5591.pdf-第5页.png

第5页 / 共12页

069bdf16-9fe5-4f2e-a658-a41d9fae5591.pdf-第6页.png

第6页 / 共12页

069bdf16-9fe5-4f2e-a658-a41d9fae5591.pdf-第7页.png

第7页 / 共12页

069bdf16-9fe5-4f2e-a658-a41d9fae5591.pdf-第8页.png

第8页 / 共12页

今天主要讲一下两个东西 1. 怎么在 PAT 上判断段错误在代码中的大概位置 2. 怎样把 PAT 的数据测出来先来第一个当我们提交代码的时候。。经常会返回段错误，但是苦于不知道 PAT 的数据，所以不知道怎么测，事实上我们可以直接在 PAT 上大致锁定段错误的范围。。其实原理很简单，由于 PAT 在碰到段错误的地方就直接返回段错误，不会让程序运行完，所以我们只要在适当的位置插上 while(1); 然后提交。。就可以根据是否超时来判断段错误的位置是在 while(1)之前还是之后。。根据若干次 while(1)位置的测试。。就可以夹出段错误的代码块是哪一段，然后。。根据经验以及常识。。去思考这一小段代码中什么样的数据会出现了段错误。。以此锁定具体位置。。我们。。来举个例子 http://paste.ubuntu.com/15267367/ 上面是 PAT A1025 的代码，下面是这道题的地址 http://www.patest.cn/contests/pat-a-practise/1025 这个代码是昨天有同学问我的。。大家可以测试提交一下。。一定会有三个 case 返回段错误。。首先。。我们可以使用类似二分的方法，在主函数的一半位置左右插入 while(1); 比如我在 39 行插入了 while(1) 我主要想测试一下是不是由于下面的 sort 或者是更下面的代码引起的。。提交之后还是三个段错误。。按一下键盘的删除键，可以回退到上一页面此时代码框里的代码仍然是保存状态，刚才那里仍然返回三个段错误，说明段错误的位置在 while(1)之前，否则就应该返回超时。接下来我们把 while(1)放到 32 行

然后提交结果还是会发现三个段错误= =说明段错误的位置还要再上面。。然后我们就会看到上面是一大段 for。。提交。。先把 while(1)放到这个 for 之前，第 18 行所有 case 都会返回运行超时。。好了。。看样子夹出来了，引起段错误的位置就是在这个 for 里面还没完。。接下来我需要思考，是 for 循环的第一层就出问题了。。还是在 i 到某个数字时出了问题呢，于是我们在这个 for 内部的最下面加了 while(1)，第 31 行

提交。。发现段错误。。说明当我们 i = 0 的时候，也就是第一层循环就发生了段错误。。接下来又可以在这个 for 块中定位位置。。比如我放到了 25 行。。提交。。返回运行超时。。说明段错误的位置在它下面

放到 27 行。。发现运行超时，由于 for 下面我们之前已经放过了。。所以可以得出结论。。段错误的位置就在这么一小段 for 里面。。在这里面。。有一个 if 跟一个 else，我们可以把 while(1)加到 if 跟 else 的执行语句里面。。比如我把 while(1)放到了 if 里面，发生了段错误。。调整了一下 while(1)的位置。。然后就超时了。。这说明段错误发生在这一句。。那么。。为什么第一层循环的时候这一行会发生段错误呢。。想到第一层时 i = 0，而段错误很大可能都是由于数组越界引起的。。然后很容易就可以看到这里面有一个 stu[i - 1]。。于是 i - 1 就是-1，导致数组下标越界。。于是错误就定位出来了。。接下来怎么改就看你自己的了。。第一部分结束。。补充一下第一部分如果不是 i = 0 的时候段错误的话，你可以加一个 if(i > 100) while(1) 这个 100 根据自己喜欢来定。。一半是选择 for 范围的一半，然后进行二分。。基本就可以定位出 i 是什么的时候段错误。这个二分跟第二部分有点关系，等下就能明白了再补充一下 sort 的 cmp 函数 bool cmp(int a, int b) { if(a != b) retur a < b; }

比如这个简单的 cmp，没有处理 a 和 b 相等的情况，这个时候，一旦数据中存在 a 和 b 相等的情况，就会直接段错误，这是由 sort 内部实现决定的接下来是第二部分这部分主要讲一下怎样把 PAT 的数据测出来。。一个 case 里面的数据个数越少越好，这里主要讲原理，测数据的原理是这样的，对某一个要测的数据是整数，，题目一定会给出它的范围，比如题目给了一个数 n，范围是 0 到 100，那么我就在输入这个数之后，加这么一句。。 if(n < 50) while(1); 这样，如果这个数小于 50，就会超时。。否则就会答案错误。。如果超时，说明这个数在这个范围里，那么我们接着考虑 25 的情况把这个句子改成 if(n < 25) while(1); 假设这里返回了答案错误。。说明 n 应该是在 25 到 49 这个范围里。。继续二分。。比如 35（不需要太精确计算一半是多少。。） if(n < 35) while(1); 反正就这样。。最后就能把 n 夹出来。。用二分的方法。。最后为了保险，可以再加一个 if(n == 30) while(1); 如果超时，说明 n 就是 30，由于二分的时间复杂度是 O(logn)所以范围 1000 我们也只需要 10 次左右就能得到结果。。这就是二分测数据的主要原理。。看一个例子。。 http://www.patest.cn/contests/pat-a-practise/1049 这道 Counting Ones，考场上不会做的时候。。应该怎么做。。首先，小数据的暴力程序你必须能写。。接下来。。这道题只需要输入一个 n，范围有点大。。2^30，我们可能需要 30 次才能测出来= =不过无所谓了。。回车键回退网页，然后稍微改一下提交。。这个范围的数字基本上几分钟就能测出来。。不演示了。。假如我们测出了某个之前超时的数据。。这里忘了一点。。这个题原先就是超时那我们就不用 while(1)了我们改一下。。 if(n < ...) while(1); return 0; 这样就可以了。。while(1)后面直接 return 0。。然后就能二分出 n 是多少了 = = 接下来。。我们在本地。。也就是自己的机子上跑一下这个 n，由于 n 有 10^9 大小，所以这题应该几十分钟能跑得出来，PAT 有三个小时。。所以没事在得到了 n 对应的答案之后，就可以特判输出了。。 if(n == 1000000000) printf("900000001"); 其他部分照常算就行了。。如果有多个 case 是大数据。。那本地开多个来跑就是了= =电脑应该是多核的应该没啥问题= =，后台有小伙伴发来信息。。让大家注意，尽量先跑分值比较

大的那些数据，因为 1 分的数据会比较边界，性价比不高，那么显然，这种做法比较适合数据个数比较少的情况 http://www.patest.cn/contests/pat-a-practise/1018 那么。。像这种，就需要测比较多的时间，但是我还真就测了一下这题的一个坑死无数人的数据。。应该在书上了。。不记得我改动过没有，反正就是那种类型，花了比较长的时间，半个小时好像，时间不充裕要慎用。。但是啊= = 这种做法还有一个用法。。就是我那年，我把分数从 90+骗到 100 的做法。。注意我没有测出完整数据。。 http://www.patest.cn/contests/pat-a-practise/1078 其他 ACD 三题我很快就一次 AC 了，这题卡了很久，当时记不清平方探测模的是啥了，处于一种不确定的状态，接着这个题总共有 4 个 case case0、2、3 能过，case1 一直答案错误，然后我就测了一下 case1 的数据。。由于数据比较小，所以比较快就测出来了。。然后我研究了一下这个数据。。知道怎么改了。。改完提交发现 case1 对了，case3 错了= = 其中一种写法，导致一个 case 错误，而另一种写法，导致另一个 case 错误但是两种写法能过的 case 的并集，是全集。。也就是说。。如果我能把两种写法结合起来。。就能过所有的 case，考虑到最后一个 case 一定是大数据，不要想把它全部测出来了。。所以我采用了这么一个做法。。 if(n == case1 的数据) { 执行能让 case1 数据通过的代码 } if(n > 1000) {执行能让 case3 数据通过的代码} 然后就全部通过了= = 这种做法很实用。。当你的代码无法通过若干 case，但是改动若干之后换了一批错。。但是它们能过的并集是全部 case。。那么就测一下能代表这个 case 的那个变量，比如有 n 个结点，那么 n 一般就可以代表这个 case，如果不行的话，再看另一个变量比如边数 m，一般来说两个变量基本能够确定一个 case，剩下的变量我们是不需要测的，而如果是大数据，就可以用上面 n > 1000 的类似写法，就不需要具体测出具体数据了，有人说想要具体演示一下= =，那就拿这个 1078 的 case1 来演示一下

就是这题，我们来测一下 case1 的数据，以第一个整数 MSize 为例题目的范围是 10^4，但是我知道 case1 一定是小数据，所以拿 n < 100 先试一下，我代码里用 TSize，这个无所谓

可以看到，我在第 31 行加了这么一句，如果 TSize 小于 100，那么就让它返回超时。。可以看到前两个都是小于 100 的，说明 case1 的 TSize < 100，接下来进行二分，看一下 TSize 是否小于 50 也就是这样。。说明 case1 的 TSize 小于 50

资料库

晴神机试技巧讲解浓缩版.pdf

相关推荐

课程资源

热门标签

最新资料