博文
我所理解的KMP算法（二）(2009-05-10 22:10:00)
摘要：三．更好理解的失效函数
接下来我们看看另一些常见的失效函数表示方法。
在严蔚敏和吴伟民编著的《数据结构（C语言版）》（清华大学出版社）一书中，采用了一种比较简单的失效函数表示方法。它的定义与前面讲的失效函数差不多，只是把上述的四种情况简化为三种情况，将②和③合并为同一种类型，即若P[0…k-1] == P[j-k…j-1]，其中0 < k < j，则failure[j] = k，而不论P[k] 是否等于 P[j]。这样模式串P中就只有failure[0] = -1了，失效函数表示方法得到了简化——当然效率稍微有所降低。
采用这种失效函数表示方法，在求解失效函数时，可以利用简单的递推，根据failure[j]来得到failure[j+1]。
原理如下：
先给出两个概念：若存在0
<= k < j，且使得P[0…k] ==
P[j-k…j]的最大整数k，我们称P[0…k]为串P[0…j]的前缀子串，P[j-k…j]为串P[0…j]的后缀子串。
从failure[j]的定义出发，计算failure[j]就是要在串P[0…j]中找出最长的相等的前缀子串P[0…k]和后缀子串P[j-k…j]，这个查找的过程实际上仍是一个模式匹配的过程，只是目标和模式现在是同一个串P。
我们可以用递推的方法求failure[j]的值。
设已有failure[j] = k，则有0 < k < j，且P[0…k-1] == P[j-k…j-1]。接下来：
若P[k] == P[j]，则由failure[j]的定义可知failure[j+1] = k + 1 =
failure[j] + 1；
若P[k] != P[j]，则可以在前缀子串P[0…k]中寻找使得P[0…h-1] == P[k-h…k-1]的h，这时存在两种情况：
① 找到h，则由failure[j]的定义可知failure[k] = h，故P[0…h-1] == P[k-h…k-1] == P[j-h…j-1]，即在串P[0…j]中找到了长度为h的相等的前缀子串和后缀子串。
这时若P[h] == P[j]，则由failure[j]的定义可知failure[j+1] = h + 1 =
failure[k] + 1 = f......
我所理解的KMP算法（一）(2009-05-10 22:03:00)
摘要：
我所理解的KMP算法
作者：goal00001111（高粱）
始发于goal00001111的专栏；允许自由转载，但必须注明作者和出处
一．简单字符串模式匹配算法的缺陷
设有目标串T(target)和模式串P(pattern)，模式匹配是指在目标串T中找到一个与模式串P相等的子串。模式匹配成功是指在目标串T中找到了一个模式串P。
简单字符串模式匹配算法（也就是BF算法）的基本思想是：从目标串T的起始比较位置pos开始（在后面的案例中，我们默认pos = 0），和模式串P的第一个字符比较之，若匹配，则继续逐个比较后继字符，否则从串T的下一个字符起再重新和串P的字符比较之。依此类推，直至串P中的每个字符依次和串T中的一个连续的字符序列（即匹配子串）相等，则称匹配成功，返回该匹配子串的首字符下标；否则成匹配不成功，返回-1。
BF算法的思想很直接，也很容易理解，其时间复杂度为O（lenT*lenP），其中lenT和lenP分别为串T和串P的长度。
我们先给出代码，再做简要分析：
/*
函数名称：BFIndex
函数功能：简单字符串模式匹配算法，若目标串T中从下标pos起存在和模式串P相同的子串，则称匹配成功，返回第一个匹配子串首字符的下标；否则返回-1。
输入参数：const string & T ：目标串T
const string & P
：模式串P
int pos &nb......
我学c++Builder系列(7)(2008-05-25 15:14:00)
摘要：
10，由系统给出正确答案
算法思路：当你希望获取更多的解或者更快的得到答案的话，就可以使用这个功能。我采用穷举的方法，让计算机列出参与运算的数字和符号的各种排列方式，并按照基本运算原则进行计算，最后详细分析了出现括号的各种情况，并以规定的格式进行输出。
新建一个Unit文件“UnitAnswer”，打开UnitAnswer.h，加入如下代码：
//---------------------------------------------------------------------------
#ifndef UnitAnswerH
#define UnitAnswerH
#include <vcl.h>
//穷举法列出参与运算的数字的各种排列方式
void CunShuZi(int num[]);
//回溯法输出各个可能的正确答案
void CunFuHao(int xuhao);
//根据序号返回对应的运算符
char FuHao(int i);
//计算当前四则运算表达式，并返回计算结果
int JiSuan(void);
//记录正确答案到文本文件中
void Print(int n);
//---------------------------------------------------------------------------
#endif
然后切换到UnitAnswer.cpp，实现上述自定义函数。
//---------------------------------------------------------------------------
#pragma hdrstop
#include "UnitAnswer.h"
//-----------------------------------------------------------------------......
我学c++Builder系列(6)(2008-05-25 15:13:00)
摘要：8，计算表达式结果
算法思路：此游戏的难点是如何将一个字符串形式的表达式解析成计算机能计算的算术表达式。我们的想法是按照数学四则运算法则，先去掉括号，然后按照先乘除后加减的顺序计算。
按照这种思路，我们必须解决如何寻找匹配的符号，如何寻找算术符号两边的数字，如何定位第一个算术符号的位置等问题。
新建一个Unit文件“UnitComputer”，打开UnitComputer.h，加入如下代码：
//---------------------------------------------------------------------------
#ifndef UnitComputerH
#define UnitComputerH
#include <vcl.h>
//定位第一个算术符号的位置，如果没有算术符号，则返回0
int AnyFirstPos(String str);
//定位最后一个算术符号的位置，如果没有算术符号，则返回0
int AnyLastPos(String str);
//返回最先出现的算术符号
char AnyFirstF(String str);
//计算不带()号的四则运算,先乘除，后加减
int SubCompute(String str);
//计算带()号的四则运算表达式
int TotalCompute(String str);
//---------------------------------------------------------------------------
#endif
然后切换到UnitComputer.cpp，实现上述自定义函数。
//---------------------------------------------------------------------------......
我学c++Builder系列(5)(2008-05-25 15:12:00)
摘要：三，添加事件处理：
1， 窗体的构造函数：
先在UnitMain.h中增加两个私有属性int ColorData[4];和int SpendTime;分别用来存储扑克牌图片信息和用户花费的时间。
然后切换到UnitMain.cpp中，在窗体Form1的构造函数中，加入下列代码，用于初始化变量和组件：
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
ZeroMemory(ColorData, 0);
SpendTime = 0;
}
2，“开始”按钮的OnClick事件处理
功能：点击“开始”按钮时，系统随机地发出四张纸牌，显示在四个Image组件中。并将“开始”按钮文字改变为“重新开始”。
代码：
void __fastcall TForm1::Button1Click(TObject *Sender)
{
randomize();
for (int i=0; i<4; i++)
{
ColorData[i] = random(10) + 1; //随机给出扑克牌的点数
String FileName = "扑克牌图片\\dw_";
&......
我学c++Builder系列(4)(2008-05-25 15:02:00)
摘要：
速算24游戏
作者：goal00001111
一，程序效果说明：
速算24游戏的规则是由系统发出4张扑克牌，要求用户利用扑克牌显示的数字，通过加减乘除运算得出24（可使用括号），为了计算方便，不会出现J,Q,K和王牌。
当启动应用程序后，程序界面如图1所示。
点击“开始”按钮，游戏开始，系统将发出4张扑克牌。这时游戏的界面如图2所示。
这时用户利用扑克牌显示的数字，通过加减乘除运算，以最快的速度得出24（可使用括号）。然后在文本框中写好表达式，接着点击“计算”按钮。这时系统会计算输入表达式的结果，并告诉用户答案是否正确。
如下图所示分别是计算正确和错误的界面。
如果错了可以再次输入新的表达式，重复上一步。直到您的表达式正确，这时系统会恭喜你算对了。
游戏还可以计算用户花费的时间，并且能够判断用户的输入是否出现了错误和屏蔽一些不正确的输入，如字母和其他非法字符等等。
......
浅析OnKeyPress事件和OnKeyDown/OnKeyUp事件(2008-05-20 15:22:00)
摘要：
浅析OnKeyPress事件和OnKeyDown/OnKeyUp事件
OnKeyPress事件
OnKeyPress事件是在用户按下键盘上任何一个可打印的字符时发生，只有能接收键盘输入的组件才有OnKeyPress事件。我们常常利用OnKeyPress事件截取在编辑框和组合框组件中所输入的击键，还可以立即测试击键的有效性或在字符输入时对其进行一定的格式处理。
例如，在TEdit组件上捕获OnKeyPress事件，判断输入的是否是小写字母，如果是，将其转换为大写字母，代码如下：
void
__fastcall TForm1::Edit1KeyPress(TObject *Sender, char &Key)
{
if (Key >= 'a' && Key
<= 'z')
{
Key
+= 'A' - 'a';
}
}
将Key的值改变为0时可取消击键，这样一来对象便接收不到字符，我们可以利用这个特点来屏蔽某些字符。例如，有时候我们只允许用户输入数字，则加入如下代码：
void __fastcall TForm1::Edit1KeyPress(TObject *Sender, char &Key)
{
if
(Key < '0' || Key > '9')
{
Key
= 0;//取消刚才输入的字符
}
}
注意：OnKeyPress事件可以引用任何可打印的键盘字符，一个来自标准字母表的字符或少数几个特殊字符之一的字符与 CTRL 键的组合，以及 ENTER 或 BACKSPACE ......
C++builder组件属性详解（1）(2007-11-30 18:30:00)
摘要：C++builder组件属性详解
尽管C++Builder的组件种类繁多，每种组件又都有许多不同的属性，但是在这些众多的属性中有相当一部分是大多数组件所共有的。因此我们应当主要掌握这些共有组件。
在设计时设置属性一般是通过属性窗口来进行的。在属性窗口设置组件属性的操作步骤如下：
1） 打开相应对象的属性窗口。
2） 从属性列表中选定属性名称。
3） 在属性窗口的右列输入或选择新的属性值。
注意：有些属性在设置值右侧有…按钮，单击该按钮会出现相应的设置对话框，设置值需要在对话框中选定。
在代码中设置组件属性的方法是：
对象名称->属性名称 ＝ 设置值；
下面我们来介绍一些主要组件的主要属性。
窗体form的属性：
1．Caption：标题。是窗体和各种可视化控件的共有属性，用来指定窗体标题栏中的说明文字，默认与控件名相同，但程序员可以在对象监视器和代码中修改。
在代码中修改的格式为：Form->Caption = "da";// da表示程序员输入的标题。
通常，对于Windows系统中的多文档界面( MDI )应用程序，当主框架窗口中的子窗口以最大化显示的时候，应用程序的标题栏中显示的内容为“ - ”；当子窗口以非最大化窗口显示的时候，主框架窗口中只显示应用程序的名称，子窗口有自己的标题栏，其中显示该窗口打开的文件名。所以，当窗体的显示方式发生了改变后，应该立即改变标题栏中的内容。
2．Name：变量名。是窗体和所有控件的共有属性，系统给予其默认名字，但程序员可以在对象监视器修改，不要在代码中修改。
通常，应该在系统开发的设计阶段就将整个工程中所有窗体的名称确定，然后在编程阶段，根据设计文档修改窗体的Name属性。一般情况下，不要在程序运行期间通过代码修改Name属性。
3．Enabled：可操作性。决定了对象在运行时是否允许用户进行操作。
它是逻辑型：true表示允许用户操作并可对其操作作出响应；false表示禁止用户操作，此时对象呈灰色。
程序员可以在对象监视器和代码中修改属性Enabled。
在代码中修改的格式为：Form-> Enabled = da;// da可以是true或false。
4．Visible：可见性。决定了对象在运行时是否可见。
它也是逻辑型：true表示可见；false......
算法设计之分治法(4)(2007-10-09 10:52:00)
摘要：参考程序
1．常规算法，复杂度为O(N):
double Power(double x, unsigned int N)
{
double result = 1.0;
for (unsigned int i=0; i<N; i++)
result *= x;
return result;
}
折半算法（二分法），复杂度为O(logN):
double Power(double x, unsigned int N)
{
if (N == 0)
return 1.0;
double t = Power(x, N/2);
if (N % 2 == 0)
return t * t;
else
return t * t * x;
}
2．算法分析：在讲解枚举法时，我们讨论了如何用枚举法求解此题，但如果求解的精度进一步提高，使用枚举法就无能为力了，在此我们再一次讨论如何用二分法求解此题。
由题意知（i,i+1）中若有根，则只有一个根，我们枚举根的值域中的每一个整数x(-100≤x≤100),设定搜索区间[x1，x2]，其中x1=x，x2=x+1。若：
⑴f(x1)=0，则确定x1为f(x)的根；
⑵f(x1)*f(x2)<0，则确定根x在区间[x1，x2]内。
⑶f(x1)*f(x2)>0，则确定根x不在区间[x1，x2]内，设定[x2，x2+1]为下一个搜索区间；
若确定根x在区间[x1，x2]内，采用二分法，将区间[x1，x2]分成左右两个子区间：
左子区间......
算法设计之分治法(3)(2007-10-09 10:51:00)
摘要：例5 比赛安排（1996年全国青少年信息学（计算机）奥林匹克分区联赛高中组复赛试题）
设有2^n（n<=6）个球队进行单循环比赛，计划在2^n-1天内完成，每个队每天进行一场比赛，设计一个比赛安排，使在2^n-1天内每个队都与不同的对手比赛。例如n=2时的比赛安排为：
队
1
2
3
4
时间
比赛
1 – 2
3 – 4
第一天
1 – 3
2 – 4
第二天
1 – 4
2 – 3
第三天
分析：已知参加比赛的球队数x(x=2^n)，要设计一个比赛安排表。分析题目要求（单循环比赛的比赛规则），我们可以归纳出比赛安排表必须满足的条件：
①球赛需要在x-1天内完成。
②每个球队每天有且只能有一场比赛。
③任意两个球队必须进行过一场比赛，并且只能进行一场比赛。
当只有两个球队进行比赛时，比赛安排表的设计非常简单，只要让两个球队直接进行一场比赛就可以了。当不止两个球队时，我们可以将所有的球队分成两半。x个球队的比赛安排表就可以通过x/2个球队的比赛安排表来产生。这样递归地使用这种一分为二的方法对球队进行分割，直到只剩下两个球队。
日期\球队
1
2
3
4
5
6
7
8
2
2
1
4
3
6
5
8
7
3
3
4
1
2
7
8
5
6
4
4
3
2
1
8
7
6
5
5
5
6
7
8
1
2
3
4
6
6
5
8
7
2
1
4
3
7
7
8
5
6
3
4
1
2
8
8
7
6
5
4
3
2
1
如图，是一张8个球队的比赛安排表。其中第i行与第j列相交的数字a(i,j)表示第j个球队在第i-1天所遇到的对手。（表的第一行为8个球队的编......