修好 Manacher 越界
场景:~/work/str/pal.cpp 用 Manacher 求最长回文子串的长度,带着内存检查一跑就报越界。 任务:修好往外扩的那个 while 条件。make 编译(带内存检查)后自测,内存检查不报错、结果正确才算过。 可操作范围:
测过了和证明了差在哪
一个算法在一万组数据上都跑对了。这件事和「它是对的」之间的差距是【0】。
对拍能给出什么样的结论
第 1 步:两种判素数的写法对拍 第 2 步:前面这些,两边都一致 第 3 步:到这一个,两边分叉了 第 4 步:一致只说明测过的那些 116 117 118 119 120 121 拿另一种写法对拍,两边结果一样。这说明【0】。
一个反例能说明什么
找到一组输入让算法给错了答案。这一组输入【0】。
什么叫貌似正确
有一类算法特别危险,它【0】。
在前一百多个数上对拍
下面 fast_prime 只拿 2、3、5、7 去试除。把它和正确版在 2~120 上对拍一遍,数一数一致了几次: #include <algorithm> #include <iostream> #include
把第一个反例找出来
接着往上找:从 2 一直试到 1000,第一个让两个版本给出不同结论的数是几?补全 first_diff。 (本题用 g++ -std=c++17 -O0 编译。)
换个测试范围结论就翻了
同一个 fast_prime、同一种验收办法(对拍),只把范围从 2..120 换成 2..200,两次的结论分别是什么?输出格式如 一致/不一致。 (本题用 g++ -std=c++17 -O0 编译。)
循环不变式是什么
第 1 步:下面那格是 best 第 2 步:前 1 个里 best 最大 第 3 步:前 2 个里 best 最大 第 4 步:前 3 个里 best 最大 第 5 步:前 4 个里 best 最大 第 6 步:前 5 个里 best 最
用不变式证明要验哪三件事(C++)
拿不变式证明一个循环是对的,要验的三件事是【0】。