读程序写结果之进阶篇
上一讲，我们就“读程序写结果”解题的一般方法，做了个简单的探讨与总结。本讲，我们共同来研究两个特例：有关“字符（串）的操作与递归调用。
技巧五：字符串的处理
字符串操作，无论是NOIP初赛还是复赛，近些年来，频频出现，非常明确地提醒了选手，在准备NOIP竞赛时，必须充分地重视并认真彻底地把字符（串）操作了解清楚。
在c/c++中，有关字符的类型有两种：char、string。特别要注意类型string与字符数组的异同点：（假设变量说明为：string a;char b[100];）
相同点：都可以用下标变量（形如a[i]、b[i]）进行访问。
有关字符（串）的函数与过程，请参阅“基础篇”。值得一提的是，常用字符的ASCII 码为（括号内为ASCII码，从小到大排列）：…’0’(30H)…’9’…’A’(41H)…’Z’…’a’(61H)…’z’…
对字符（串）的处理，要求选手能结合字符（串）有关知识，灵活使用前面讲过的技巧。以下选例说明字符（串）操作在“读程序写结果”中的应用。
[选例八NOIP2008提高组第四题]
1#include<stdio.h>
2#include<stdlib.h>
3#include<string.h>
4int i,j,len;
5char s[50];
6int main()
7{
8scanf("%s",s);
9len=strlen(s);
10for(i=0;i<len;++i)
11{
12if(s[i]>='A'&&s[i]<='Z')s[i]-='A'-'a';
13}
14for(i=0;i<len;++i)
15{
16if(s[i]<'x')s[i]+=3;else s[i]+=-23;
17}
18printf("%s/",s);
19for(j=1;j<4;j++)
20{
21for(i=0;i<len-j;i=i+j)
22{
23s[i]=s[i+j];
24}
25}
26printf("%s\n",s);
27/*
28输入：ABCDEFGuvwxyz
29*/
30system("pause");
31return0;
32}
输入：ABCDEFGuvwxyz
输出：____________
[解析]：应该算基础题。程序有点长，我们可以根据结构分为以下几个程序段进行分析：第10至13行：这个循环是依次判断字符是否为大写字母，若是，则改为小写。执行后s 的值为：abcdefguvwxyz；
第14至17行：注意分界点（对比对象）是字母’x’，运算后，s为：defghijxyzabc
第18行：输出：defghijxyzabc/
第19至25行：循环递变，j的值比较小，直接列表模拟！注意15行：变量i的步长。变量j123
递变前的s defghijxyzabc e f g h i j x y z a b cc g fi h xj z yb a ccc
递变后的s efghijxyzabcc g f i h x j z y b a c cc h fi z xj a yb c ccc
实现功能依次移位奇数位移位1�4�7�10�13
第21行：输出：hfizxjaybcccc
虽然本程序给人第一感觉：程序长、似乎挺难的，但经过简单的分割处理，可以看出，每个程序段的功能都是显而易见的。“一切反动派都是纸老虎”！在战略上可以藐视这类题，但在战术上应该重视细节。克服长程序给人的心理压力，沉下心来，仔细分析，认真运算，一切就迎刃而解。
[选例九]
1#include<stdlib.h>
2#include<stdio.h>
3#include<string.h>
4int n,i,j;char str[200];
5char a[22][200];
6int t1,t2,code;
7int main()
8{
9gets(str);
10int temp1;
11n=0;
12while(1){
13i=(strchr(str,'')-str>0)?strchr(str,'')-str:0;
14n=n+1;
15if(i>0)
16{temp1=0;
17a[n][0]=n+64;
18while(temp1<=i-1){
19a[n][temp1++]=str[temp1];}
20a[n][i]='\0';//
21temp1=i+1;
22while(str[temp1]!=0)
23{str[temp1-i-1]=str[temp1++];
24};
25str[temp1-i-1]=0;
26}
27else{
28temp1=0;
29a[n][0]=n+64;
30while(str[temp1]!=0)a[n][temp1++]=str[temp1];
31str[temp1]=a[n][temp1]='\0';
32str[0]='\0';break;}
33}
34for(i=1;i<=n-1;i++)
35for(j=1;j<=n-i;j++){
36char strtemp[200];
37strtemp[0]=0;
38strcat(strtemp,a[j]);
39strcat(strtemp,a[j+1]);
40sscanf(strtemp,"%d",&t1);//将strtemp转成整数
41strtemp[0]=0;
42strcat(strtemp,a[j+1]);
43strcat(strtemp,a[j]);
44sscanf(strtemp,"%d",&t2);
45if(t1<t2){
46strcpy(a[21],a[j]);strcpy(a[j],a[j+1]);strcpy(a[j+1],a[21]);
47;}//a[21]作临时存储空间
48;}
49for(i=1;i<=n;i++)
50{
51for(int temp=0;temp<strlen(a[i]);temp++)
52printf("%c",a[i][temp]);
53}
54printf("\n");
55system("pause");
56return0;
57}
输入：9334321
程序运行的结果是：
[解析]这题用到的字符（串）子程序比较多，有需要的，请参阅“基础篇”。
while（1）构成循环的功能是什么呢？第13行，取空格的位置；继而，如果空格存在
的话，把空格前的字符串赋予a[n]，并在串str中把至空格为止的字符全部删除；若空格不存在，则把str赋予a[n]，令str为空串。所以，实际上，它是以空格为分隔，把各数字字串，分别置于数组a中，即a={'9'、'3'，'34'，'321'}。
第34到48行，冒泡排序经典程序段，不同的是，大小的评价标准不一样。它是以相邻两数字字串连接在一起的数值大小为衡量标准。以a[j]='3'、a[j+1]='34'为例，执行完第40、44行的语句后可求得t1=334、t2=343，由于t1<t2，交换a[j]、a[j+1]。这样从“大”到“小”排列后依次输出结果：9343321。
也即，输出由这些数字字串排列生成的最大数值。
技巧六：子程序调用
在处理子程序调用时，应注意参数的传递，特别是区分值参与变参。如果存在全程变量与局部变量交叉使用时，要注意变量的作用域。必须清楚，只有在调用的子程序完全执行
．．．．
完毕
．．，才能返回调用该子程序的程序中继续执行。
递归调用是子程序调用的重点，也是难点。如何有效正确计算递归程序的结果呢，下面举几个例子说明一下：
[选例十]
#include<stdio.h>
#include<stdlib.h>
void w(int num)
{
if(num>=14)w(num/14);
printf("%d\n",num);
}
c语言的冒泡排序算法
int main()
{
w(2009);
system("pause");
return0;
}
程序运行的结果是：
[解析]具体执行过程如下：（注意箭号顺序）
⎪
⎪
⎨
⎧
⎨
⎧
)
print(143)
w(143)
三个printf语句，依次输出：101432009
本例应用大括号的方式全部展开递归调用的过程，只要谨记所调用的子程序执行完毕方能返回调用该子程序的程序中继续执行，严格把关语句的执行顺序就可以了。
只是，很多时候，我们没法，或者很难手工全部展开递归的详细过程，这时，一般可以采用“自底向上”，从递归边界出发，递推出结果。如：
[选例十一]
#include<stdio.h>
#include<stdlib.h>
4
5
int s(int n,int k)
{
if((n==k)||(k==1))return1;
else
return s(n-1,k-1)+k*s(n-1,k);
}
int main()
{
printf("%d\n",s(7,5));
system("pause");
return0;
}
输出结果：
[解析]程序很短很简单，但是如果我们用类似上例的方法来模拟展开该递归的执行调用过程，会碰到前所未有的困难。原因很简单，递归调用的次数太多了。碰到这种情况时，我们可以从递归的边界出发，进行递推求解。具体求解过程如下：
1、边界赋值：s[n,n]=1；s[n,1]=1
2、递推求解过程：
S[3,2]=s[2,1]+2*s[2,2]=3
S[4,2]=s[3,1]+2*s[3,2]=7；s[4,3]=s[3,2]+3*s[3,3]=6
S[5,3]=s[4,2]+3*s[4,3]=25；s[5,4]=s[4,3]+4*s[4,4]=10
s[6,4]=s[5,3]+4*s[5,4]=65；s[6,5]=s[5,4]+5*s[5,5]=15
S[7,5]=s[6,4]+5*s[6,5]=65+5*15=140
整个递推过程，可记录如下表格：
k
12345
n
11
211
3131
41761
5125101
616515
71140
也即本例输出结果为：140
值得注意的是，我们只要求出表格中的数据即可，其它空白的，无需求解。为了节省时间，避免不必要的人为错误，所做的运算越少越好。那么哪些是该算的、哪些是无需计算的，也即如何只进行有效计算呢？这问题，留给读者自己思考。
小结：字符（串）操作，除了要求选手要有扎实的语言基础并了解相关字符串知识点外，多数还体现了对选手细心、耐心及毅力品质的考核。题目一般不会引用高深的算法或理论，需要的就是“静心分析、耐心计算”。
而子程序的调用，考查的除了子程序调用本身的一些知识点外，多数还会揉合一些其它综合知识。比如，选例十一，其实就是第二类Stirling数。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。