做网站广告收入,封面设计网站有哪些,有哪些好玩的网页游戏,上海短视频推广公司对拍就是通过把自己写的程序的结果和一个完全正确的程序结果进行比较 从而得出自己写的错误程序的漏洞
比如这道题
24点游戏 EOlymp - 44
The number of ones
In arithmetic expression you are allowed to use the number 1, operations of addition, multiplication and …对拍就是通过把自己写的程序的结果和一个完全正确的程序结果进行比较 从而得出自己写的错误程序的漏洞
比如这道题
24点游戏 EOlymp - 44
The number of ones
In arithmetic expression you are allowed to use the number 1, operations of addition, multiplication and parenthesis. What is the minimum number of ones you need to obtain the positive integer n?
Input
One number n (1 ≤ n ≤ 5000).
Output
The required number of ones. 题意将输入的数字 只能通过用1和加乘运算表示出来 问这个数字最少用多少1
一开始自己想到遍历因数 尽可能用小的因数相乘 不断累积小的因数 从而获得这个数 如果是质数 就-1先算偶数的结果然后
最后再加1 那么这种做法WA
复杂度分析每一个结果要计算O(sqrt(n))次
最大sqrt(5000)约等于71
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int maxn 5010;
bool bok[maxn];
int cnt;
void div(int n){if(n5){cntn;return;}if(!bok[n]){cnt;div(n-1);}else {for(int i2;i*in;i){if(n%i0){cnti;div(n/i);break;}}}
}
int main()
{freopen(in.txt,r,stdin);freopen(pro.txt,w,stdout);for(int i2;i5000;i){if(!bok[i])for(int jii;j5000;ji){bok[j] 1;}}int n;while(~scanf(%d,n)){div(n);printf(%d\n,cnt);cnt0;}return 0;
}此时可以考虑用对拍检测法检测程序 AC程序
而正确做法动态规划 应该这么做
对每一个数遍历所有可能乘到这个数的可能 然后从中选择最小的记录下来
符合动态规划的最优子结构 和重叠子问题 性质 因为大数是通过小数的结果反馈得来 复杂度分析对于任何一个结果On*sqrt(n)
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int maxn 5010;
int dp[maxn];
int main()
{freopen(in.txt,r,stdin);freopen(right.txt,w,stdout);dp[1]1;for(int i2;i5000;i){dp[i] dp[i-1]1;for(int j2;j*ji;j){if(i%j0)dp[i] min(dp[i],dp[i/j]dp[j]);}}int n;while(~scanf(%d,n)){printf(%d\n,dp[n]);}return 0;
}另外数据生成程序
#includebits/stdc.h
using namespace std;
int main()
{freopen(in.txt,w,stdout);for(int i1;i5000;i){printf(%d\n,i);}return 0;
}把所有数据范围的数据都遍历了
或者我们生成随机数
#includecstdio
#includecstring
#includeiostream
#includectime
#includecstdlib
using namespace std;
typedef long long ll;
int main()
{freopen(in.txt,w,stdousrand(time(0));//初始化随机数生成器for(int i1;i100;i){printf(%d\n,rand()%50001);}//注意srand和rand如果放到一起写 一般同一秒内生成的随机数是相同的//因为time(0)是根据1970年1月1日00点00分00秒开始到现在的秒数return 0;
}最后测试程序
#includebits/stdc.h
#includewindows.h
using namespace std;
stringstream ss;
int main(int argc,char *argv[])
{int t 100;system(data.exe);//运行数据生成程序int s1 clock();system(right.exe);//执行正确程序int e1 clock();couts1endl;system(pro.exe);//执行错误程序int e2 clock();coute2endl;Sleep(1000);//程序暂停1scoute1-s1 e2-e1endl;//输出两个程序的耗费时间(ms)if(system(fc pro.txt right.txt)){//比较两个文件是否存在不同printf(WA);}return 0;
}那么运行最后的错误程序 就能看到是否有不一样输出的地方了
最后发现46这里有问题
自己的程序
46 2*23
23 122
22 2*11
11 110
10 2*5
sum up212125 13
正确程序比如 46 就是遍历所有的可能 dp[45]1
或者通过 45 5*9
9 3*3
sum up 15 33 12
这种结果并不是通过因数拆分得到的 而是通过遍历所有可能选出最小的可能 而双数在错误程序中 必定是一个通过2去化简的数
所以这种情况直接略过了从45过渡过来的可能 略过了最小的可能 所以当选择极限方案时 还是不仅要考虑贪心 也要考虑DP
贪心是我们已知的最优解的走法 而动态规划是我们要从所有子问题分支中依据数值选择出最优的分支
对于问题的判断不清 很容易选择贪心算法 错误的选择了最优分支 而不忽略了真正的最优可能分支
那么对拍检测4步
1 自己的待查程序
2 一个正确/暴力程序
3 一个输出生成程序
4 测试程序
四个程序最好放到同一目录结构下
运行测试程序 找出错误实例
