博文
贪心算法::启发式搜索（转贴自rickone的blog)(2005-10-05 14: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);
&nb......
COM书籍链接(2005-10-05 13:55:00)
摘要：
http://blog.vckbase.com/teacheryang/category/114.html?Show=All......
学C++时要注意的（从985837的帖子拷贝过来）(2005-10-05 13:46:00)
摘要：下面的是学C++时要注意的。绝对经典。！！
1.把C++当成一门新的语言学习（和C没啥关系！真的。）；
2.看《Thinking In C++》，不要看《C++变成死相》；
3.看《The C++ Programming Language》和《Inside The C++ Object
Model》,不要因为他们很难而我们自己是初学者所以就不看；
4.不要被VC、BCB、BC、MC、TC等词汇所迷惑——他们都是集成开发环境，而我们要学的是一门语言；
5.不要放过任何一个看上去很简单的小编程问题——他们往往并不那么简单，或者可以引伸出很多知识点；
6.会用Visual C++，并不说明你会C++；
7.学class并不难，template、STL、generic
programming也不过如此——难的是长期坚持实践和不遗余力的博览群书；
8.如果不是天才的话，想学编程就不要想玩游戏——你以为你做到了，其实你的C++水平并没有和你通关的能力一起变高——其实可以时刻记住：学C++是为了编游戏的；
9.看Visual C++的书，是学不了C++语言的；
10.浮躁的人容易说：XX语言不行了，应该学YY；——是你自己不行了吧！？
11.浮躁的人容易问：我到底该学什么；——别问，学就对了；
12.浮躁的人容易问：XX有钱途吗；——建议你去抢银行；
13.浮躁的人容易说：我要中文版！我英文不行！——不行？学呀！
14.浮躁的人容易问：XX和YY哪个好；——告诉你吧，都好——只要你学就行；
15.浮躁的人分两种：a)只观望而不学的人；b)只学而不坚持的人；
16.把时髦的技术挂在嘴边，还不如把过时的技术记在心里；
17.C++不仅仅是支持面向对象的程序设计语言；
18.学习编程最好的方法之一就是阅读源代码；
19.在任何时刻都不要认为自己手中的书已经足够了；
20.请阅读《The Standard C++ Bible》(中文版：标准C++宝典)，掌握C++标准；
21.看得懂的书，请仔细看；看不懂的书，请硬着头皮看；
22.别指望看第一遍书就能记住和掌握什么——请看第二遍、第三遍； ......
如何创建一个集合的幂集(2005-10-05 13:30:00)
摘要：void PowerSet(List a, List b)
{
if(a.IsEmpty())
{
Output(b);
}
else
{
Element e = RemoveHead(&a);
InsertHead(&b, e); // 元素e放入超集
PowerSet(a, b);
RemoveHead(&b); // 元素e不放入超集
PowerSet(a, b);
}
}
......
如何使应用程序只能创建一个实例(2005-10-05 13:29:00)
摘要：作者：qq590240
1.利用互斥句柄
AppName = "test";
HANDLE m_hMutex = CreateMutex(NULL, FALSE, AppName);
// 检查错误代码
if (GetLastError() == ERROR_ALREADY_EXISTS)
{
// 如果已有互斥量存在则释放句柄并复位互斥量
CloseHandle(m_hMutex);
m_hMutex = NULL;
// 程序退出
return FALSE;
}
2.利用FindWindow()
BOOL IsRun (LPSTR szClassName=NULL, LPSTR szCaption=NULL)
{
HWND Hwnd;
Hwnd = FindWindow (szClassName,szCaption); //通过类名和程序标题查找
if ((int)Hwnd > 0)
//如找到则(int)Hwnd > 0.这是以前写的比较傻.可以写成if(Hwnd).如果没发现程序就会返回NULL
{
ShowWindow (Hwnd,SW_RESTORE); //将程序Restore
SetForegroundWindow (Hwnd); //将程序提到最前
return TRUE;
}
return FALSE;
} ......
在一个函数中求最大最小值(2005-10-05 13:27:00)
摘要：// 本算法比1.5n次的比较次数的算法略快
void MaxMin(int values[], int n, int &max, int &min)
{
int i;
max = values[0];
min = values[0];
for(i=1; i<n; ++i)
{
if(values[i] > max)
{
max = values[i];
}
else if(values[i] < min)
{
min = values[i];
}
}
}......
在一个函数中求最大最小值，要求比较次数为1.5n次(2005-10-05 13:25:00)
摘要：void MaxMin(int *values, int n, int &max, int &min)
{
int nHalf = n>>1;
int i;
// 通过n/2次交换，使得前半部分总体上小于后半部分，
// 即最小值肯定在前半部分，最大值肯定在后半部分
for(i=0; i<nHalf; ++i)
{
if(values[i] > values[i+nHalf])
Swap(values[i], values[i+nHalf]);
}
// 如果n为奇数，则最后剩下一个没有比较，
// 这时让它与第一个比较，如果比第一个更小，则交换，否则不动，作为最大的部分
if( (n&1) != 0)
{
if(values[0] < values[n-1])
Swap(values[0], values[n-1]);
}
// 在前半部分找最小值
min = values[0];
for(i=1; i<nHalf; ++i)
{
if(values[i] < min)
min = values[i];
}
// 在前半部分找最大值
max = values[nHalf];
for(i=nHalf+1; i<n; ++i)
{
if(values[i] > max)
max = values[i];
}
}
......
顺序栈的模板类定义(2005-09-27 15:19:00)
摘要：/////////////////////////////////////////////////////////////////////////
// Definition of class CStack //
// CStack.h //
////////////////////////////////////////////////////////////////////////////
const int INITSIZE = 100;
const int INCREMENT= 10;
template <class T>
class CStack
{
public:
CStack()
{
entry = new T[INITSIZE];
assert(entry);
nSize = INITSIZE;
nTop = -1;
}
CStack(int nInitSize)
{
entry = new T[nInitSize];
assert(entry);
nSize = nInitSize;
nTop = -1;
}
~CStack()
{
if(entry != NULL)
{
delete []entry;
}
nSi......
八皇后问题的非递归写法(2005-09-26 22:06:00)
摘要：int x[SIZE]; // 某一行上皇后的放置位置
int up_free[2*SIZE-1]; // 斜列是否空闲
int down_free[2*SIZE-1];// 斜行是否空闲
int col_free[SIZE]; // 列是否空闲
// 求解（国际象棋）皇后问题
// i － 当前的行号
// n － 总的皇后数
void Queen(int n)
{
int i, j;
Stack st;
Element elem;
InitStack(&st);
// 初始位置入栈
elem.x = 0;
elem.y = -1;
Push(&st, elem);
while(!IsStackEmpty(st))
{
Pop(&st, &elem); // 弹出上一行的皇后位置
i = elem.x;
j = elem.y;
/* 恢复原状 */
if(j != -1)
{
x[i] = 0;
col_free[j] = TRUE;
up_free[i+j] = TRUE; /* 向上的斜列 */
down_free[i-j+n-1] = TRUE; /* 向下的斜列 */
}
找出1到1000内 能被7或11整除 但不能被7和11同时整除的数(2005-09-20 11:42:00)
摘要：#include <stdio.h>
#include <assert.h>
void Find(int *a, int *n)
{
assert(a != NULL && n != NULL);
int i;
int nCount=0;
for(i=7; i<1000; i+=7)
{
if(i%11 != 0)
a[nCount++] = i;
}
for(i=11; i<1000; i+=11)
{
if(i%7 != 0)
a[nCount++] = i;
}
*n = nCount;
}
// 下面是根据网友留言重新更改的函数，循环次数减少10％左右，但由于没有使用除法运算，所以整体速度提升了好几倍
void Find1(int *a, int *n)
{
assert(a != NULL && n != NULL);
int i, j;
int nCount=0;
int temp;
for(i=0; i<=1000/77; ++i)
{
temp = 77 * i;
for(j=1; j<7; ++j)
{
a[nCount++] = temp+7*j;
a[nCount++] = temp+11*j;
}
for(j=7; j<11; ++j)
a[n......