解题报告——函数 w、回文串.pptVIP

解 题 报 告 ——函数 w、回文串 @计2 郑扬涛 函 数 W 题目大意： Ytaaa定义了函数 w 用于未知的用途。 if a = 0 or b = 0 or c = 0, then w(a, b, c) =1?if a 20 or b 20 or c 20, then w(a, b, c) =w(20, 20, 20)?if a b and b c, then w(a,b,c) = w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c)?otherwise w(a,b,c) = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1) 现在对于输入的 a,b,c，请你求出 w(a,b,c) 逐句翻译成代码？ 随着递归层数 的不断增加 通过时间与空间的转换来提高算法性能 思路分析 每次递归都会造成大量的重复计算,因此我们可以把已经算过的数据存储起来,下一次需要用到的时候直接调用即可！ ＡＣ代码 #include?stdio.h?? #include?string.h?? int?m[30][30][30]={0};?? int?w(int?a,int?b,int?c){?? ????if?(a?=?0?||?b?=?0?||?c?=?0)?? ????????return?1;?? ????else?if?(a??b??b??c)?? ????????return?(m[a][b][c-1]?+?m[a][b-1][c-1]?-?m[a][b-1][c]);???????? ????else?? ????????return?(m[a-1][b][c]?+?m[a-1][b1][c]?+?m[a-1][b][c-1]?-?m[a-1][b-1][c-1]);?? }?? int?main()?? {?? ????int?a,b,c;?? ????for?(a?=?0;a?=?20;a++)?? ????????for?(b?=?0;b?=?20;b++)?? ????????????for?(c?=?0;c?=?20;c++)?? ????????????????m[a][b][c]?=?w(a,b,c);???? ???? while?(scanf(%d%d%d,a,b,c) != EOF){?? ????????if?(a??20?||?b??20?||?c??20)?? ????????????printf(%d\n,m[20][20][20]);?? ????????else?? ????????????printf(%d\n,m[a][b][c]);?? ????}?? ????return?0;?? } 事先计算好 w(a,b,c) 存到数组里 回 文 串 题目大意： 要求支持两个操作： 添加一个字符串。例如 add s。 2. 判断第 k(从 1 开始)个字符串是否是回文串。例如 judge k 对每个judge，根据是否为回文串，输出yes\no，编号不存在输出error. 思路分析 这题直接按题目要求翻译就可以了，注意一些细节的地方,比如： 1、一些 空格、回车 会影响到字符串的输入 2、回文串判断函数 中 [循环到哪里]，[首尾元素的对应]…… #include?iostream?? #include?vector?? #include?string?? using?namespace?std;?? vectorstring?str;?? void?judge(string?s);?? int?main()?? {?? ????int?n,i,num;?? ????string?opr,s,temp;?? ????while?(cin n){?? ????????getchar(); //读掉回车?? ????????for?(i?=?0;i??n;i++){?? ????????????cin??opr;?//读入操作? ????????????getchar();??//读掉空格 ????????????if?(opr?==?“add”){ //若是添加?? ????????????????cin s; //读入字符串?? ????????????????str.push_back(s);//存到数组里?? ????????????} else?if?(opr?==?“judge”){ //若是判断?? ????????????????cin??num; //读入编号?? ????????????????if?(num??str.s