论坛文章：基础算法、技巧、调试概要 -- 雨中飞燕之家-- 编程爱好者博客

题目相对来说简要了一些，算是有代表性了，各方面都有题目
偶不希望像别的帖子那样像为了凑数般弄够100题，相反这里不过二三十。
前六章均为算法基础入门必会解答的题目，也就是若当中有任何一题，
您无法给出正确解答，就不算有算法基础（带星的题目例外），
并且这里不提供基础题解答，若你实在需要，请自行查资料或者找人帮你。
下文假定阅读者具有良好的小学数学基础，
以及懂得使用C/C++/Pascal语言当中的任何一种，尽管你会其它的语言也行，
但算法描述方面以及代码效率还是推荐以上三种。
如果以下算法基础的题目您学习了很久也无法正确解决的话，
那么本人不建议你继续学习编程（基础题不用STL库独立解答出才算是会）。

第一章。循环控制
1.输入一个奇数n，输出对角线长为n的实心或者空心的菱形图案
如当n=5时，有：
    *
   ***
*****
   ***
    *
详细可参阅http://yzfy.org/bbs/viewthread.php?tid=35
2.输入一个奇数n，构造并输出一个n阶等和幻方，
即每一行每一列和两对角线上的n个数的和相等
如当n=5时，有（构造方法请自行搜索或者观察下表）：
03 16 09 22 15
20 08 21 14 02
07 25 13 01 19
24 12 05 18 06
11 04 17 10 23
3.输入一个1e9以内的整数n和k(2<=k<=36)，输出相应的k进制数。
相关题目请参阅http://yzfy.org/bbs/viewthread.php?tid=474
4.输入一个整数n(2<=n<=1e9)，判断它是不是质数，
时间复杂度必须为O(n^0.5），不得为O(n)
质数就是2，以及其它有且只有两个约数的整数，
如3,5,7,11,13,17,19,23,29,31,......（以上为前10个奇质数）
5.字符串模式匹配。输入两个字符串a,b，判断b是否在a中出现，
如有，请输出第一次出现的位置。
参考题目http://yzfy.org/bbs/viewthread.php?tid=8

第二章。简单穷举搜索
1.输入两个数a,b(1 <= a,b <= 1e5)，统计a,b之间一共有多少个质数
相关题目请参阅http://yzfy.org/bbs/viewthread.php?tid=392
若要通过链接里那个题目还需要优化，单纯做出本题并不难。
2.查找1000以内的所有水仙花数，如153 = 1^3 + 5^3 + 3^3 = 1 + 125 + 27
各位上的数字的三次方的和等于自己本身
3.输入一个数n(1<=n<=1e4)，然后再输入n个不同的整数，再输入一个整数k，
判断k是否在那n个整数上出现过。

第三章。迭代、递推和递归
1.斐波那契数列和：输入整数n，求1/1+2/1+3/2+5/3+8/5+.....
一直到第n项的结果。
参考题目http://yzfy.org/bbs/viewthread.php?tid=138
2.★经典Hanoi塔问题，详见http://yzfy.org/bbs/viewthread.php?tid=296

第四章。简单计算几何
1.简单碰撞检测，详见http://yzfy.org/bbs/viewthread.php?tid=543
此乃游戏程序制作必须掌握的内容

第五章。排列组合
1.★有重复全排列，详见http://yzfy.org/bbs/viewthread.php?tid=498

第六章。贪心与分治
1.简单贪心算法题目，详见http://yzfy.org/bbs/viewthread.php?tid=275
及http://yzfy.org/bbs/viewthread.php?tid=338 （此题小心陷阱）
及难一点的★http://yzfy.org/bbs/viewthread.php?tid=325
2.输入一个数n(1<=n<=1e6)，然后再输入n个有序整数（从小到大或者从大到小），
再输入一个整数k，判断k是否在那n个整数上出现过。
3.★输入三个整数a,n,k(1<= a,n <=1e9且1<=k<=1e4)，求a^n mod k，
即a的n次方的结果被k除的余数。
参考题目http://yzfy.org/bbs/viewthread.php?tid=19
4.★快速排序

**以下章节为简单进阶，但实际应用得也不少，特别是记忆化搜索**
第七章。简单记忆化搜索(回溯,DFS,BFS,DP)
1.迷宫寻路。输入一个迷宫地图，找出入口到出口的路线，路线保证唯一。
如以下地图（第一行输入指示地图大小，0表示墙，1表示路）：
7 7
0000000
1111010
0001010
0101110
0101010
0111011
0000000
本题可扩展到RPG游戏的自动寻路问题，当然难度也相应地增加，
难度是不光要算出最短路(或近似解)，并且要以尽可能快的速度算出来。
类似题目http://yzfy.org/bbs/viewthread.php?tid=283
2.连连看游戏消除判定。任意两个图案相同的方块，
当它们之间可以用最多三段的拆线无障碍连通的时候便可消除。
3.最大可连通区域。如有名的PUYOPUYO游戏消除时，
当现出四个或以上相同颜色的PUYO相连时，便可消去，
参考题目http://yzfy.org/bbs/viewthread.php?tid=297
4.3n+1问题（简单DP），见http://yzfy.org/bbs/viewthread.php?tid=115
5.经典题目“回文”（经典DP），见http://yzfy.org/bbs/viewthread.php?tid=105
其实质是最长公共子序列(LCS)问题的变形。
论坛的改错题MDLE的判定就是此算法(LCS)的运用。

第八章。数值计算
1.大整数间的加减乘，以及大整数除以一小整数(32位int范围内称小整数)
题目参见（大整数乘法）http://yzfy.org/bbs/viewthread.php?tid=123
大整数除以小整数http://yzfy.org/bbs/viewthread.php?tid=385

// ************************************************************ //
// 本文源自飞燕之家在线测评论坛http://yzfy.org/，转载清注明出处 //
// ************************************************************ //
算法技巧小集合(C语言描述)
1.例题ct3_1: 个人所得税计算★
（源自 http://yzfy.org/bbs/viewthread.php?tid=269 ）
题目描述：
个人所得税计算方法：假设起征点为k元，
超过k到k+500这部分税率为0.05
超过k+500到k+2000这部分税率为0.1
超过k+2000到k+5000这部分税率为0.15
超过k+5000到k+20000这部分税率为0.2
超过k+20000到k+40000这部分税率为0.25
超过k+40000到k+60000这部分税率为0.3
超过k+60000到k+80000这部分税率为0.35
超过k+80000到k+100000这部分税率为0.4
超过k+100000的部分的税率为0.45

输入：
多组测试数据，每组一行，一行有两个整数n和k
n是收入，0<= k,n <= 2e9
当输入0 0的时候结束

输出：
输出要交的税的数额，保留2位小数

样例输入：
800 800
1000 800
2000 1000
0 0

样例输出：
0.00
10.00
75.00

题目看似很复杂，因为数据分段明显不少，并且看似没有关联。
从原题目的链接帖子的第一页里，你可以看到很多人写了N多if嵌套，
程序逻辑显得极其混乱，并且非常容易出错，
只要看他们提交的结果都不对就知道了。
如果是你，你会怎么写这一题的解答代码呢？
不妨在看后面解答之前先细心想想，等你想尽办法以后，
再看看以下的解答，也许那种恍然大悟的感觉会非常好哦！
以下先帖一段经典if嵌套的方法并且能通过的C代码：

#include <stdio.h>
int main(void)
{
    int k,n;
    while (scanf("%d%d",&n,&k),!(n==0&&k==0))//数据输入
    {
        double tax = 0.0;
        if( n-k <= 0 ); //使用分段函数方式计算
        else if ( n-k-500 < 0 )
            tax = (n-k)*0.05;
        else if( n-k-2000 < 0 )
            tax = 500*0.05 + (n-k-500)*0.1;
        else if ( n-k-5000 < 0)
            tax = 500*0.05 + (2000-500)*0.1 + (-2000+n-k)*0.15;
        else if ( n-k-20000 < 0)
            tax = 500*0.05 + (2000-500)*0.1 + (5000-2000)*0.15
                +(n-k-5000)*0.2;
        else if ( n-k-40000 < 0)
            tax = 500*0.05 + (2000-500)*0.1 + (5000-2000)*0.15
                +(20000-5000)*0.2 +(k-n-20000)*0.25;
        else if ( n-k-60000 < 0)
            tax = 500*0.05 + (2000-500)*0.1 + (5000-2000)*0.15
                +(20000-5000)*0.2+(40000-20000)*0.25+(n-k-40000)*0.3;
        else if ( n-k-80000 < 0)
            tax = 500*0.05 + (2000-500)*0.1 + (5000-2000)*0.15
                +(20000-5000)*0.2+(40000-20000)*0.25+(60000-40000)*0.3
                +(n-k-60000)*0.35;
        else if ( n-k-100000 < 0)
            tax = 500*0.05 + (2000-500)*0.1 + (5000-2000)*0.15
                +(20000-5000)*0.2+(40000-20000)*0.25+(60000-40000)*0.3
                +(80000-60000)*0.35+(n-k-80000)*0.4;
        else
            tax = 500*0.05 + (2000-500)*0.1 + (5000-2000)*0.15
                +(20000-5000)*0.2+(40000-20000)*0.25+(60000-40000)*0.3
                +(80000-60000)*0.35+(100000-80000)*0.4+(n-k-100000)*0.45;
        printf("%.2lf\n",tax); //输出计算结果
    }
    return 0;
}
首先要声明，帖此代码并不是给大家取笑，而事实上，面对这个题目，
很多初学者的确就是使用类似以上代码的变形（帖子里还有比这个更长的），
但偶认为他（她）们也的确思考过，只是实在觉得没有办法化简了。
偶也曾经见过有人写一个解24点游戏的程序，24点游戏就是给你四个数，
通过加入四则运算符和括号，使得表达式的值为24。
这个解24点游戏的程序需要全排列和运算符和括号穷举，对于初学者的确不容易。
那个人也挺“聪明”的，他知道四个数的排列不过24种，
三个符号的排列不过4^3=64种，括号不过5种，最多也不过24*64*5=7680种，
当中一些重复的，去掉后大约二三千种，于是他一种写一个if，
最后代码写了六七千行，也的确顺利地解决了。
这种方法也不失为一种算法，或者可以称为源代码级别穷举算法吧。
偶看到那个程序的代码的时候，不得不Orz程序作者的毅力。
但是，我们为什么要学算法？这个题目就回答了这个问题的一个方面：
好的算法可以让你的代码更清晰明了，更简短优美，
还有在代码有问题的时候也能够更容易发现错误的地方。

现在不讲那个24点，转回这个题目。你现在想到好办法了没有？
我们来简单一点，先考虑收n<=5000元，k=0的情况，有如下信息：
超过k到k+500这部分税率为0.05
超过k+500到k+2000这部分税率为0.1
超过k+2000到k+5000这部分税率为0.15
其实我们完全可以不要按照字面的逻辑来进行程序的分界，
我们可以把它们打乱。比如，
k+500到k+2000这部分，相当于征收两次税，且均为0.05
k+2000到k+5000这部分，相当于征收三次税，且均为0.05
那么原题目等价地换为：
超过k这部分需征收一次，税率为0.05
超过k+500这部分需再次征收，税率为0.05
超过k+2000这部分需再次征收，税率为0.05
结果全部均变为0.05，很合理地，我们想到循环，重复地做同一个东西。
于是，你现在再想想，还需要不需要写那么多的if语句呢？
并且if写得越多、写得越复杂就算容易错。我们需要一段简短漂亮的代码。
相信说到这里，您也差不多甚至已经想到解决办法了。
如果你已经想到了，那恭喜你！！！

以下为标准解答程序(下文简称“标程”)，请细心阅读：
// http://yzfy.org/bbs/viewthread.php?tid=274
#include <stdio.h>
int main()
{
    int n,k,t;
    unsigned nBase[]={0,500,2000,5000,20000,
                40000,60000,80000,100000,-1};
    while(scanf("%d%d", &n, &k), n>0||k>0) //数据输入
    {
        double sum = 0;
        for(n-=k,t=0; (unsigned)n>nBase[t]; ++t)
        {
            sum += n - nBase[t];
        }
        printf("%.2lf\n", sum/20.0); //输出计算结果
    }
    return 0;
}

而事实上，你可能会问，是不是那个税率等间距递增才能使用这种方法。
那偶告诉你，其实不等间距递增也没有问题的，甚至递增和递减混合也行，
一样可以使用此办法化简得如上仅10行左右代码，并且可扩展性可以很好。
这个就留给读者您自己思考一下吧。

// ************************************************************ //
// 本文源自飞燕之家在线测评论坛http://yzfy.org/，转载清注明出处 //
// ************************************************************ //
代码调试技巧小集合(C语言描述，但C/C++/Pascal通用)
1.输入重定向
有不少人对自己提交到网站里得到的错误的结果而感到莫名其妙。
但有可能由于题目的输入数据巨多，要是手工输入将会非常累。
例如输入的数据可能多达成千上万。其实以下将要介绍的代码技巧，
对于做ACM题目较多的人来说，他（她）们也肯定会知道的。
本文算是在做普及工作吧。
首先，从手工转为自动方式，最显然的就是从文件读入的数据代替手工。
如果在源代码里希望把输入从屏幕输入定向到一个文件，
可以使用freopen函数（C/C++均支持此方法），以下为示例：
#include <stdio.h>
int main(void)
{
        freopen("in.txt","r",stdin); //输入从in.txt
        int a,b;
        while(scanf("%d%d", &a, &b)!=EOF)
        {
                printf("%d\n", a+b);
        }
        return 0;
}
这样你可以把题目的输入内容先保存的in.txt文件里，
在程序运行后看看屏幕输出，看是否和题目的样例输出一样。
从这里也可以看出，输入和输出是完全独立的，
您不必把所有输入或输出保存，直到程序全部计算完毕再输出，
这样会很浪费内存，我们也不希望你这样做。
你应当在你能够确定输出内容的时候就马上输出，能少占用内存就少用。
如果你希望本地调试成功的代码不用修改就可以直接提交到OJ系统上，
那你应该加上如下预处理（OJ系统通用标准，不支持这个特性的OJ就不合格）：
#ifdef ONLINE_JUDGE //判断是不是OJ系统上编译
#define FINPUT(file) 0 // 如果是，则不重定向到文件
#else
#define FINPUT(file) freopen(file,"r",stdin)
#endif
#include <stdio.h>
int main(void)
{
        FINPUT("in.txt"); //如果不是则输入从本地in.txt
        int a,b;
        while(scanf("%d%d", &a, &b)!=EOF)
        {
                printf("%d\n", a+b);
        }
        return 0;
}
如果你懂得命令行下运行一个程序，那么你可以不用修改源代码，
假设你的代码所生成的程序名是temp.exe，在命令行下运行：
temp.exe<in.txt
一样实现了相同的功能。
如果程序输出内容过多，你需要保存下来分析的话，那么还可以使用输出重定向。
如上方法，你也可以定义这样一个宏：
        #define FOUTPUT(file) freopen(file,"w",stdout)
如果输入输出均需要重定向，上面的代码可以改写为：
#ifdef ONLINE_JUDGE //判断是不是OJ系统上编译
#define FINPUT(file) 0 // 如果是，则不重定向到文件
#define FOUTPUT(file) 0
#else
#define FINPUT(file) freopen(file,"r",stdin)
#define FOUTPUT(file) freopen(file,"w",stdout)
#endif
#include <stdio.h>
int main(void)
{
        FINPUT("in.txt"); //如果不是则输入从本地in.txt
        FOUTPUT("out.txt");
        int a,b;
        while(scanf("%d%d", &a, &b)!=EOF)
        {
                printf("%d\n", a+b);
        }
        return 0;
}
在命令行下则可以：
temp.exe <in.txt >out.txt

2.断言和运行时错误捕获
断言对于初学者来说，可能是一个很新鲜的名词。
但这个东西对于软件调试来说有一个非常有用的东西，
不过使用的时候也得小心，不正确的使用甚至会适得其反。
首先，断言就是在逻辑上，你认为一定会得到的结果，
例如你假定内存分配一定成功，那么返回值一定不为NULL，
在你包含了头文件assert.h或者cassert后，就可以使用
assert(exp);
exp是你需要断言的表达式，bool类型，当exp为true的时候，
断言成功，程序继续执行，否则程序强制停止，并且发出警告。
这样你就可以明确得知程序发生了逻辑问题，必须进行修改。
但问题就在于，如果你直接使用assert(exp)这个函数，
那么这个断言不管在什么情况下都会编译进执行文件，
如果提交到OJ上，并且断言在内循环里，就显得这个断言会占用相当的时间。
如果我们不希望发布正式版本的软件或者提交代码时去掉这个断言以提升速度，
我们又可以用宏封装一下：
#ifdef ONLINE_JUDGE //判断是不是OJ系统，非OJ系统调试可另起名字
#define ASSERT_LEVEL 1
#else
#define ASSERT_LEVEL 0
#endif
#if (ASSERT_LEVEL>=1)
#define ASSERT(exp) _assert(#exp, __FILE__, __LINE__)
#else
#define ASSERT(exp) 0
#endif
double foo(int n) //计算阶乘
{
        ASSERT(n>=0);
        return n*foo(n-1);
}
#include <stdio.h>
int main(void)
{
        int n=10;
        printf("%d\n", foo(n));
        return 0;
}
以上为一个错误递归算阶乘的程序示例，运行一下你就知道断言的威力了。
那个foo函数应当改为：
double foo(int n) //计算阶乘
{
        ASSERT(n>=0);
        if(n==0)return 1;
        return n*foo(n-1);
}
使用断言还有很多技巧和需要注意的东西，这里暂不多说，先自己体会体会吧。

关于运行时错误捕获，很多人马上就想到了C++的try。但事实上，
这种方法不一定能把异常都捕获，但在OJ系统里面，
你任何一个没有进行处理的异常的抛出都会导致RE（注意main函数返回非0也RE），
尽管有些异常不会对运行结果有影响，操作系统也会忽略掉，
于是一般运行的时候用户也无法发现已经出现异常。
同样，VC也是MS的产品，连操作系统都忽略的异常，用它去调试同样也忽略，
你不能依赖VC调试器得到所有异常的信息，
所以你不要以为VC上调试没有出现任何异常信息就以为那真的是正确的代码，
有可能是系统忽略掉，也有可能是你自己的测试用的数据没有触发它。
对于这个问题目前本人也没有较好的解决办法，所以还是建议你，
养成良好的编程习惯，适当的地方就加上断言，以增加异常被捕获的机率，
这样就更容易发现出错的地方。
// ************************************************************ //
// 本文源自飞燕之家在线测评论坛http://yzfy.org/，转载清注明出处 //
// ************************************************************ //
雨中飞燕
2008年1月12日

博客介绍

正文

论坛文章：基础算法、技巧、调试概要2008-01-13 23:43:00

评论