标题:算法思想:数据连续化
取消只看楼主
ryophoenix
Rank: 1
来 自:重庆
等 级:新手上路
帖 子:60
专家分:0
注 册:2007-10-16
 问题点数:0 回复次数:0 
算法思想:数据连续化
我们先来看这样一段代码:
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]]
搜索更多相关主题的帖子: break case 算法 数据 char 
2008-01-21 01:10



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-198145-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.168175 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved