Tanky Woo的程序人生

话说已经三个月没碰过算法了，真的很无奈，恐怕学到的一点知识全忘光了。
昨天，萝莉神给我一道题目：

TitleRoowe（没见过这么BT的，拿自己名字去编题目）很喜欢研究数学，现在他就遇到一个有趣的问题，比如，直角三角形的周长是120的话，那么它的三条边可以是20，48，52，或者24，45，51，还有30，40， 50，有三种不同的解，现在他想知道一个区间[a,b]中哪个数的解数最多（1<= a, b <= 1000000）？
输入：
10 100
1000 100000
1 1000000
300000 700000
100000 300000
100000 700000
800000 900000
104 720720
80 360360
1 1000000
输出：
60 2
55440 40
720720 104
360360 80
240240 64
360360 80
831600 78
720720 104
360360 80
720720 104

让我做下，本来懒得做的，但是他说打表就OK了，于是我就欣然答应了。。。奈何他眼中的打表难易度和我眼中不一样，再次看到了数学系高材生和我的差距，嘿嘿。

     第一次尝试，失败。
    我说，不就是勾股定理a^2+b^2=c^2吗？结果他说，你再去补补数学知识。。。。
    于是给了我一个链接，我一看，不就是百度百科的勾股数吗，于是就暂时搁浅了。
    今晚第二次尝试，仍然失败。
    依稀记得昨天他给我说了有个什么勾股数公式，在百度百科那个勾股数的最下面介绍了，但是我看了半天，还是有点迷糊。
    然后让他把代码给我看看，好吧，结合百科介绍的勾股数公式，茅塞顿开。

   这里给出勾股数公式：
   直角三角形三条边a, b, c，其中a,b是直角边。
   则 a=2*m*n 　　

b=m^2-n^2 　　

c=m^2+n^2

当然，这是有前提条件的，也就是其局限性：“勾股数的公式还是有局限的。勾股数公式可以得到所有的基本勾股数，但是不可能得到所有的派生勾股数。比如6，8，10；9，12，15…，就不能全部有公式计算出来”

也就是说，3,4,5可以求出来，但是其倍数6,8,10就不行了。

这里要注意几个问题：

1.构成三角形的条件：

2*m*n+m^2-n^2 > m^2+n^2

既m>n

2.a, b, c互质，即无法得到派生的勾股数。

以下是代码：

// Tanky Woo
// www.WuTianQi.com
#include <iostream>
#define M 1000000
int arr[M+1];
using namespace std;

int gcd(int a, int b)
{
    if(b==0)
        return a;
    else
        return gcd(b, a%b);
}

void init()
{
    for(int i=1; i<=800; ++i)
        for(int j=i+1; 2*j*j+2*j*i<=M; ++j)
        {
                int x, y, z;
                x=2*i*j;
                y=j*j-i*i;
                z=j*j+i*i;
                //确保x,y,z互质
                if(gcd(gcd(x, y), z) == 1)
                {
                    int t = x+y+z;
                    int tmp = 1;
                    while(tmp*t <= M)
                    {
                        arr[tmp*t]++;
                        ++tmp;
                    }
                }
        }
}

int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    init();
    int n, m;
    while(scanf("%d%d",&n,&m) != EOF){
        int pos = 0;
        int Max = 0;
        for(int i=n; i<=m; i++){
            if(arr[i] > Max){
                Max = arr[i];
                pos = i;
            }
        }
        printf("%d %d\n",pos, Max);
    }
    return 0;
}

Tanky Woo原创，转载请注明：转载自Tanky Woo
文章标题: 勾股数公式
本文链接地址: http://www.wutianqi.com/?p=1632

posted @ 2010-12-03 11:19 Tanky Woo 阅读(5945) | 评论 (2) | 编辑收藏

一些计算机编程的经典书籍总结（大家一起来补充！）

（最后更新时间：2010.11.26 11点16分）

这个帖子原本是在C++奋斗乐园论坛讨论的，后来觉得有必要和更多朋友分享下，所以就在这里也贴出来了，希望大家一起补充。

因为我个人学的是C/C++的，所以JAVA等程序语言的书籍我就不讨论了。
这里讨论的主要是C/C++的经典书籍，另外还有计算机专业要学的一些重要课程领域的书，大家一起来补充吧！

我相信经过大家的补充，这篇帖子一定可以帮助许多学C/C++和计科专业学生。

格式是：书名+豆瓣链接(最好给出分类)

因为我很多书我也没看过，所以希望大家能给出书的分类，若我对书的分类有误，请大家提出，谢谢。

（希望大家把下面的推荐多点下，别让这个文章沉下去了。谢谢）

C/C++：
《C程序设计语言》http://book.douban.com/subject/1139336/
《C Primer Plus》http://book.douban.com/subject/1319751/
《C陷阱与缺陷》http://book.douban.com/subject/2778632/
《C与指针》http://book.douban.com/subject/3012360/
《C专家编程》http://book.douban.com/subject/2377310/
《编程珠玑》 http://book.douban.com/subject/1910326/
《C++ Primer》http://book.douban.com/subject/1767741/

《C++ Primer Plus》http://book.douban.com/subject/1319751/

《C++程序设计语言》http://book.douban.com/subject/1099889/

《Effective C++》http://book.douban.com/subject/1842426/

《More Effective C++》http://book.douban.com/subject/1453373/

《深度探索C++对象模型》http://book.douban.com/subject/1091086/

《STL源码剖析》http://book.douban.com/subject/1110934/

《C++标准程序库》http://book.douban.com/subject/1110941/

数据结构与算法：
《数据结构(C语言版)》严蔚敏 http://book.douban.com/subject/2024655/
《数据结构与算法分析》 http://book.douban.com/subject/1971825/
《算法导论》：http://book.douban.com/subject/1885170/

《计算机算法的设计与分析》http://book.douban.com/subject/1683278

Windows 编程
《Windows程序设计》http://book.douban.com/subject/1088168/
《Windows核心编程》http://book.douban.com/subject/1088045/
《深入浅出MFC》http://book.douban.com/subject/1482240/
《VC++深入详解》http://book.douban.com/subject/1835449/

操作系统：
《计算机的心智:操作系统之哲学原理》http://book.douban.com/subject/3670621/
《现代操作系统（第2版）》http://book.douban.com/subject/1390650/
《自已动手写操作系统》http://book.douban.com/subject/1422377/
《深入解析Windows操作系统》http://book.douban.com/subject/2031396/
《深入理解计算机系统》 http://book.douban.com/subject/1230413/

《操作系统设计与实现(第三版)》 http://book.douban.com/subject/2044818/

数据库：
数据库系统概论(第四版) http://book.douban.com/subject/1945005/

计算机网络：
计算机网络作者: （美）特南鲍姆 http://book.douban.com/subject/1179807/
《TCP/IP详解》共三卷
http://book.douban.com/subject/1088054/
http://book.douban.com/subject/1087767/
http://book.douban.com/subject/1058634/

软件工程：

《人月神话》 http://book.douban.com/subject/2230248/
《重构:改善既有代码的设计》http://book.douban.com/subject/2989411/
《敏捷软件开发：原则、模式与实践》 http://book.douban.com/subject/2347793/
《企业应用架构模式》 http://book.douban.com/subject/4826290/

其他：
《设计模式：可复用面向对象软件的基础》http://book.douban.com/subject/1099305/

Tanky Woo原创，转载请注明：转载自Tanky Woo
文章标题: 一些计算机编程的好书
本文链接地址: http://www.wutianqi.com/?p=1596

posted @ 2010-11-25 18:57 Tanky Woo 阅读(4037) | 评论 (13) | 编辑收藏

一个简单的文本查询程序—摘至《C++ Primer》

摘要: 这是在《C++ Primer》上第十章最后的一个小节。以前把这里漏掉了，刚才看了下，觉得这个程序很不错，便于对vector, map, set的基本掌握。特地把这一个小程序记录下来。 /* *目的：一个简单的文本查询程序 *作用：程序将读取用户指定的任意文本文件，然后允许用户从该文件中查找单词。 *查询的结果是该单词出现的次数，并列出每次出现所在的行。 *... 阅读全文

posted @ 2010-11-11 20:16 Tanky Woo 阅读(2660) | 评论 (4) | 编辑收藏

霍纳法则(Horner Rule)

霍纳法则(Horner Rule)，是一个比较常用的法则，但是网上关于这个的相关资料不是很多，我主要找到了两个。
1.http://blog.csdn.net/lwj1396/archive/2008/07/18/2669993.aspx

2.http://flynoi.blog.hexun.com/31272178_d.html
在第二篇文章里讲到了霍纳法则出现的原因：为多项式求值提供了一个高效的方法。
“对于多项式求值问题，我们最容易想到的算法是求出每一项的值然后把所求的值累加起来，这种算法的时间和空间效率都不高，对于数据规模不大的题目来说由于其直观、简单很容易被大家采纳，可一旦数据规模过大时，这种算法就显得无能为力了”

这个算是比较详细的霍纳法则概念了：
假设有n＋2个实数a0，a1，…，an,和x的序列，要对多项式Pn(x)= anxn ＋an－１xn－１＋…＋a１x＋a０求值，直接方法是对每一项分别求值，并把每一项求的值累加起来，这种方法十分低效，它需要进行n＋(n－1)＋…＋1＝n(n＋１)/2次乘法运算和n次加法运算。有没有更高效的算法呢?答案是肯定的。通过如下变换我们可以得到一种快得多的算法，即Pn(x)= anxn ＋an－１xn－１＋…＋a１x＋a０＝((…(((anx ＋an－１)x＋an－２)x+ an－3)…)x＋a1)x＋a０，这种求值的安排我们称为霍纳法则。

在这里我写了一个霍纳法则的小程序：

// Author: Tanky Woo
// blog: www.WuTianQi.com
#include <iostream>
using namespace std;

// Calculate the value of an*x^n + an-1*x^(n-1) +

a2*x^2 + a1*x + a0
double HornerRule(double a[], int n, double x);

int main()
{
    double *a;
    int n;
    double x;

    cout << "Input the n (a0, a1, a2

an): ";
    cin >> n;

    a = new double[n+1];
    cout << "Input the a0, a1, a2,

, an (n+1 numbers): ";
    for(int i=0; i<=n; ++i)
        cin >> a[i];

    cout << "Input the x: ";
    cin >> x;

    for(int i=n; i>=0; --i)
    {
        if(i != n)
            cout << " + ";
        cout << a[i] << "*x^" << i;
    }
    cout << " = " << HornerRule(a, n, x) << endl;

    return 0;
}

double HornerRule(double a[], int n, double x)
{
    double res = 0.0;

    for(int i=n; i>=0; --i)
        res = x*res + a[i];

    return res;
}

posted @ 2010-11-11 16:10 Tanky Woo 阅读(6894) | 评论 (5) | 编辑收藏

汉诺塔,n皇后,跳马问题汇总

软件课讲了这些问题，这次顺便总结下。

说白了也就是：递归，回溯，深搜或者广搜。

1.汉诺塔

////////////////////////////////////////////////
/*
汉诺塔
题目：
假设有A, B, C 3个轴，有n个直径各不相同，
从小到大依次编号为1，2，3，…，n的圆盘
按照从小到大的顺序叠放在A轴上。现在要求
将这n个圆盘移至C轴上并仍然按照同样顺序
叠放，但圆盘移动时必须遵守下列规则：
1.每次只能移动一个圆盘，它必须位于某个
轴的顶部。
2.圆盘可以插在A,B,C中任一轴上。
3.任何时刻都不能将一个较大的圆盘压在较小
的圆盘之上。
*/
///////////////////////////////////////////////

经典的问题，属于递归的入门级问题，但是同样不好分析，在n<=4以内还可以模拟下汉诺塔的实现，当n>=5时就不太现实了，让我们来看看汉诺塔当圆盘个数n时有多少组解？按照传说来看：n=64,当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

但是这毕竟是神话，不过当把64个金片全部放到另外一根针时，确实要很长很长一段时间。
让我们来看看需要多长时间。
首先，我们找出递推关系：
f(n + 1) = 2*f(n) + 1
至于这个怎么得到的可以画图看看。
把递推关系算出来后，也就是:
f(n) = 2^n-1
那么当n=64时，是多少？
f(64)= 2^64-1=18446744073709551615 　　
假如每秒钟一次，共需多长时间呢？一年大约有 31536926 秒，计算表明移完这些金片需要5800多亿年，比地球寿命还要长，事实上，世界、梵塔、庙宇和众生都已经灰飞烟灭。

好吧，说了那么多，还是步入正题。

汉诺塔的实现有递归和非递归两种情况，递归的很常见，也很简单，非递归实际上就是二叉树的中序遍历。也可以认为是栈的实现。

递归的版本：

/*递归实现*/
#include <iostream>
using namespace std;

//把n号圆盘从x移到y，并打印出。
void Move(int n, char x, char y)
{
  cout<< "把" << n << "号圆盘从" << x << "移动到" << y << endl;
}

//把前n个通过b从a移到c
void Hanoi(int n, char a, char b, char c)
{
    if(n == 1)
        Move(1, a, c);
    else
    {
        Hanoi(n-1, a, c, b);
        Move(n, a, c);
        Hanoi(n-1, b, a, c);
    }
}

int main()
{
    int n;
    cout << "输入n的大小: ";
    cin >> n;
    Hanoi(n, 'a', 'b', 'c');
    cout << "Ok!" << endl << "By Tanky Woo." << endl;
    return 0;
}

非递归的版本有时间再补上。

2.n皇后

对于每一个ACMer,八皇后问题都是必经之路。

作为搜索类题目还是老问题：

1.边界条件。
2.对每种情况都得遍历到，可以用解答树分析。
3.剪枝 http://www.wutianqi.com/?p=1341(搜索与剪枝)
4.辅助空间的变化。回溯前和回溯后的变化。
如果不用辅助空间的回溯当然就不需要注意辅助空间的问题了。

以下是n皇后的源码：

/*
*  n皇后问题
*  Tanky Woo
*/

#include <iostream>
using namespace std;

int queen[100];
int n;         // n皇后
int tot = 0;   //解法种数

// www.wutianqi.com
void search(int cur)
{
    if(cur == n)   //递归边界。符合要求，输出。
    {
        tot++;
        for(int i=0; i<n; ++i)
            cout << queen[i] << " ";
        cout << endl;
    }
    else
    {
        for(int i=0; i<n; ++i)
        {
            bool flag = 1;
            queen[cur] = i;    // 尝试把第cur行的皇后放在第i列
            for(int j=0; j<cur; ++j)    // 检查是否和前面的皇后冲突
                if(queen[cur] == queen[j]        // 同一列
                || cur-queen[cur] == j-queen[j]    // 正对角线
                || cur+queen[cur] == j+queen[j])   // 反对角线
                {
                    flag = 0;
                    break;
                }
            if(flag)
                search(cur+1);    // 如果合法，继续
        }
    }
}

int main()
{
    cout << "输入皇后个数n: ";
    cin >> n;
    search(0);
    cout << "共有" << tot << "种解." << endl << "By Tanky Woo." << endl;
    return 0;
}

对于这个问题，还可以用辅助空间来提高算法的效率: 增加辅助空间vis[][]来判断是否有其他皇后已经在列和对角线上。

#include <iostream>
using namespace std;

int queen[100];
int n;         // n皇后
int tot = 0;   //解法种数

int vis[3][100];   // 辅助空间
void search(int cur)
{
    if(cur == n)   //递归边界。符合要求，输出。
    {
        tot++;
        for(int i=0; i<n; ++i)
            cout << queen[i] << " ";
        cout << endl;
    }
    else
    {
        for(int i=0; i<n; ++i)
        {
            if(!vis[0][i] && !vis[1][cur+i] && !vis[2][cur-i+n])
            {
                queen[cur] = i;
                vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 1;
                search(cur+1);
                vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 0;  //记住要变化来
            }
        }
    }
}

int main()
{
    memset(vis, 0, sizeof(vis));
    cout << "输入皇后个数n: ";
    cin >> n;
    search(0);
    cout << "共有" << tot << "种解." << endl << "By Tanky Woo." << endl;
    return 0;
}

3.跳马问题：
据说此题证明可以用组合数学中的哈密顿环。
组合数学确实博大精深，看过一段时间的组合数学，感觉和实际联系的很多，Orz.
此题有两种版本：

①：给定一个N*N的棋盘，起始点在(0,0)处，要求求出有多少种方法，可以不重复的遍历棋盘上所有的点。
规则：1.马走日字
2.走过的点就不能再走了

此题和上面的n皇后类似，是标准的DFS。
分析：从起始点开始，每次遍历八种方向，直到边界条件，并输出。

以下是跳马问题一的源码：

/*马跳棋盘问题*/

#include <iostream>
using namespace std;
const int N = 10;
int a[N][N] = {0};
int cnt = 0;

void Horse(int a, int b, int t);
// www.wutianqi.com
int main()
{
    int i = 0, j = 0, t = 1;
    a[i][j] = t;
    Horse(i, j, step+1);
    cout << cnt << endl;
    cout << "By Tanky Woo.\n";
    return 0;
}
void Horse(int a, int b, int t)
{
    int x[4] ={-2, -1, 1, 2}, y[4] = {-2, -1, 1, 2};
    if(t == N*N+1)
        cnt++;

    for(int i=0; i<4; ++i)
        for(int j=0; j<4; ++j)
        {
            if(x[i]==y[j] || x[i]==-y[j])
                continue;
            if(a+x[i]>=0 && a+x[i]<N && b+y[j]>=0 && b+y[j]<N && board[a+x[i]][b+y[j]]==0)
            {
                a[a+x[i]][b+y[j]] = t;
                Horse(a+x[i], b+y[j], t+1);
                a[a+x[i]][b+y[j]] = 0;
            }
        }
}

第二个版本： ②：设有右图所示的一个棋盘，在棋盘上的A点，有一个中国象棋的马，并约定马走的规则：
规则：1. 马走日字
2. 马只能向右走。
试找出所有从A到B的途径。

此题也是OI上很有名的骑士问题。
此题似乎比较适合BFS.
还没尝试过。

让我再想想，好像还有八数码和素数环问题没写。
不过在HDOJ上遇到过一个素数环的题目：
http://www.wutianqi.com/?p=1329
有兴趣可以做下。

对于DFS和BFS更多的题目，可以在我博客右上角搜索栏里输入DFS或BFS，会出来相应题目。

posted @ 2010-09-30 15:24 Tanky Woo 阅读(2506) | 评论 (2) | 编辑收藏

线段树(区间树)Segment Tree

实际上还是称为区间树更好理解一些。
树：是一棵树，而且是一棵二叉树。
线段：树上的每个节点对应于一个线段(还是叫“区间”更容易理解，区间的起点和终点通常为整数)
同一层的节点所代表的区间，相互不会重叠。
叶子节点的区间是单位长度，不能再分了。

线段树是一棵二叉树，树中的每一个结点表示了一个区间[a,b]。a,b通常是整数。每一个叶子节点表示了一个单位区间。对于每一个非叶结点所表示的结点[a,b]，其左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2,b](除法去尾取整）。

线段树的基本用途：
线段树适用于和区间统计有关的问题。比如某些数据可以按区间进行划分，按区间动态进行修改，而且还需要按区间多次进行查询，那么使用线段树可以达到较快查询速度。

线段树的构建

   createSeg   //以节点v为根建树、v对应区间为[l,r]
{
    对节点v初始化
     if (l!=r)
    {
        以v的左孩子为根建树、区间为[l,(l+r)/2]
        以v的右孩子为根建树、区间为[(l+r)/2+1,r]
    }
}

(浏览器似乎不太好用了，上面的代码点“插入代码”不管用，就直接贴出来了)

个人感觉线段树比较灵活，要多做一些题目才能对线段树有一个大概的掌握。
网上看见了一些线段树的资料，这里也贴出来。

线段树的一种简化实现
http://www.cnitblog.com/cockerel/archive/2006/09/13/16806.html

线段树(区间树)Segment Tree

http://www.wutianqi.com/?p=1140

http://www.wutianqi.com/?p=1369

线段树基础知识
http://hi.baidu.com/lemon_cn/blog/item/2093b64bd63797f682025c9f.html

线段树的构造过程
http://kmplayer.javaeye.com/blog/576486

RMQ问题以及ST算法
http://hi.baidu.com/wjn123335/blog/item/4d485a08414c5ed362d9868a.html

数据结构 – 线段树
http://www.cnblogs.com/superbin/archive/2010/07/17/1779842.html
http://www.cnblogs.com/superbin/category/253674.html
http://www.cnblogs.com/superbin/archive/2010/08/02/1790467.html

线段树模版
http://www.cppblog.com/NicYun/archive/2008/08/05/58037.html

线段树
http://blog.chinaunix.net/u3/102500/showart_2257428.html

下一篇我会贴出树状数组的讲解。

posted @ 2010-09-25 14:08 Tanky Woo 阅读(4450) | 评论 (0) | 编辑收藏

我的新博客

我的独立博客：http://www.wutianqi.com/
希望大家支持。
谢谢

posted @ 2010-09-24 09:22 Tanky Woo 阅读(226) | 评论 (2) | 编辑收藏

字典树（讲解+模版）

又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。

字典树与字典很相似,当你要查一个单词是不是在字典树中,首先看单词的第一个字母是不是在字典的第一层,如果不在,说明字典树里没有该单词,如果在就在该字母的孩子节点里找是不是有单词的第二个字母,没有说明没有该单词,有的话用同样的方法继续查找.字典树不仅可以用来储存字母,也可以储存数字等其它数据。

Trie的数据结构定义：

#define MAX 26
typedef struct Trie
{
    Trie *next[MAX];
    int v;   //根据需要变化
};

Trie *root;

next是表示每层有多少种类的数，如果只是小写字母，则26即可，若改为大小写字母，则是52，若再加上数字，则是62了，这里根据题意来确定。
v可以表示一个字典树到此有多少相同前缀的数目，这里根据需要应当学会自由变化。

Trie的查找（最主要的操作）：
(1) 每次从根结点开始一次搜索；
(2) 取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索；　　(3) 在相应的子树上，取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。　　
(4) 迭代过程…… 　　
(5) 在某个结点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。

这里给出生成字典树和查找的模版：

生成字典树：

void createTrie(char *str)
{
    int len = strlen(str);
    Trie *p = root, *q;
    for(int i=0; i<len; ++i)
    {
        int id = str[i]-'0';
        if(p->next[id] == NULL)
        {
            q = (Trie *)malloc(sizeof(Trie));
            q->v = 1;    //初始v==1
            for(int j=0; j<MAX; ++j)
                q->next[j] = NULL;
            p->next[id] = q;
            p = p->next[id];
        }
        else
        {
            p->next[id]->v++;
            p = p->next[id];
        }
    }
    p->v = -1;   //若为结尾，则将v改成-1表示
}

接下来是查找的过程了：

int findTrie(char *str)
{
    int len = strlen(str);
    Trie *p = root;
    for(int i=0; i<len; ++i)
    {
        int id = str[i]-'0';
        p = p->next[id];
        if(p == NULL)   //若为空集，表示不存以此为前缀的串
            return 0;
        if(p->v == -1)   //字符集中已有串是此串的前缀
            return -1;
    }
    return -1;   //此串是字符集中某串的前缀
}
对于上述动态字典树，有时会超内存，比如 HDOJ 1671 Phone List，这是就要记得释放空间了：

int dealTrie(Trie* T)
{
    int i;
    if(T==NULL)
        return 0;
    for(i=0;i<MAX;i++)
    {
        if(T->next[i]!=NULL)
            deal(T->next[i]);
    }
    free(T);
    return 0;
}

题目分析+解答报告：

HDOJ 1251 统计难题：
http://www.wutianqi.com/?p=1364

HDOJ 1671 Phone List
http://www.wutianqi.com/?p=1366

这里还有几个字典树的相关资料，我上传了RaySource里了，顺便和大家分享下：

算法合集之《浅析字母树在信息学竞赛中的应用》

字典树

posted @ 2010-09-24 09:17 Tanky Woo 阅读(2217) | 评论 (1) | 编辑收藏

搜索与剪枝

半年前在POJ上遇到过一次剪枝的题目，那时觉得剪枝好神秘。。。今天在网上查了半天资料，终于还是摸索到了一点知识，但是相关资料并不多，在我看来，剪枝是技巧，而不是方法，也就是说，可能一点实用的小技巧，让程序可以少判断一点，这就是剪枝，剪枝无处不在，

搜索的进程可以看作是从树根出发，遍历一棵倒置的树—-搜索树的过程。而所谓的剪枝，顾名思义，就是通过某种判断，避免一些不必要的遍历过程，形象的说，就是减去了搜索树中的某些“枝条”，故称剪枝。
(杭电课件上是这么说的：即剪去解答树上已被证明不可能存在可行解或最优解的子树.)

既然采用了搜索，剪枝就显得十分的必要，即使就简简单单的设一个槛值，或多加一两条判断，就可对搜索的效率产生惊人的影响。例如Ｎ后问题，假如放完皇后再判断，则仅仅只算到7，就开始有停顿，到了8就已经超过了20秒，而如果边放边判断，就算到了10，也没有停顿的感觉。所以，用搜索一般都就要剪枝。

剪枝至少有两方面，一是从方法上剪枝，如采用分枝定界，启发式搜索等，适用范围比较广；二是使用一些小技巧，这类方法适用性虽不如第一类，有时甚至只能适用一道题，但也十分有效，并且几乎每道题都存在一些这样那样的剪枝技巧，只是每题有所不同而已。

剪枝的原则：
1.正确性：必须保证不丢失正确的结果。
2.准确性：能够尽可能多的减去不能通向正解的枝条
3.高效性：在很多时候，为了加强优化的效果，我们会增加一些判断，这样对程序效率也带来了副作用，所以要考虑剪枝的高效性，否则得不偿失。

最后说一下：剪枝在搜索中用的是非常的广泛的。
（
参照杭电课件第47页一句话：
ACMer们：
为了ACM事业，努力地剪枝吧！！
）

题目我不多说，HDOJ 1010就是一个很好的剪枝题目。
HDOJ 1010解答：
http://www.wutianqi.com/?p=1345

另外，杭电的课件–搜索篇里面也讲了搜索与剪枝。

posted @ 2010-09-19 15:12 Tanky Woo 阅读(2136) | 评论 (0) | 编辑收藏

最小生成树(Minimum Spanning Tree)

原文链接：

http://www.wutianqi.com/?p=1284

给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树.

求最小生成树的算法
(1) 克鲁斯卡尔算法
图的存贮结构采用边集数组,且权值相等的边在数组中排列次序可以是任意的.该方法对于边相对比较多的不是很实用,浪费时间.
(2) 普里姆算法
图的存贮结构采用邻接矩阵.此方法是按各个顶点连通的步骤进行,需要用一个顶点集合,开始为空集,以后将以连通的顶点陆续加入到集合中,全部顶点加入集合后就得到所需的最小生成树 .

下面来具体讲下：
克鲁斯卡尔算法
方法:将图中边按其权值由小到大的次序顺序选取,若选边后不形成回路,则保留作为一条边,若形成回路则除去.依次选够(n-1)条边,即得最小生成树.(n为顶点数)

第一步:由边集数组选第一条边

第二步:选第二条边,即权值为2的边

第三步:选第三条边,即权值为3的边

第四步:选第四条边,即权值为4的边

第五步:选第五条边

普里姆算法
方法:从指定顶点开始将它加入集合中,然后将集合内的顶点与集合外的顶点所构成的所有边中选取权值最小的一条边作为生成树的边,并将集合外的那个顶点加入到集合中,表示该顶点已连通.再用集合内的顶点与集合外的顶点构成的边中找最小的边,并将相应的顶点加入集合中,如此下去直到全部顶点都加入到集合中,即得最小生成树.
例在下图中从1点出发求出此图的最小生成树,并按生成树的边的顺序将顶点与权值填入表中.

———————>先写出其邻接矩阵

第一步:从①开始，①进集合，用与集合外所有顶点能构成的边中找最小权值的一条边
①——②权6
①——③权1 -> 取①——③边
①——④权5