算法思想：数据连续化
我们先来看这样一段代码：void WordSwitch(char *word, char (*a)[26])
{
int ch;
ch=*word;//取第一个字母
switch(ch)
{
case 'a':
a[0][0]++;
break;
case 'A':
a[1][0]++;
break;
case 'b':
a[0][1]++;
break;
case 'B':
a[1][1]++;
break;
case 'c':
a[0][2]++;
break;
case 'C':
a[1][2]++;
break;
case 'd':
a[0][3]++;
break;
case 'D':
a[1][3]++;
break;
// 以此类推，他把26个大小写字母用switch case全部写一次
// 一共写了160行代码，这里再多列出来也没有什么意义了
default:
}
}
以上代码其实在做一个大小写统计，如果输入的是大写字母，
就a[1][ch-'A']++;否则a[0][ch-'a']++;
事实上，我们只需要写7，8行代码就搞定的东西，有人却写了160行，
你觉得这说明了什么？只说明了写这个代码的人并没有掌握算法里的数据连续化处理。
首先，什么是数据连续化？其意思就是，给你一组离散化的数据，
假如我们对这组数据的操作极相似，并且，
我们如果可以用连续的方式进行相同处理，就可以避免写大量几乎一样的代码。
例如以上代码，26个大小字字母就是一组离散的数据，是一组字符。
然而，通过ASCII码的关系，我们可以把字符变为一组连续的数据进行处理。
并且在这里把数据连续化处理后，速度还是原本代码的好几倍，
因为最坏情况下也只需要进行四次判断就足够了。
现在再给另一个例子，就是给你年月日，计算出这天是那一年的第几天。
很多的新手都会这样或者以类似的方式来写：
int GetDay(int y, int m, int d) //y年m月d日
{
int s;
switch(m-1)
{
case 1:
s=31; break;
case 2:
s=31+28; break;
case 3:
s=31+28+31; break;
case 4:
s=31+28+31+30; break;
case 5:
s=31+28+31+30+31; break;
case 6:
s=31+28+31+30+31+30; break;
case 7:
s=31+28+31+30+31+30+31; break;
case 8:
s=31+28+31+30+31+30+31+31; break;
case 9:
s=31+28+31+30+31+30+31+31+30;
break;
case 10:
s=31+28+31+30+31+30+31+31+30+31;
break;
case 11:
s=31+28+31+30+31+30+31+31+30+31+30;
break;
}
if(m>2) //大于二月的话
if(y%400==0 || (y%100 && y%4==0)) //判断闰年
{
s++; //是的话加上2月29日那天
}
return s+d; //返回这天是那一年的第几天
}
在这里我们又见到一大段 switch - case 的东西。
不但容易复制出错（当中如果有一个错，就要连同后面的也要修改），相当的麻烦。
偶这里为了不容易出错，是直接写表达式，那些“高手”居然直接把结果直接计算好。
直接计算好的问题是，万一有一个数不小心算错了，要检查也是一件超麻烦的事情。
好，现在让我们用连续化的思想去做这个题的话，
我们首先看看每个月的月数有没有规律。不过这没有明显的规律，为了能连续化处理，
我们可以建立一个数组，直接保存每个月的天数（第12月可以不保存），如：
int List[12]={31,28,31,30,31,30
31,31,30,31,30,31};
这样，我们就可以直接使用循环进行累加，免去了查错的麻烦，
并且很容易扩展到任意多个月的计算：
int GetDay(int y, int m, int d) //y年m月d日
{
int s=d;
int List[12]={31,28,31,30,31,30
31,31,30,31,30,31};
if(y%400==0 || (y%100 && y%4==0)) //判断闰年
{
++List[1]; //是的话2月多加一天
}
for(y=0, --m; y<m; ++y) //年份变量已不再需要，直接作为循环变量
{
s += List[y]; //直接累加
}
return s; //返回这天是那一年的第几天
}
我见过有很多人说算法很简单，还搬出一大堆道理，
说以后编程写应用程序根本用不着什么算法，还说我们学编程的不是学数学，
还说学编程的核心不是学算法，说学编程不仅仅是算法。
但事实上，这种人基本上都是自己在打自己嘴巴。事实上是逃避学习算法的借口。
学过基础算法的人和没学过算法的人写出来的代码完全是两码事。
就像以上的算日期的两份代码，你喜欢哪一份？假如每个月的天数不是限制为公历，
而是改成其它的呢，你如果用第一段代的代码，那是不是得进行大量修改？
还是用第二段短的代码，仅仅改一下那个数组的值呢？
你觉得哪份代码通用性和可读性好？哪份代码更容易维护修改？
我们再来看一个题：
按照输入要求进行打印一个螺旋数字矩阵。
结果有的人也这么写（这个代码在当中已经算比较短并且比较有代表的一个了）：
#include<stdio.h>
int main()
{
int array[31][31]={0};
int x,y,t,m,n,m2,n2;
int count;
while(scanf("%d%d%d",&y,&x,&t)!=EOF)
{
if(t==0) //逆方向
{
for(n=1,count=1;count<=x*y;n++)
{
for(m=n;m<=x-n+1&&count<=x*y;m++,count++)
array[m][n]=count;/*竖下*/
for(m-=1,n2=n+1;n2<=y-n+1&&count<=x*y;n2++,count++)
array[m][n2]=count;/*横右*/
for(n2-=1,m2=m-1;m2>=n&&count<=x*y;m2--,count++)
array[m2][n2]=count;/*竖上*/
for(m2+=1,n2=n2-1;n2>n&&count<=x*y;n2--,count++)
array[m2][n2]=count;/*横左*/
}
}
else //顺方向
{
for(m=1,count=1;count<=x*y;m++)
{
for(n=m;n<=y-m+1&&count<=x*y;n++,count++)
array[m][n]=count;/*横右*/
for(n-=1,m2=m+1;m2<=x-m+1&&count<=x*y;m2++,count++)
array[m2][n]=count;/*竖下*/
for(m2-=1,n2=n-1;n2>=m&&count<=x*y;n2--,count++)
array[m2][n2]=count;/*横左*/
for(n2+=1,m2=m2-1;m2>m&&count<=x*y;m2--,count++)
array[m2][n2]=count;/*竖上*/
}
}
for(m=1;m<=x;m++) //输出结果
{
for(n=1;n<=y;n++)
printf("%4d",array[m][n]);
putchar('\n')
}
putchar('\n');
}
return 0;
}
在那个帖子里，长度为2K字节以上的代码到处可见，连一些算法大牛也用了很麻烦的写法。
那个题并非考验你的算法的速度，而是考验你如何处理和运用数据。
在这里运用连续化处理就并不是像前两个例子那么显而易见了，主要是在前进方向上，
四个方向就是一组离散的数据，为了能连续化处理，我们可以这样：
int sym[4][2]={0,-1, 1,0, 0,1, -1,0,};
依次对应：上，右，下，左。
再加一个值从0至3之间的变量，这个变量的值就可以直接指示方向，
这个变量加一或者减就可以顺或者逆时针转一个角度了。
示例代码：
#include <stdio.h>
//SET_XY 获取方向增量
#define SET_XY(x,y,d) x=sym[d][0], y=sym[d][1]
int main()
{
int m, n, t;
int sym[4][2]={0,-1, 1,0, 0,1, -1,0,}; //连续化处理的关键
while(scanf("%d%d%d", &m, &n, &t) != EOF)
{
int map[32][32] = {0}; //初始化数据
int x, y, dx, dy, d, nStep = 2;
for(x = 1, y = m + 1; x <= n; x++) //设置上下边界
map[x][0] = map[x][y] = -1;
for(x = 1, y = n + 1; x <= m; x++) //设置左右边界
map[0][x] = map[y][x] = -1;
x = y = 1; d = 1 + (t == 0);
SET_XY(dx, dy, d);
if(map[y+dy][x+dx]) //设置起始方向
{
d = (d+1+((t==0)<<1))%4; //d就是方向
SET_XY(dx, dy, d);
}
for(map[1][1] = 1;;nStep++) //螺旋遍历
{
x += dx , y += dy;
map[y][x] = nStep;
if(map[y+dy][x+dx]) //碰到边界或者有数的地方
{
d= (d+1+((t == 0)<<1))%4; //改变方向
SET_XY(dx, dy, d);
if(map[y+dy][x+dx])break; //无处可走，退出
}
}
for(y = 1; y <= n; y++) //输出结果
{
for(x = 1; x <= m; x++)
printf("%4d",map[y][x]);
printf("\n");
}
printf("\n");
}
return 0;
}
这个思想在制作迷宫游戏，或者2D，3D方格类游戏，要进行方向性判断的时候，
把方向增量进行连续化以简化处理是一个很常见的思想。尽管在上面螺旋矩阵的例子里，
这个优势还不是很明显。或者你这样，写一个随机生成2维迷宫地图的程序，
看看不使用以上思想写出来的程序，和使用以上思想写出来的程序，差别在哪里吧。
前者为了判断四个方向来处理，将要使用四个if；
后者并不需要专门判断方向，直接就可以得到方向增量来处理。
代码量的差别在那个时候，将一目了然。
[[it] 本帖最后由 ryophoenix 于 2008-1-29 22:13 编辑 [/it]]
