这两天在看论坛上以往的编程比赛题，不知道为什么前三次的比赛帖子找不到了，所以我从第四次开始看起了。帖子虽然已经是2005年的了，到现在已经有4年的时间了，但现在看来比赛的题目依然很有趣也很有质量，而且我可以想象，05年的时候论坛上众多的编程爱好者是如何饱含热情熬夜写程序的。。。
第四次的编程比赛题在这儿：http://www.programfan.com/club/showpost.asp?id=118388&t=o
我的方法是利用栈，把操作数和运算符放到两个栈里，然后依次取出两个数和一个运算符进行运算，结果再放回栈里，直到栈空；假设有n个数则这n个数之间有n-1个空格是放运算符的，运算符只有加减，可看作是布尔变量0或1，则n-1个布尔变量最大值就是(n-1)的平方再减1，所以让运算符从最小的0开始到最大的(n-1)的平方减1，依次将它们化成二进制的0或1，1代表加，0代表减，然后和操作数栈中出栈的两个操作数运算，计算出最后的结果再看能否被k整除，这就是我的算法。算法倒是好想，但写程序的时候遇到了很多细节上的问题，比如忘记考虑边界问题等等。。。
这是我的代码：
#include <stdio.h>
#define MAX 10000
typedef struct
{ int num[MAX];
int top;
}sqstack;
sqstack init()
{ sqstack s;
s.top=-1; /*初始化时栈顶是-1*/
return s;
}
int push(sqstack *s,int x)
{ if(s->top==MAX-1)
return 0;
s->top++; /*栈顶先加1，再入栈*/
s->num[s->top]=x;
return 1;
}
int pop(sqstack *s,int *x)
{ if(s->top==-1)
return 0;
*x=s->num[s->top]; /*先出栈，栈顶再减1*/
s->top--;
return 1;
}
char ch='?';
int take(sqstack *a,sqstack *b,sqstack *temp1) /*此处a,b,temp已代表地址，所以后面a,b,temp前不用再加&号*/
{ int n,k,i,t,x,y,z,Y,S,m=1,p,T;
printf("Please input n:\n"); /*输入数的总数量*/
scanf("%d",&n);
printf("zhengchushu K,K is between 2 to 100:\n");
scanf("%d",&k);
printf("please input the numbers:\n");
for(i=0;i<=n-1;i++)
scanf("%d",&temp1->num[i]);
a->top=-1; /*这一步必不可少*/
for(i=n-1;i>=0;i--)
push(a,temp1->num[i]);
for(i=0;i<n-1;i++)
m=m*2;
m=m-1;
for(t=0;t<=m;t++) /*this is important*/
{ for(i=0;i<=n-1;i++) /*由于对操作数的操作会改变栈内元素，所以每次循环要重置栈temp*/
{ temp1->num[i]=a->num[i];
temp1->top++;
}
T=t;
for(i=0;i<n-1;i++) /*这个循环是将T转换为二进制的0和1，然后放到栈b中*/
{
Y=T%2;
push(b,Y);
S=T/2;
T=S;
}
while(b->top!=-1)
{ pop(temp1,&y);
pop(temp1,&x);
pop(b,&z);
switch(z)
{ case 1: {y=y+x;push(temp1,y); }break;
case 0: {y=y-x;push(temp1,y); }break;
default: printf("error!\n");
}
}
temp1->top--; /*这一步必不可少*/
if(y%k==0){ y=1; break;} /*这一步,只要找到可以被整除的就退出for循环*/
else y=0;
} /*this end*/
if(y==1) printf("Divisible\n");
else if(y==0) printf("Not divisible\n");
printf("You can press any key to conniue,or press 'q' to quit.\n");
ch=getch(); //注意这一行，本程序是用C编译器编译的，getch()函数在conio.h头文件中，本程序没有conio.h头文件，可用getchar()代替getch()，但getchar()会自动读取缓冲区里面的字符，所以此处要用两个getchar()函数，因为你输入完数字之后会按回车键，第一个getchar()会自动读取这个回车键，所以要用两个getchar()函数。
return 1;
}
main()
{ int take(sqstack *a,sqstack *b,sqstack *temp);
sqstack a,b,temp1;
a=init();
b=init();
temp1=init();
while(ch!='q')
take(&a,&b,&temp1);
return 0;
}
。。我现在才发现我写的这个程序这么长！！一看这么长，我就觉得它已基本上不可能会是个优秀的程序了（其实也并不一定）。再看看当时的冠军nopeak的代码，他的方法很巧妙，占用内存小，运行速度也快，他的代码如下：
#include <iostream.h>
#define MAX1 100
#define MAX2 10000
int main()
{
int a[MAX1]={0},n,k;
while(cin >> n >> k)
{
int temp;
cin >> temp;
a[(temp+MAX2*k)%k]=1; // 括号里面是不太好理解的一段代码
while(--n)
{
int b[MAX1]={0};
cin >> temp;
for(int i=0;i<k;i++)//新输入的数与上轮存在的余数进行加和减运算
{
if(a[i])
{
b[(i+temp+MAX2*k)%k]=1;
b[(i-temp+MAX2*k)%k]=1;
}
}
for(i=0;i<k;i++)a[i]=b[i];//某一轮输入结束后,所有存在的余数对应的a数组值取1,别的置0
}
if(a[0])cout << "Divisible" << endl;//最后一轮输入结束后,看是否有余数为0,即能整除的结果
else cout << "Not divisible" << endl;
}
return 0;
}
很明显，nopeak的程序不仅比我的程序简明，而且执行效率还高出很多！我一共用了3个包含10000个元素的数组，而nopeak只用了两个100个元素的数组，而且用nopeak的算法用int型变量也不会产生溢出，而我所定义的int型，当输入数值很大时相加或相减就会产生溢出，主要是定义3个10000个元素的数组太浪费空间了，另外程序也太长了，显得很繁琐。。。nopeak的算法真的很妙，我真的想不出来这样的算法来