博文
公历日期类(2005-06-15 16:43:00)
摘要：//file:date.h
#include<iostream.h>
class date
{
public:
date(){year=month=day=leapyear=pastdays=week=-1;};
date(int y,int m,int d);
int getweek(){return week;};
friend bool operator<(date& dt1,date& dt2);
friend long leapyearsbetween(date dt1,date dt2);
friend ostream& operator<<(ostream& out,date& dt);
friend long operator-(date dt1,date dt2);
date& operator+=(int days);
protected:
int year,month,day;
int leapyear,pastdays,week;
};
//file:date.cpp
#include<iomanip.h>
#include "date.h"
date::date(int y,int m,int d)
{
static int
r1[13]={0,31,28,31,30,31,30,31,31,30,31,30,31},
r2......
公历历法::星期算法(2005-06-12 18:24:00)
摘要：[原创]
【引】
《创世纪》
创世在宇宙天地尚未形成之前，黑暗笼罩着无边无际的空虚混饨，上帝那孕育着生命的灵运行其中，投入其中，施造化之工，展成就之初，使世界确立，使万物齐备。
上帝用七天创造了天地万物。这创造的奇妙与神秘非形之笔墨所能写尽，非诉诸言语所能话透。
第一日，上帝说：“要有光！”便有了光。上帝将光与暗分开，称光为昼，称暗为夜。于是有了晚上，有了早晨。
第二日，上帝说：“诸水之向要有空气隔开。”上帝便造了空气，称它为天。
……
第七日，天地万物都造齐了，上帝完成了创世之功。在这一天里，他歇息了，并赐福给第七天，圣化那一天为特别的日子，因为他在那一天完成了创造，歇工休息。就这样星期日也成为人类休息的日子。
“造化钟神秀，阴阳割分晓。”上帝就是这样开辟鸿蒙，创造宇宙万物的。
以上来自《圣经》，现在还有一些基督教徒每个礼拜天去教堂朝拜，可见一个星期七天就源于此，这正是我讨论的中心，如何计算哪年哪月哪日是星期几。
【公历历法】
公历历法很简单，年有润年（LeapYear）和平年之分，平年每月天数恒为：
月份 一 二 三 四 五 六 七 八 九 十 十一 十二
天数 31 28 31 30 31 30 31 31 30 31 30 31
共365天。润年366天，二月多一天，29天。
【润年判断】
如果年份数能被4整除但不能被100整除或者能被400整除者，为润年。
【400年刚好一个轮回】
很容易想到每400年内的润年数相等，即刚好一个轮回，400年有多少个润年？被4整除的有100个，被100整除的有4个，被400整除的只有1个，所以一共有100-4+1=97个润年，所以400年共有(365*400+97)天，即146097天，除7余0！
也就是说2001年1月1日的星期数与1年1月1日的星期数相同，翻出日历一看，星期一，我不知道上帝什么时候造的人，或许是1年1月1日。这样一来，任何一个日期我们都可以把它折算到0~399年之内的日期来算，0年的说法不准确，或许没有，但不影响这个数学结论，我们只是借它来推一推而已。
【起初的400年】
如果每一年都是平年，即365天，除7余1，也就是说如果不遇上润年，每往下一年就会使星期数增一。同样的道理，如果遇上润年，则多增一。我们要算的也就是把......
贪心算法::启发式搜索(2005-05-23 12:12:00)
摘要：蛮干算法的成功完全是借助于计算机运算的快速，如果问题的解比较少的时候使用起来是比较容易的。但当问题的解比较多，则不宜使用，常用的做法是剪枝，剪枝是一种形象的描述，因为按深搜的算法，图可以描述为与之对应的树或森林，而剪枝的意思就是去掉某些子树，为什么要去掉，这里要用到一个剪枝判断，判断的方法是具体问题具体分析，但是有一点是要考虑到的，剪枝的高效性是建立在判断的额外开销上的，如果这里的开销大，则剪枝只会宣告失败。
而更好的做法是运用“贪心策略”。
【贪心算法】
贪心算法（也叫贪婪算法）不是某种特定的算法，而是一类抽象的算法，或者说只是一种思想，它的具体表现在，对解空间进行搜索时，不是机械地搜索，而是对局部进行择优选取，贪心算法的目的不是为了找到全部解，也当然找不出最优解，而只是找出一种可行解，这样就会得到惊人的高效性。因此，贪心算法也叫启发式搜索，这种启发就是所谓的“贪心策略”。
以马踏棋盘问题为例，问题描述：在国际象棋的棋盘上指定一个初始马位置，一匹马从这个位置出发，经过不重复的走动，直到踏遍整个棋盘，输出一种可行路径。
对8×8的棋盘来说，马踏棋盘的解是一个天文数字，相当之多，而采用蛮干算法，求一个解的时候会非常吃力，因此采用贪心算法。这里选取的贪心策略是，在某个马位置顶点的后继顶点（子结点）中，择优选取那些出口更小的顶点进行搜索，出口的意思就是这个点能跳到的可行位置的路径数，这样的贪心策略是容易被人接受的，一开始往出口少的点跳，则往后出口多的点就多，能跳通的可能性就大，而事实也证明了，如果采用这样的策略在求一个解时几乎不需要回溯，对于更大的棋盘也如此。
C++代码：在（VC6上调试通过）
#include "stdio.h"
class horse
{
public:
horse(int,int);
~horse();
void solve(int,int);
protected:
void dfs(int,int,int);
int **data;
......
穷举搜索::回溯与深搜(2005-05-23 11:43:00)
摘要：计算机常用算法大致有两大类，一类叫蛮干算法，一类叫贪心算法，前者常使用的手段就是搜索，对全部解空间进行地毯式搜索，直到找到指定解或最优解。【建立解空间】问题的解应该如何描述，如何建立？借助图论的思想，我们可以用图来描述，图的定义为G<V,E>，由顶点集和边集构成，顶点即实实在在的数据、对象，而边可以抽象为关系，即顶点间的关系，这种关系不一定非要在数据结构上表现出来，用数据结构的语言来描述，如果关系是一对一，则为线性表，如果关系是一对多，则为树，如果关系是多对多，则为图，如果完全没有关系，则为集合。但在数据结构中这种关系不一定非要在数据的存储性质上一开始就表现出来，譬如，你可以用一个数组表示一个线性表，也可以表示完全二叉树，同样也可以用邻接表表示一个图，对于关系的描述不是数据结构本身的描述，而是算法的描述，正如数据结构是离不开特定的算法一样，不可分开单独而谈。描述了解，那如何建立解空间，即如何对图进行搜索？【深度优先搜索】(Depth First Search)是用栈的机制对图的顶点进行深度优先的搜索。简易流程如下：DFS(V0（起始顶点）)访问V0for(v=V0的第一个子结点 到 最后一个子结点（边所对的顶点）） 如果v未被访问，DFS(v);搜索过程是先往结点深处搜索，一旦有子结点未访问就向下遍历。这样的方法类似回溯算法，先往下试探，如果不行出退回（回溯）。【回溯】回溯的经典例子是8皇后问题。例：在国际象棋地图上（8×8）放上8个皇后，使任意两个皇后都不在同一行或同一列或同一斜行，找出所有解。每一个皇后的位置可以认为是一个顶点，而皇后之间不在同一行或同一列或同一斜行的性质认为是顶点之间的关系，我们可以用回溯试探的方法考虑：先依次试探每一个皇后的位置，如果有不满足条件的情况则退回，直到完成所有解的计数和输出。用数组存储：int pos[8];pos[0]表示第一个皇后的位置（0,1,...7)依次类推。流程：dfs(c)//c从0开始for(v=0;v<8;++v) 如果pos[c]:=v满足条件，dfs(c+1); 退回之后pos[c]:=0;这跟书上的回溯算法不太一样，因为是采用深搜的方法写的，其实思想是一致的，要仔细体会。
附N皇后C语言代码：/*p118.4*//*N Q......
排序由浅入深（二）::交换排序(2005-05-22 19:38:00)
摘要：【交换排序】
是一种主要以交换的方式对序列进行排序的方法。
其实排序的基本方法或手段主要就是比较和交换，像选择法等都借助了交换的手段，但都不是主要以交换为手段，在直接选择排序的时候，一轮比较就能确定最大元素的位置，然后再进行交换，也就是说这样的交换是“稳定”的。
【冒泡排序法】
也叫起泡排序法，过程跟气泡从水里冒出来类似。一轮交换对相邻元素进行比较，如果逆序则交换，作用只能使一个元素到达最终位置，而其它的交换是多余的，如果只进行比较而不交换的话，就跟直接选择排序法一样，不同的是，它是不稳定的。
void bubblesort(int n,list r)
{
for (i=1;i=n-1,i++)
{
flag=1;//标记是否有交换
for (j=1;j=n-1;j++)
if (r[j].key>r[j+1].key)
{
flag=0;
swap(r[j],r[j+1]);//交换相邻元素
}
if(flag)return;//如果一轮比较没有元素交换则说明整体有序，直接退出
}
}
【快速排序法】
也是一种交换排序法，实际上它是冒泡法的改进。
【算法】
思想是：一次划分使整个元素部分有序，即从序列中任选一个元素，然后对其它元素进行这样的划分，使得所有比它小（大）的元素在左侧而所有比它大（小）的元素在右侧，然后用分治的思想对左右侧的序列同样的处理，直到只有一个元素为止。
一次划分的算法如下：
int quickpass(list r,int low,int high)
{
int i=low; j=high; x=r[i]; //置......
排序由浅入深（一）::选择排序(2005-05-22 18:56:00)
摘要：【选择排序】
的思想是依次从待排序数列中选择最大（小）的、第二大（小）的等等，然后依次重新排列为有序数列。
以某个关键字（key）选一个最大（小）的元素出来，可以看成是一场比赛，就像拳击比赛，如果你能从第一局打到最后一局，那你就是最强者，我们选出这个最强者的过程就是选择的过程，选出来之后，将它标记，然后再从剩下的选手中以同样的方法（分治）选出第二强的，依次下去，直到只剩一个选手（边界）为止。这就是选择排序的全部思想方法。
①直接打擂的方式：（直接选择排序法）
直接选择排序法的算法是这样的，首先选出前n个元素中的最小（大）者，如果这个最小（大）者不是第1个元素，则与第1个元素交换，然后以同样的方法对付后n-1个元素（分治），直到处理的元素只剩一个，即得到有序序列。它和冒泡排序法很类似，不同的是冒泡排序法进行了更多次的交换，而有些交换是不必要的，这使得冒泡排序法是不稳定的，而直接选择排序法是稳定的排序法。
②锦标赛的方法：（树型选择法）
玩过拳皇游戏的人就知道这种比赛方法，实际中的比赛可以不必要打这么多次，我们可以把n个选手分成n/2组，假定n=8，先分成4组，每组两人，两个人打一局，这样可以产生4个胜者，再将这4个人分2组，每组同样两人，各自再打一局，这样可以产生2个胜者，同样再做一次就能产生冠军。这样做的好处是强者可以只打几场就能坐上冠军的宝座，不像前一种方法，冠军要跟其它的人都打一场才能确定（当然，这是最糟的情况）。但是树型选择法最大的缺点是需要的存储空间要大，要建一个败者树，对n很大的情况不太理想。
③堆排序：
将前一种方法进一步改进，使得在O(1)的空间复杂度上就能完成的选择排序法，就是大名鼎鼎的“堆排序法”。堆是一个线性表，下标从1开始取，且满足：nk>=max{n2k,n2k+1}或者nk<=min{n2k,n2k+1}，前者称为大顶堆，后者称为小顶堆。这样看似乎不太明白，我们把堆转换成完全二叉树，它的特点就相当显然了。
【完全二叉树】
是这样一棵二叉树，我们以堆中的元素，从头取，先取1个，做为根，再取2个，做为它的左右子结点，再取4个做为下一层的子结点，依次下去就构成完全二叉树。它的前n-1层（n是它的总层数，称为深度）是一棵满二叉树（即所有非子叶的结点的的度都为2，饱满的意思），第n层的结点靠左对齐。
这样就可以简单的得到结点之......
分治的实现::递归程序设计(2005-05-23 21:33:00)
摘要：【分治算法】
是一种思想，你拿到的问题往往不会是很简单的事情，而再复杂再难的问题都可以分解成一些有限的简单问题的和，这就是分治法的原理。
举个最简单的例子，计算阶乘之和n!+(n-1)!+...+1!：
n可以取大取小，问题的范围可以大可以小，如果小就比较容易，比如1！=1这是己知，如何将大问题化成小问题，找它们之间的联系：
如果n=k已经解决，那么n=k+1能否解决，如何解决？
很显然：n=k+1的情况就是将n=k的结果加上(k+1)!的值。
【递归程序设计】
是一种算法常用设计方法，在高级语言中，函数之间可以进行嵌套调用，用栈的机制实现，这样的做法可以使我们在算法设计的时候能够达到套调算法设计。
int facsum(int n)
{
if(n==1)return 1;
return fac(n)+facsum(n-1);
}
/*fac()为求阶乘函数，facsum()为阶乘求和函数*/
“if(n==1)return 1;”为小问题、简单问题解的直接描述，在递归中称为递归边界，没有设定边界的递归是只能‘递’不能‘归’的，即死循环。
“return fac(n)+facsum(n-1);”中将n的范围缩小：n-1，以此将大问题化为类似的小问题，类似很重要，如果不类似就不能调同一个函数，这很显然。——这样一个过程就是分治算法的实现。
[阶乘求和可以用更高效率的算法求解，以上只是做为一个简单例子]
再举一例，将数组的元素逆置：
void inverse(int a[],int n)
{
if(__①__)return;
swap(a[0],a[n-1]);/*swap(a,b)为交换a,b的值*/
inverse(__②__);
}
①处为小问题解描述，也是递归边界，怎样的小问题是很显然的呢？当数组的元素个数小于2时是不需要逆置的，所以填：n<2
②交换之后进行递归，分解成小问题，两端的已经交换，所以往中间靠，所以填：a+1,n-2
这样的问题有很多很多，如拆半法查找，用二分法求方程的根等等。都离不开两点：1、小问题的描述，即递归边界，2、将大问题化成小问题。
拆半法查找的小问题是：low==high；二分法求根的......