博文
我所理解的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......
约瑟夫环问题算法集锦(2008-12-05 12:41:00)
摘要：/*
Name: 约瑟夫环问题算法集锦
Copyright: 始发于goal00001111的专栏；允许自由转载，但必须注明作者和出处
Author: goal00001111搜集整理
Date: 03-12-08 18:14
Description:
有编号从1到N的N个人坐成一圈报数，报到M的人出局，下一位再从1开始， 如此持续，
直止剩下一位为止，报告此人的编号X。
输入N,M，求出X。
共搜集整理了7类10种算法，对于初学者和算法爱好者来说——看了绝对值！
*/
#include<iostream>
#include <time.h>
using namespace std;
int Fun_1(int n, int m);
int Fun_2(int n, int m);
int Fun_3(int n, int m);
int Fun_4(int n, int m);
int Fun_5(int n, int m);
int Fun_6(int n, int m);
int Fun_7(int n, int m);
int Fun_8(int n, int m);
int Fun_9(int n, int m);
int Fun_10(int n, int m);
int main(int argc, char* argv[])
{
int n, m;
//cout << "Input max, step: ";
// cin >> n >> m;
time_t startTime;
time_t endTime;
time(&star......
杨辉三角算法集锦(2008-11-27 19:18:00)
摘要：/*
Name: 杨辉三角算法集锦
Copyright: 始发于goal00001111的专栏；允许自由转载，但必须注明作者和出处
Author: goal00001111
Date: 27-11-08 19:04
Description:
分别使用了二维数组，一维数组，队列，二项式公式，组合公式推论和递归方法等9种算法
算法思路详见代码注释——注释很详细，呵呵
*/
#include<iostream>
#include<iomanip>
using namespace std;
const int MAXROW = 40;
void PrintBlank(int n);
int Com(int n, int m);
int Try(int row, int cel);
void Fun_1(int row);
void Fun_2(int row);
void Fun_3(int row);
void Fun_4(int row);
void Fun_5(int row);
void Fun_6(int row);
void Fun_7(int row);
void Fun_8(int row);
void Fun_9(int row);
int main()
{
int row;
cin >> row;
Fun_1(row);
cout << endl;
Fun_2(row);
cout << endl;
Fun_3(row);
&nb......
有序全排列生成算法(2008-11-21 14:10:00)
摘要：有序全排列生成算法
作者：goal00001111（高粱） 写本文的动力来自一个NOI题目：输出n个数的第m种全排列。
输入两个自然数m,n 1<=n<=20，1<=m<=n!
输出n个数的第m种全排列。
要解决这个问题，必须要生成有序的全排列。
生成n个
数字的全排列是算法学习中的一个经典案例，也是信息学奥赛中的一个常考内容，值得我们去深入研究。生成全排列的算法很多，大概分类有直接模拟法，设置中介
数法和数学分析法（这是我杜撰的一个名称），其中直接模拟法又可以分为递归和非递归模拟。设置中介数后，更是可以分为字典序全排列生成法，递增进位排列生
成算法，递减进位排列生成算法和循环左移排列生成算法等类别。此外还有邻位对换法和邻元素增值法等另类生成方法。利用这些算法生成的全排列，有些是有序全
排列，有些却是无序的，本文主要探讨有序全排列。
在上面列举的算法中，字典序全排列生成法和邻元素增值法，以及我杜撰的数学分析法可以生成有序全排列，即可以输出n个数的第m种全排列。其中字典序全排列
生成法根据是否设置中介数又可以分为两类，不用设置中介数的方法即直接模拟法。
我
们首先来看最简单的递归直接模拟法。这是普通递归方法的一个改进。普通的递归方法是利用将当前数组左界元素与其右侧的元素交换位置来实现排列，这样得到的
全排列是无序的。所以我们不能直接调换位置，而是将左界右侧的元素顺序右移，不破坏原排列的顺序，保证右侧元素的递增性。
为了回答本文开头提出的问题，我们统一设置一个接口void Permutation(long long n, long long
m);其中n表示共n个自然数，m表示第m种全排列。
在子程序中我们先创建一个数组a[n]来存储n个自然数，然后递归查找并输出n个数的第m种全排列。下面是主要的代码：（完整的代码附在文章后面，下同）
/*
函数名称：Permutation
函数功能：输出n个数的第m种全排列
输入变量：long long n：1，2，3，...，n共n个自然数（1<=n<=20） long long
m：第m种全排列（1<=m<=n!） 输出变量：无 */
void Permutation(long long n, long long m)// 递归直接模拟法......
凯撒密码(2008-10-25 20:37:00)
摘要：/*
Name:
Copyright:
Author:
Date: 25-10-08 20:34
Description:
凯撒密码（caeser）是罗马扩张时期朱利斯o凯撒（Julius Caesar）创造的，用于加密通过信使传递的作战命令。
它将字母表中的字母移动一定位置而实现加密。注意26个字母循环使用，z的后面可以堪称是a。
凯撒密码的加密算法极其简单。其加密过程如下：
在这里，我们做此约定：明文记为m，密文记为c，加密变换记为E(key1,m)（其中key1为密钥），
解密变换记为D(key2,m)（key2为解密密钥）（在这里key1=key2,不妨记为key）。
凯撒密码的加密过程可记为如下一个变换：c≡m+key (mod n） （其中n为基本字符个数）
同样，解密过程可表示为：m≡c+key (mod n） （其中n为基本字符个数）
*/
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;
bool ReadFile(vector<string> & article, char * fileName);
bool WriteFile(const vector<string> & article, char * fileName);
void Encrypt(const vector<string> & proclaimedInWriting, vector<string> & cryptograph, int key);
void Decode(const vector<string> & cryptograph, vector<string> & proclaimedInWritin......
模运算及其应用(2008-10-25 11:59:00)
摘要：
模运算及其应用
goal00001111搜集整理
摘要：模运算在数论和程序设计中应用很广泛，从奇偶数的判别到素数的判别，从模幂运算到最大公约数的求法，从孙子问题到凯撒密码问题，无不充斥着模运算的身影。本文从模运算的概念，性质，到模运算的基本应用，较为全面的介绍了模运算及其编程方法。
关键词：模运算 程序设计
应用
模运算在数论和程序设计中都有着广泛的应用，从奇偶数的判别到素数的判别，从模幂运算到最大公约数的求法，从孙子问题到凯撒密码问题，无不充斥着模运算的身影。虽然很多数论教材上对模运算都有一定的介绍，但多数都是以纯理论为主，对于模运算在程序设计中的应用涉及不多。本文以c++语言为载体，对基本的模运算应用进行了分析和程序设计，以理论和实际相结合的方法向大家介绍模运算的基本应用。。
一 基本理论：
基本概念：
给定一个正整数p，任意一个整数n，一定存在等式 n = kp + r
；
其中k、r是整数，且 0 ≤ r < p，称呼k为n除以p的商，r为n除以p的余数。
对于正整数p和整数a,b，定义如下运算：
取模运算：a % p（或a mod p），表示a除以p的余数。
模p加法：(a + b) % p ，其结果是a+b算术和除以p的余数，也就是说，(a+b) = kp +r，则(a + b) % p = r。
模p减法：(a-b) % p ，其结果是a-b算术差除以p的余数。
模p乘法：(a * b) % p，其结果是 a * b算术乘法除以p的余数。
说明：
1. 同余式：正整数a，b对p取模，它们的余数相同，记做 a ≡ b % p或者a ≡ b (mod p)。
2. n % p得到结果的正负由被除数n决定,与p无关。例如：7%4 = 3， -7%4 = -3， 7%-4 = 3， -7%-4 = -3。......
二进制在数学中的妙用(2008-06-15 16:39:00)
摘要：
二进制在数学中的妙用
goal00001111搜集整理
十八世纪初，莱布尼茨发明了二进制数，当时的他肯定没有预料到二进制在信息时代会有着如此广泛的应用。二进制数以其工作可靠，运算简单，逻辑严密，容易实现等特点，成为了计算机的专用语言。在计算机科学和大量应用数学领域中，二进制记数法是必不可少的。在趣味数学方面，同样也有广泛的应用。
让我们先来看一个经典的数学趣题：
一工人工作7天，老板有一段黄金，每天要给工人1/7的黄金作为工资，老板只能切这段黄金2刀，请问怎样切才能每天都给工人1/7的黄金？
这题不简单吧？小心别把脑子都想破了。
在给出答案之前，先让我们看另一个简单的例子：
用天平称1~63克整数克重的物品，至少要配备几只多重的砝码（砝码只能放在天平的一端）？
没有学过二进制的人是很难想到答案的，可是如果你知道二进制数，那就不难了。我们知道二进制中只有0和1两个数字，它的各位数字的权值从小到大依次为2^0，2^1，2^2，2^3，。。。。我们用一个数的每位数字乘以其权值所得到的乘积之和来表示这个数。对于一个具有8位的二进制数来说，它可以表示的数据范围是0~2^8。
63 = 2^6 – 1 =
2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5
所以，我们只需配备2^0 =1，2^1 = 2，2^2 = 4，2^3 = 8，2^4 = 16，2^5 = 32五种不同克数的砝码各一个。
类似的题目还有如何装苹果：
现有一笔出售苹果的生意，已知客人可能需要的苹果数量肯定是1个到1000个之间，但不知道具体数字。客人要求必须全部用他提供的箱子装整箱（每个箱子都最多可以装1000个苹果），箱子一旦装成就无法再拆开重装。
你手中有1000个苹果，10个箱子，客人需要的苹果数量未知，问怎么装才能满足客人的需要？
解题的原理和上题是一样的，都是利用二进制数的记数原理。因为1000 < 2^10 = 1024，所以只要使用2^0，2^1，2^2，2^3，2^4，2^5，2^6，2^7，2^8，2^9十个数，就可以表示1到1023之间的所有数。
例如：30 = 2^1 +......
我学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，实现上述自定义函数。
//---------------------------------------------------------------------------......