周恒（zhouheng1212 ）的窝！(粗体字文章别删)

zhouheng1212

内容有些多而且杂了。

[ 本帖最后由 zhouheng1212 于 2006-8-15 16:08 编辑 ]

zhouheng1212

标  题: 皮克定理证明zz
发信站: 逸仙时空 Yat-sen Channel (Sat Aug 12 13:07:16 2006), 转信

寄信人: kelefe (O_O)
标  题: 皮克定理zz
发信站: 逸仙时空 Yat-sen Channel (Sat Aug 12 11:48:22 2006)
来  源: 124.29.56.45

奥地利数学家皮克(Georg Pick，1859---1943年)发现了一个计算点阵中多边形面
积的公式:
S＝N＋ L/2 －1   其中多边形面积S，内部格点数N，边上格点数L

相关习题:ZOJ1032或POJ1265(同一个题)


（一）  皮克公式
一张方格纸上，上面画着纵横两组平行线，相邻平行线之间的距离都相等，这样
两组平行线的交点，就是所谓格点。
如果取一个格点做原点O，如图1，取通过这个格点的横向和纵向两直线分别做横
坐标轴OX和纵坐标轴OY，并取原来方格边长做单位长，建立一个坐标系。这时前
面所说的格点，显然就是纵横两坐标都是整数的那些点。如图1中的O、P、Q、M、
N都是格点。由于这个缘故，我们又叫格点为整点。
（图1） （图2）
一个多边形的顶点如果全是格点，这多边形就叫做格点多边形。有趣的是，这种
格点多边形的面积计算起来很方便，只要数一下图形边线上的点的数目及图内的
点的数目，就可用公式算出。
那么格点与面积间有什么公式呢？下面我们一起看看怎样寻求这公式。
我们要借助一个简单的例子--寻求格点多边形的面积和格点数之间的精确关系--
通过特殊的情形归纳出一般的公式。
为简单起见，假定每个小方格的边长d＝1。首先选择面积和格点数容易计算的格
点多边形作为具体例子,加以讨论。例如边长是1或2的格点正方形(图2的OABC和O
PQR),两腰是1的格点三角形(图2中的OAB),一腰是1,一腰是2的格点三角形(图2中
的OPC),边长是2和4的格点矩形(图2中的OLMR)。我们把它们的面积S,内部格点数
N和边上格点数L,列成一表如下:
图形  S   N   L   S－N  L/2
OABC  1   0   4   1   2
OPQR  4   1   8   3   4
OAB   1/2   0   3  1/2   3/2
OPC   1   0   4   1   2
OLMR  8   3   12  5   6
看过上表的前四列，我们可能感到很失望，S，N，L之间几乎看不出有什么联系来
，不过，我们在前面已经看到，当S很大时，S和N的差(相对地说)是很小的。因此
，我们在表上添了一列，包含S-N的值，这列数字是随着L增大而增大的。如果用
2去除L，列到最后一列，我们立刻得到下面的有趣的关系:
S－N＝ L/2 －1
即
          S＝N＋ L/2－1 ………………………………（1）

也就是说,
（格点数N）＋ （ ）与 面积S的差恰好是1。
公式（1）是我们从五个特例归纳出来的，它到底是正确的还是巧合呢？下面我们
一起来验证一下。
     (图3)
  像寻求公式的时候那样，我们在思索一个公式的证明时，也可以先从简单的特
殊情形想起。现在我们就先考虑两边平行于坐标轴的格点矩形ABCD，如图（3）。
假定这矩形的长宽分别是m和n。容易从图3看出，这时，面积S，内部的格点数N和
边上的格点数L分别是

S＝mn,
N＝(m－1)(n－1),          ……………………（2）
L＝2(m＋1)＋2(n－1)＝2(m＋n).

（最后一式中，2（m＋1）是上下两边的格点数，2（n－1）是左右两边除去顶点
以外的格点数。）
  因此，
N＋ L/2 －1＝(m－1)(n－1)＋(m＋n)－1＝mn＝S。
这表明公式（1）对于矩形是成立的。
  有了矩形作基础，我们就不难讨论两腰分别和两坐标轴平行的格点直角三角形
，例如上图中的△BCD或△ABD。由图形的对称性，容易看出△BCD和△ABD的面积
，内部格点数和边上格点数都是分别相等的。（事实上，如果把矩形ABCD绕它的
中心即对角线的交点旋转180°，那么△ABD就和△CDB重合，而且格点也都一一重
合起来了。）如果用L1表示BD线段内部的格点数（即不包含端点的格点数），那
么，除去这L1个格点以后，矩形内部的格点就平均分配在△BCD和△ABD的内部。
又前面已经算出，矩形内部的格点数是(m－1)(n－1)，所以这两个三角形内部都
有
N＝ ((m-1)(n-1)-L1)/2
个格点。又容易看出，这两个三角形边上的格点数都是L＝m＋1＋n＋L1，
而面积显然都是
   S＝ mn/2
因此
   N＋ L/2 = ((m-1)(n-1)-L1)/2 ＋(m+n+1+L1)/2＝ mn/2 ＋1 ＝ S＋1

这表明公式（1）对于两腰平行于坐标轴的格点直角三角形是正确的。
现在我们进一步讨论一般的格点三角形。
（图4）
△ABC是一个三角形，如图4，方格纸上通过三顶点的直线围成一个矩形ALMN。三
角形ALB，BMC，CNA都是直角三角形，因此都满足公式（1）。现在把图中四个三
角形的面积，内部格点数和边上格点数，分别用不同的记号表示出来，列成下表
:
三角形  面积  内部格点数  边上格点数
△ABC  S    N      L
△ALB   S1   N1     L1
△BMC   S2   N2     L2
△CNA   S3   N3     L3
利用前面所得到的关于矩形面积和格点的公式（2），由图4容易看出

       S＋S1 ＋S2 ＋S3＝mn，
       N＋N1 ＋N2 ＋N3 ＋L－3＝(m－1)(n－1)，    （3）
       L＋L1 ＋L2 ＋L3 －2L＝2(m＋n)

顺次用1，-1，-1/2 乘（3）式的三个式子，然后相加，就得到

S－（N＋L/2）＋[S1－（N1＋L1/2）]＋[S2－（N2＋L2/2）]＋[S3－（N3＋L3/2）]＋3
＝﹣1

我们已经知道公式（1）对于直角三角形是成立的，因此，上式中有方括号的各项
都等于-1。所以由上式得
S－（N＋ L/2）＝﹣1。
这表明对于格点三角形，公式（1）是正确的。
  最后，讨论一般的具有n个顶点的格点多边形A1A2…An，如图5所示,我们可以
用数学归纳法证明。当n＝3时，公式（1）已经证明。现在假定该公式对于n－1边
形成立，要证明公式（图5）      对于n边形也成立。联结An－1
A1，我们就把这个n边形分成一个格点三角形和一个n－1边格点多边形。

zhouheng1212

标  题: 傅立叶变换的源程序
发信站: 逸仙时空 Yat-sen Channel (Wed Apr 19 13:30:18 2000), 站内信件

发信人: pinacle (Elton), 信区: Programming
标  题: Re: 谁有傅立叶变换的原程序！急需！！！！
发信站: BBS 水木清华站 (Thu Jul 22 10:10:28 1999)


#include<stdio.h>
#include<math.h>
#include<float.h>
#include<malloc.h>
#include<stdlib.h>
void initial(int num_data, float* real, float* inm);
void enter_data(int num_data, float* data);
void wave_sin(int num_data, float* data);
void wave_cos(int num_data, float* data);
void decay(int num_data, float* data);
void random(int num_data, float* data);
void table(int num_data, char flag,
   float* tablesin, float* tablecos);
void DFT(int num_data, char flag, float* real, float* img,
float* tablesin, float* tablecos);
float period;
void main()
{
int num_data;
int i;
char flag;
float *real, *img;
float *tablecos, *tablesin;
printf("PLEASE INPUT SAMPLE PERIOD(Second):");
scanf("%f", &period);
printf("PLEASE INPUT SAMPLE POINT NUMBER:");
scanf("%d", &num_data);
fflush(stdin);
printf("DFT OR IDFT (D/I):");
flag=getchar();
if(flag=='d') flag='D';
if(flag=='i') flag='I';
printf("\n");
real=(float*)malloc(sizeof(float)* num_data);
img=(float*)malloc(sizeof(float)* num_data);
tablesin=(float*)malloc(sizeof(float)* num_data);
tablecos=(float*)malloc(sizeof(float)* num_data);
initial(num_data, real, img);
table(num_data, flag, tablesin, tablecos);
DFT(num_data, flag, real, img, tablesin, tablecos);
for(i=0; i<num_data; i++)
  printf("%8d real=%12.6f img=%12.6f\n",
  i, real[i], img[i]);
free(real);
free(img);
free(tablesin);
free(tablecos);
}
void initial(int num_data, float* real, float* img)
{
int n;
for(n=0; n<num_data; n++)
{
  real[n]=0;
  img[n]=0;
}
printf("INITIAL REAL DATA\n");
enter_data(num_data, real);
printf("\nINITIAL IMG DATA\n");
enter_data(num_data, img);
}
void enter_data(int num_data, float* data)
{
int selection;
printf("FUNCTION SELECTION\n");
printf("1-----AMPLITUDE*SIN(2*3.1415926
  *FREQUENCY*PERIOD*T)\n");
printf("2-----AMPLITUDE*COS(2*3.1415926
  *FREQUENCY*PERIOD*T)\n");
printf("3-----AMPLITUDE*EXP(-PERIOD)\n");
printf("4-----DATA=0\n");
printf("5-----ENTER DATA\n");
printf("ENTER SELECTION---");
scanf("%d", &selection);
switch(selection)
{
case 1:wave_sin(num_data, data);break;
case 2:wave_cos(num_data, data);break;
case 3:decay(num_data, data);break;
case 4:break;
case 5:random(num_data, data);break;
}
}
void wave_sin(int num_data, float* data)
{
float amplitude, frequency, c;
int n;

printf("PLEASE INPUT AMPLITUDE OF WAVE:\n");
scanf("%f", &amplitude);
printf("PLEASE INPUT FREQUENCY OF WAVE(Hz):\n");
scanf("%f", &frequency);
for(n=0; n<num_data; n++)
{
  c=2*3.1415926*frequency*period*n;
  data[n]=(float)(amplitude*sin(c));
}
}
void wave_cos(int num_data, float* data)
{
float amplitude, frequency, c;
int n;
printf("PLEASE INPUT AMPLITUDE OF WAVE:\n");
scanf("%f", &amplitude);
printf("PLEASE INPUT FREQUENCY OF WAVE(Hz):\n");
scanf("%f", &frequency);
for(n=0; n<num_data; n++)
{
  c=2*3.1415926*frequency*period*n;
  data[n]=(float)(amplitude*cos(c));
}
}
void decay(int num_data, float* data)
{
float amplitude, c;
int n;
printf("PLEASE INPUT AMPLITUDE OF WAVE\n");
scanf("%f", &amplitude);
for(n=0; n<num_data; n++)
{
  c=-period*n;
  data[n]=(float)(amplitude*exp(c));
}
}
void random(int num_data, float* data)
{
int n;
for(n=0; n<num_data; n++)
{
  printf("PLEASE INPUT DATA[%d]:", n);
  scanf("%f", &data[n]);
}
}
void table(int num_data, char flag,
   float* tablesin, float* tablecos)
{
float w, c;
int n;
w=(float)(8*atan(1)/num_data);
if(flag=='D') w=-w;
for(n=0; n<num_data; n++)
{
  c=w*n;
  tablecos[n]=(float)cos(c);
  tablesin[n]=(float)sin(c);
}
}
void DFT(int num_data, char flag, float* img,
float* tablesin, float* tablecos)
{
int i, j, L;
float *result_r, *result_i;
result_r=(float*)malloc(sizeof(float)*num_data);
result_i=(float*)malloc(sizeof(float)*num_data);
for(i=0; i<num_data; i++)
{
  result_r[i]=0;
  result_i[i]=0;
  for(j=0; j<num_data; j++)
  {
L=i*j%num_data;
result_r[i]=result_r[i]+real[j]*tablecos[L]
  +img[j]*tablesin[L];
result_i[i]=result_i[i]+img[j]*tablecos[L]
  -real[j]*tablesin[L];
  }
}
if(flag=='D')
{
  for(i=0; i<num_data; i++)
  {
real[i]=result_r[i];
img[i]=result_i[i];
  }
}
else if(flag=='I')
{
  for(i=0; i<num_data; i++)
  {
real[i]=result_r[i]/num_data;
img[i]=result_i[i]/num_data;
  }
}
free(result_r);
free(result_i);
}

zhouheng1212

标  题: C语言的诡异(zz)
发信站: 逸仙时空 Yat-sen Channel (Fri Jun 20 11:27:49 2003), 转信


标题   C之诡谲（上）  wtong（原作）
关键字   ANSI C,指针，数组
C之诡谲(上)
从研究生二年纪开始学习计算机也差不多两年了，一路走来，有很多的收获，也有不少
的
遗憾，现在正好有一段闲暇，就想对走过的路留下一些足迹，回忆。每个人都有自己不
同
的人生，说到这里，就是程序人生了，歌德在《浮士德》中说过:“如果不曾在悲哀中
咀
嚼过面包，不曾在哭泣中等待过明天，这样的人就不知道你——天的力量。”所以我想
记下
一些带给我悲哀，带
给我哭泣的程序人生。其实学习计算机的基础课程是非常重要的，离散数学，编译原理
，
操作系统，形式语言……，如果你认真走过了这些路，在以后的日子你会发现你的路会
越
走越宽，以前的努力和汗水会不断的给你灵感，给你支持，给你前进的武器和勇气。你
会发
现以后取得的很多成
就，不过是朝花夕拾而已！
对于程序语言我喜欢的是C++，它能带给你别的语言无法给予你的无上的智力快感，当然

也会给你一门语言所能给你的魔鬼般的折磨。其实Java，C#，Python语言也非常的不错
，
我也极为喜欢。它们都是非常成功的语言，我从来就不愿意做某一种语言的盲目信仰者
，
每种语言都有它成功的地方，失败的地方，都有它适合的地方，不如意的地方。所以每
一次
看到评价语言的文章
，我看看，但从来不会发言。
C++的前世是C，而且C所留下的神秘以及精简在C++中是青出于蓝而胜于蓝！C所带给人的

困惑以及灵活太多，即使一个有几年经验的高段C程序员仍然有可能在C语言的小水沟里
翻
船。不过其实C语言真的不难，下面我想指出C语言中最神秘而又诡谲多变的四个地方，
它
们也继续在C++语言中变幻莫测。
指针，数组，类型的识别，参数可变的函数。
一.指针。
它的本质是地址的类型。在许多语言中根本就没有这个概念。但是它却正是C灵活，高效

，在面向过程的时代所向披靡的原因所在。因为C的内存模型基本上对应了现在von
Neumann（冯·诺伊曼）计算机的机器模型，很好的达到了对机器的映射。不过有些人似

乎永远也不能理解指针【注1】。
注1:Joel Spolsky就是这样认为的，他认为对指针的理解是一种aptitude，不是通过训

练就可以达到的。http://www.joelonsoftware.com/printerFriendly/articles/fog00
00
000073.html
指针可以指向值、数组、函数，当然它也可以作为值使用。
看下面的几个例子:
int* p;//p是一个指针，指向一个整数
int** p;//p是一个指针，它指向第二个指针，然后指向一个整数
int (*pa)[3];//pa是一个指针，指向一个拥有3个整数的数组
int (*pf)();//pf是一个指向函数的指针，这个函数返回一个整数
后面第四节我会详细讲解标识符（identifier）类型的识别。
1.指针本身的类型是什么？
先看下面的例子:int a;//a的类型是什么？
对，把a去掉就可以了。因此上面的4个声明语句中的指针本身的类型为:
int*
int**
int (*)[3]
int (*)()
它们都是复合类型，也就是类型与类型结合而成的类型。意义分别如下:
point to int（指向一个整数的指针）
pointer to pointer to int（指向一个指向整数的指针的指针）
pointer to array of 3 ints（指向一个拥有三个整数的数组的指针）
pointer to function of parameter is void and return value is int （指向一个函

数的指针，这个函数参数为空，返回值为整数）
2.指针所指物的类型是什么？
很简单，指针本身的类型去掉 “*”号就可以了，分别如下:
int
int*
int ()[3]
int ()()
3和4有点怪，不是吗？请擦亮你的眼睛，在那个用来把“*”号包住的“()”是多余的，

所以:
int ()[3]就是int [3]（一个拥有三个整数的数组）
int ()()就是int ()（一个函数，参数为空，返回值为整数）【注2】
注2:一个小小的提醒，第二个“()”是一个运算符，名字叫函数调用运算符（functio
n
call operator）。
3.指针的算术运算。
请再次记住:指针不是一个简单的类型，它是一个和指针所指物的类型复合的类型。因
此
，它的算术运算与之（指针所指物的类型）密切相关。
int a[8];
int* p = a;
int* q = p + 3;
p++;
指针的加减并不是指针本身的二进制表示加减，要记住，指针是一个元素的地址，它每
加
一次，就指向下一个元素。所以:
int* q = p + 3;//q指向从p开始的第三个整数。
p++;//p指向下一个整数。
double* pd;
……//某些计算之后
double* pother = pd – 2;//pother指向从pd倒数第二个double数。
4.指针本身的大小。
在一个现代典型的32位机器上【注3】，机器的内存模型大概是这样的，想象一下，内存

空间就像一个连续的房间群。每一个房间的大小是一个字节（一般是二进制8位）。有些

东西大小是一个字节（比如char），一个房间就把它给安置了；但有些东西大小是几个
字
节（比如double就是8个字节，int就是4个字节，我说的是典型的32位），所以它就需要
几
个房间才能安置。
注3:什么叫32位？就是机器CPU一次处理的数据宽度是32位，机器的寄存器容量是32位
，
机器的数据，内存地址总线是32位。当然还有一些细节，但大致就是这样。16位，64位
，
128位可以以此类推。
这些房间都应该有编号（也就是地址），32位的机器内存地址空间当然也是32位，所以
房
间的每一个编号都用32位的二进制数来编码【注4】。请记住指针也可以作为值使用，作

为值的时候，它也必须被安置在房间中（存储在内存中），那么指向一个值的指针需要
一
个地址大小来存储，即32位，4个字节，4个房间来存储。
注4:在我们平常用到的32位机器上，绝少有将32位真实内存地址空间全用完的（232 ＝

4G），即使是服务器也不例外。现代的操作系统一般会实现32位的虚拟地址空间，这样
可
以方便运用程序的编制。关于虚拟地址（线性地址）和真实地址的区别以及实现，可以
参
考《Linux源代码情景分析》的第二章存储管理，在互联网上关于这个主题的文章汗牛充

栋，你也可以google一下。
但请注意，在C++中指向对象成员的指针（pointer to member data or member
function）的大小不一定是4个字节。为此我专门编制了一些程序，发现在我的两个编译

器（VC7.1.3088和Dev-C++4.9.7.0）上，指向对象成员的指针的大小没有定值，但都是
4
的倍数。不同的编译器还有不同的值。对于一般的普通类（class），指向对象成员的指

针大小一般为4，但在引入多重虚拟继承以及虚拟函数的时候，指向对象成员的指针会增
大
，不论是指向成员数据，
还是成员函数。【注5】。
注5:在Andrei Alexandrescu的《Modern C++
Design》的5.13节Page124中提到，成员函数指针实际上是带标记的（tagged）unions，

它们可以对付多重虚拟继承以及虚拟函数，书上说成员函数指针大小是16，但我的实践
告
诉我这个结果不对，而且具体编译器实现也不同。一直很想看看GCC的源代码，但由于旁

骛太多，而且心不静，本身难度也比较高（这个倒是不害怕^_^），只有留待以后了。
还有一点，对一个类的static member来说，指向它的指针只是普通的函数指针，不是
pointer to class member，所以它的大小是4。
5.指针运算符&和*
它们是一对相反的操作，&取得一个东西的地址（也就是指针），*得到一个地址里放的
东
西。这个东西可以是值（对象）、函数、数组、类成员（class member）。
其实很简单，房间里面居住着一个人，&操作只能针对人，取得房间号码；
*操作只能针对房间，取得房间里的人。
参照指针本身的类型以及指针所指物的类型很好理解。
小结:其实你只要真正理解了1，2，就相当于掌握了指针的牛鼻子。后面的就不难了，
指
针的各种变化和C语言中其它普通类型的变化都差不多(比如各种转型)。

zhouheng1212

二.数组。
在C语言中，对于数组你只需要理解三件事。
1.C语言中有且只有一维数组。
所谓的n维数组只是一个称呼，一种方便的记法，都是使用一维数组来仿真的。
C语言中数组的元素可以是任何类型的东西，特别的是数组作为元素也可以。所以int
a[3][4][5]就应该这样理解:a是一个拥有3个元素的数组，其中每个元素是一个拥有4个

元素的数组，进一步其中每个元素是拥有5个整数元素的数组。
是不是很简单！数组a的内存模型你应该很容易就想出来了，不是吗？:）
2.数组的元素个数，必须作为整数常量在编译阶段就求出来。
int i;
int a;//不合法，编译不会通过。
也许有人会奇怪char str[] = “test”;没有指定元素个数为什么也能通过，因为编译
器
可以根据后面的初始化字符串在编译阶段求出来，
不信你试试这个:int a[];
编译器无法推断，所以会判错说“array size missing in a”之类的信息。不过在最新

的C99标准中实现了变长数组【注6】
注6:如果你是一个好奇心很强烈的人，就像我一样，那么可以查看C99标准6.7.5.2。
3.对于数组，可以获得数组第一个（即下标为0）元素的地址（也就是指针），从数组
名
获得。
比如int a[5]; int* p = a;这里p就得到了数组元素a[0]的地址。
其余对于数组的各种操作，其实都是对于指针的相应操作。比如a[3]其实就是*(a+3)的
简
单写法，由于*(a+3)==*(3+a)，所以在某些程序的代码中你会看到类似3[a]的这种奇怪
表
达式，现在你知道了，它就是a[3]的别名。还有一种奇怪的表达式类似a[-1]，现在你也

明白了，它就是*(a-1)【注7】。
注7:你肯定是一个很负责任的人，而且也知道自己到底在干什么。你难道不是吗？:）

所以你一定也知道，做一件事是要付出成本的，当然也应该获得多于成本的回报。
我很喜欢经济学，经济学的一个基础就是做什么事情都是要花成本的，即使你什么事情
也
不做。时间成本，金钱成本，机会成本，健康成本……可以这样说，经济学的根本目的
就
是用最小的成本获得最大的回报。
所以我们在自己的程序中最好避免这种邪恶的写法，不要让自己一时的智力过剩带来以
后
自己和他人长时间的痛苦。用韦小宝的一句话来说:“赔本的生意老子是不干的！”
但是对邪恶的了解是非常必要的，这样当我们真正遇到邪恶的时候，可以免受它对心灵
的
困扰！
对于指向同一个数组不同元素的指针，它们可以做减法，比如int* p = q+i;p-q的结果
就
是这两个指针之间的元素个数。i可以是负数。但是请记住:对指向不同的数组元素的指

针，这样的做法是无用而且邪恶的！
对于所谓的n维数组，比如int
a[2][3];你可以得到数组第一个元素的地址a和它的大小。*(a+0)（也即a[0]或者*a）就

是第一个元素，它又是一个数组int[3]，继续取得它的第一个元素，*(*(a+0)+0)（也即

a[0][0]或者*(*a)），也即第一个整数（第一行第一列的第一个整数）。如果采用这种
表
达式，就非常的笨拙，所以a[0][0]记法上的简便就非常的有用了！简单明了！
对于数组，你只能取用在数组有效范围内的元素和元素地址，不过最后一个元素的下一
个
元素的地址是个例外。它可以被用来方便数组的各种计算，特别是比较运算。但显然，
它
所指向的内容是不能拿来使用和改变的！
关于数组本身大概就这么多，下面简要说一下数组和指针的关系。它们的关系非常暧昧
，
有时候可以交替使用。
比如 int main(int args, char* argv[])中，其实参数列表中的char* argv[]就是
char**
argv的另一种写法。因为在C语言中，一个数组是不能作为函数引数（argument）【注8
】
直接传递的。因为那样非常的损失效率，而这点违背了C语言设计时的基本理念——作为

一门高效的系统设计语言。
注8:这里我没有使用函数实参这个大陆术语，而是运用了台湾术语，它们都是argumen
t
这个英文术语的翻译，但在很多地方中文的实参用的并不恰当，非常的勉强，而引数表
示
被引用的数，很形象，也很好理解。很快你就可以像我一样适应引数而不是实参。
dereferance，也就是*运算符操作。我也用的是提领，而不是解引用。
我认为你一定智勇双全:既有宽容的智慧，也有面对新事物的勇气！你不愿意承认吗？
:
）
所以在函数参数列表（parameter list）中的数组形式的参数声明，只是为了方便程序
员
的阅读！比如上面的char*
argv[]就可以很容易的想到是对一个char*字符串数组进行操作，其实质是传递的char*
字
符串数组的首元素的地址（指针）。其它的元素当然可以由这个指针的加法间接提领（

dereferance）【参考注8】得到！从而也就间接得到了整个数组。
但是数组和指针还是有区别的，比如在一个文件中有下面的定义:
char myname[] = “wuaihua”;
而在另一个文件中有下列声明:
extern char* myname;
它们互相是并不认识的，尽管你的本义是这样希望的。
它们对内存空间的使用方式不同【注9】。
对于char myname[] = “wuaihua”如下
myname
w
u
a
i
h
u
a
\0
对于char* myname；如下表
myname
\|/
w
u
a
i
h
u
a
\0
注9:可以参考Andrew Konig的《C陷阱与缺陷》4.5节。
改变的方法就是使它们一致就可以了。
char myname[] = “wuaihua”;
extern char myname[];
或者
char* myname = “wuaihua”;//C++中最好换成const char* myname = “wuaihua”。

extern char* myname;
(to be continued!)
吴桐写于2003.5.26
最近修改2003.6.16
作者相关文章:
auto_ptr_ref的奇妙（下）(原作)
auto_ptr_ref的奇妙（上）(原作)
行百里半九十(原作)
对该文的评论 人气:2937
  yeppie(2003-6-20 9:05:43)
下 怎么打不开？
  asdmonster(2003-6-20 9:04:50)
mark
  ys19811110(2003-6-20 8:59:27)
aptitude 这个词我理解为“天赋”
  wtong(2003-6-20 8:27:41)
Maxwell:谢谢你的不同声音，不过你发现没有，如果你经常对比看中英翻译的著作的时

候，会发现计算机中
    argument用的特别多，反而parameter用的比较少，在很多情况下，中文翻译将

argument翻译
    为“参数”，而不是“实参”，因为“实参”实在是很不顺口，它只有在和“
形
式参数”对比的时候，
    优势才突现出来，但是英文中这种对比比较少，以至于在很多情况下就让我误
解
这里的“参数”到达是
    argument还是parameter。你可以多看看中英文章对比。
    提领，我是这样想的，从一个指针中把值给提出来，很形象，当然这也是我个
人
的看法。每个人都
    有自己的观点。
    不过我想最重要的是:我们知道这个术语的原文和真实的意思，那是最重要的
。
gforceca1900 :因为我修改了《C之诡谲(下)》，而修改的文章又要通过CSDN审批，这
个
审批过程我认为比较
      官僚公式化，很慢。我想今天上午应该可以看到了，请耐性等一等。
      也可以指正一下我别的文章。Maxwell:谢谢你的不同声音，不过你发现

没有，如果你经常对比看中英翻译的著作的时候，会发现计算机中
    argument用的特别多，反而parameter用的比较少，在很多情况下，中文翻译将

argument翻译
    为“参数”，而不是“实参”，因为“实参”实在是很不顺口，它只有在和“
形
式参数”对比的时候，
    优势才突现出来，但是英文中这种对比比较少，以至于在很多情况下就让我误
解
这里的“参数”到达是
    argument还是parameter。你可以多看看中英文章对比。
    提领，我是这样想的，从一个指针中把值给提出来，很形象，当然这也是我个
人
的看法。每个人都
    有自己的观点。
    不过我想最重要的是:我们知道这个术语的原文和真实的意思，那是最重要的
。
gforceca1900 :因为我修改了《C之诡谲(下)》，而修改的文章又要通过CSDN审批，这
个
审批过程我认为比较
      官僚公式化，很慢。我想今天上午应该可以看到了，请耐性等一等。
      也可以指正一下我别的文章。Maxwell:谢谢你的不同声音，不过你发现

没有，如果你经常对比看中英翻译的著作的时候，会发现计算机中
    argument用的特别多，反而parameter用的比较少，在很多情况下，中文翻译将

argument翻译
    为“参数”，而不是“实参”，因为“实参”实在是很不顺口，它只有在和“
形
式参数”对比的时候，
    优势才突现出来，但是英文中这种对比比较少，以至于在很多情况下就让我误
解
这里的“参数”到达是
    argument还是parameter。你可以多看看中英文章对比。
    提领，我是这样想的，从一个指针中把值给提出来，很形象，当然这也是我个
人
的看法。每个人都
    有自己的观点。
    不过我想最重要的是:我们知道这个术语的原文和真实的意思，那是最重要的
。
gforceca1900 :因为我修改了《C之诡谲(下)》，而修改的文章又要通过CSDN审批，这
个
审批过程我认为比较
      官僚公式化，很慢。我想今天上午应该可以看到了，请耐性等一等。
      也可以指正一下我别的文章。
      http://www.csdn.net/Develop/list_article.asp?author= wtong。
  很高兴看到所有网友理性的赞成和反对！
  Maxwell(2003-6-20 3:26:47)
实参是实际使用时的参数，有什么勉强。
你那个引数，要是指针呢，字符串呢，不要告诉我它们存在存储器里都是数的形式。
要说到形象，提领怎么个形象法？
当然解引用或者反引用也不好，这个得承认，不过台湾的术语也好不到哪里去，所以我
们
倒是真需要宽容一下了。
  yqiong(2003-6-20 2:57:25)
非常感谢指教。
  gforceca1900(2003-6-20 1:09:56)
我一直以为理解c,非得到编译器和操作系统的层面上。
c的诡异，一半来自它的设计哲学:为了编译器的方便（效率），
    另一半是历史原因了（为了兼容，有时是很大的负担）。
    比如unix的历史，体现在linux上的就多多，庞大。
c 简单 又 复杂。
还有，（下）怎么点不亮？
  qeizi(2003-6-19 22:37:38)
thx for your help!
  yangq119(2003-6-19 20:42:50)
ds
  thinkinginlife(2003-6-19 18:01:05)
楼主的文章写得非常好，总结的非常到位。谢谢！
楼主那篇《行百里半九十》也写得非常好，看起来很爽！
  wtong(2003-6-19 16:55:18)
谢谢大家的欣赏，不过C语言本身的波诡云谲可能就这些了，跟C++比起来真是小巫见大
巫
！:）
我们的很多教科书早就应该淘汰了！
  oliverlin(2003-6-19 16:42:50)
helpful
thanks
  lato(2003-6-19 14:41:14)
int main(void)
{
&lt;%
  printf("%s\n", "说C不好，说C简单，都可以，关键是有没有资格。");
  &lt;:exit&lt;:0):&gt;
%&gt;
}
  _i_(2003-6-19 13:47:19)
这就是基础知识的作用。恭喜作者。穷究物理。
但好多东西书上没有讲，也讲不了。
许多代码海河人的个性有关，
  smandhgx(2003-6-19 13:00:41)
通俗易懂，好文章，希望继续努力
  dreamfly8848(2003-6-19 12:51:56)
it's good

zhouheng1212

标  题: LZW算法
发信站: 逸仙时空 Yat-sen Channel (Tue Oct 24 23:19:58 2000), 站内信件


[下面文章转自北京大学]

LZW压缩算法由Bob Montgomery发明，用来压缩/解压GIF格式的文件。

《压缩》
考虑用四种颜色（A，B，C，D）表示输入数据流的系统。我们
要建立一个编码表，其中编码用来表示颜色的字符串。每次我们发
现一个新的字符串，我们将会分配给它下一个编码码并且将它分为
前缀字符串和后缀颜色。符号\或者---代表前缀字符串，/代表后缀
颜色。表前四个表象是编码为0到3的4种颜色，每个代表一个单独
的颜色。下面2个编码（4和 5）是清除码和图象结束编码。第一
个被分配的用来表示颜色字符串的编码是6。每次我们找到一个
的编码，我们都将它的前缀放到输出数据流中。
A B A B A B A B B B A B A B A  A  C  D A C D A D  C A B A A A B A B .....
\/\/---/-----/\/---/-------/\/ \/ \ /\/---/---/\ /\/-----/---/---/
6 7 8   9 10 11  12 13 14 15 16  17 18 19 20 21  22  23   Code
  6  8  10  8      14  16    8  13  7   Prefix
编码表是由输入数据流构造的。每个编码都是由上个编码的后缀
开始，一直从输入中取颜色直到得到一个新的组合。
Color   Code  Prefix  Suffix  String  Output
A    0           -
B    1           -
C    2           -
D    3           -
Clear   4           -
End   5           -
A \      A   A       第一个颜色是种特殊情况。
B /  \ 6   A   B   AB    A
A |  / 7   B   A   BA    B
B |
A /  | 8   6   A   ABA   6
B  |
A  |
B \  / 9   8   B   ABAB  8
B /  | 10    B   B   BB    B
B  |
A |  / 11    10    A   BBA   10
B |
A |
B |
A /  \ 12    9   A   ABABA   9
A \  / 13    A   A   AA    A
C /  \ 14    A   C   AC    A
D \  / 15    C   D   CD    C
A /  | 16    D   A   DA    D
C  |
D |  / 17    14    D   ACD   14
A |
D /  \ 18    16    D   DAD   16
C \  / 19    D   C   DC    D
A /  | 20    C   A   CA    C
B  |
A  |
A |  / 21    8   A   ABAA  8
A |
B /  | 22    13    B   AAB   13
A  |
B  / 23    7   B   BAB   7
生成的输出流是:A B 6 8 B 10 9 A A C D 14 16 D C 8....。
GIF编码程序开始时，用2+1=3位长度对4色进行编码，所以当编码
到达8的时候我们必须将编码增长到4位。同样的，当编码到达16
的时候，我们将会将编码位数增长到5位。如果编码到达13位，
我们发送一个清除编码并且重新开始。GIFENCOD.GIF显示了编码
过程的流程图。其中使用了“树”的方法来查找是否新的字符串
已经在表种，这个方法比hash更加简单，速度更快，也更加
容易理解。

《解码》
  我们现在要看我们是不是可以只凭借前面介绍的编码程序
生成的输出数据流就可以。生成原始数据流且恢复编码表。
输出数据流是:
    A B 6 8 B 10 9 A A C D 14 16 D C 8 ....
  解码过程比起来编码过程不容易理解，不过容易实现。
输入被成对的取出，并且新的编码被赋给每一对。前缀是这个
对的左边，后缀是将对的右边按照表中信息展开后的颜色。展
开编码的步骤包括输出编码的后缀，使用前缀作为新的编码。
这个过程不断重复直到前缀是一个单一的颜色，然后它也被输
出。展开的输出被放到一个栈中，然后从栈中输出显示，这就
是编码程序看见的颜色的原始顺序。我们将会对开始几个编码
详细讲解，希望可以使您弄清楚解码的过程。
  第一个对是（A B），所以编码6的前缀是A并且后缀是B，
并且6代表字符串AB。A的颜色被送去显示。
  第二个对是（B 6），所以编码7的前缀是B并且后缀是6展
开形成的BA的最后一个颜色，所以编码7=BA，并且有一个后缀
A。颜色B被送去显示。
  第三个对是（6 8）。我们怎么展开8呢？我们知道8的前
缀是6，不过我们不知道后缀。答案是我们使用前缀编码的后缀
；这个例子中6的前缀是A，所以我们使用A。这样，编码8=ABA
并且有一个后缀A。我们将6展开得到BA，当我们将它从栈中弹
出的时候变成了AB用来显示。
  第四个对是（8 B），所以编码9前缀是8后缀是B，所以编
码9=ABAB。我们输出ABA到栈中，并且将它弹出输出ABA。
  第五个对是（B 10）并且下一个编码是10。编码10的前缀
是B，需要的后缀是B（因为前缀是B）。编码10=BB，并且我们
输出前缀B来显示。
  第六个对是（10 9）并且下个编码是11。所以编码11的前
缀是10，后缀是9的展开的最后一个颜色，A。这样，编码11=BBA，
并且我们输出BB来显示。
  到目前为止，我们已经输出了正确的颜色流A B AB ABA B BB，
并且已经恢复了编码表中的编码6到11。这个过程对整个数据流
不断重复来构造原始的颜色流，建造一个和编码程序中表格同样
的表格。这个表格由代表4色，清除编码，结束编码的编码0到5
开始。当我们到达编码8的时候，我们必须增长编码大小到5位。
GIFDICOD.GIF中显示了解码过程的流程图。
  我希望这篇文章可以解除LZW压缩算法的一些神秘之处，它
其实你看到就很容易明白的。

zhouheng1212

标  题: 灯塔问题
发信站: 逸仙时空 Yat-sen Channel (Mon Apr 24 19:22:44 2000), 站内信件

//灯塔问题
#include <iostream.h>
#include <fstream.h>
#include <conio.h>
int sz[11][11],cf=1,k,n,a[20],b[20],c[20];
void shuru(void);
void shuchu(void);
bool panduan(void);
void goujian(void);
void main()
{
    int i,j,lj=0,d;
    shuru();
for(i=1;i<=n;i++)cf=cf*2;
for(i=0;i<cf;i++)
{
    d=i;
    for(j=1;j<=n;j++)
    {sz[n][n-j+1]=d%2;d=d/2;}
    goujian();
    if(panduan()==true){lj=lj+1;shuchu();}
}
cout<<"共有"<<lj<<"种情况"<<endl;
getch();
}
void goujian(void)
{
    int i1,j1;
    for(i1=n-1;i1>0;i1--)
    {
for(j1=1;j1<=i1;j1++)
{
    if(sz[i1+1][j1]==1&&sz[i1+1][j1]==1)
        sz[i1][j1]=0;
    if(sz[i1+1][j1]==0&&sz[i1+1][j1+1]==0)
        sz[i1][j1]=0;
    if(sz[i1+1][j1]==1&&sz[i1+1][j1+1]==0)
        sz[i1][j1]=1;
    if(sz[i1+1][j1]==0&&sz[i1+1][j1+1]==1)
        sz[i1][j1]=1;
}
}
}
bool panduan()
{
    int pd=1,j1;
for(j1=1;j1<=k;j1++)
    if(sz[a[j1]][b[j1]]!=c[j1]) pd=0;
if(pd==0) return false;else return true;
}
void shuchu(void)
{
    int i2,j2;
for(i2=1;i2<=n;i2++)
{
    for(j2=1;j2<=n-i2;j2++) cout<<" ";
for(j2=1;j2<=i2;j2++) cout<<sz[i2][j2]<<" ";
cout<<endl;
    }
cout<<endl;
}
void shuru(void)
{
//    char filename[18];
ifstream input;
// cout<<"Input filename:";
// cin>>filename;
// input.open(filename);
input.open("dt.txt");
input>>n;
k=0;
do{
    k++;
input>>a[k]>>b[k]>>c[k];
}while((a[k]!=0)&&(b[k]!=0));
k--;
}

zhouheng1212

标  题: 迷宫问题
发信站: 逸仙时空 Yat-sen Channel (Fri Mar 30 00:29:28 2001), 站内信件


#include<stdlib.h>
#include<stdio.h>
#include<time.h>
#define max_len 30

class Maze{
public:
    /*constuctor*/
    Maze(int len){
      n=len;
      srand(unsigned int(time(0)));
      Initial();
    }
    /*print to screen*/
    void Print(){
      for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)
            if (v[i][j]==2)printf("◎");//path found
              else if (v[i][j]==1) printf("■");//no path
                else printf("  ");//null place
        printf("\n");
      }
      printf("\n");
    }
    /*output to file*/
    void OutToFile(char* file){
    }
    /*find a path to the maze*/
    void Find(){
      v[n-2][n-1]=2;
      move(1,0);
      v[n-2][n-1]=0;
      printf("Total path for this maze is %d\n",c);
    }
private:
    int n;/*total len for an n*n matrix*/
    int c;/*count of paths*/
    int v[max_len][max_len];/*ask for a max size space*/
    /*generate a maze*/
    void Initial(){
      //1.set the free space
      for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            v[i][j]=rand()%2;
      for(i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if (v[i][j]) v[i][j]=rand()%2;
    //2.set the edge of the maze
      for(i=0;i<n;i++){
        v[0][i]=1;
        v[n-1][i]=1;
        v[i][0]=1;
        v[i][n-1]=1;
      }
      //3.set the antrance and exit
      v[1][0]=v[n-2][n-1]=0;
      //4.set count of path to be zero
      c=0;
    }
    /*move to v[i][j] and set it to be 2*/
    void move(int i,int j){
      /*if out of the maze*/
      if (i<0 || j<0 || i>=n || j>=n)return;
      /*if the path found*/
      if ((i==n-2) && (j==n-1)) {c++;Print();return;}
      /*if the place has been taken or no free space*/
      if (v[i][j])return;
      /*move to next place*/
      v[i][j]=2;
      move(i-1,j);
      move(i+1,j);
      move(i,j-1);
      move(i,j+1);
      v[i][j]=0;
    }
};
void main(){
    Maze a(20);
    a.Print ();
    a.Find ();
}

zhouheng1212

标  题: C语言中实现参数个数可变的函数
发信站: 逸仙时空 Yat-sen Channel (Wed Apr  5 01:08:11 2000), 站内信件

采用C语言编程的时候，函数中形式参数的数目通常是确定的，在调用时要依次给出与
形式参数对应的所有实际参数。但在某些情况下希望函数的参数个数可以根据需要确定
。典型的例子有大家熟悉的函数printf()、scanf()和系统调用execl()等。那么它们是
怎样实现的呢？C编译器通常提供了一系列处理这种情况的宏，以屏蔽不同的硬件平台造
成的差异，增加程序的可移植性。这些宏包括va_start、va_arg和va_end等。
  使用这些宏有两种不同的形式，二者在程序中包括的头文件不同，宏的定义也存在
一些差别。
  采用ANSI标准形式时，参数个数可变的函数的原型声明是:
  type funcname(type para1, type para2, ...)
  
  这种形式至少需要一个普通的形式参数，后面的省略号不表示省略，而是函数原型
的一部分。type是函数返回值和形式参数的类型。
  采用与UNIX System V兼容的声明方式时，参数个数可变的函数原型是:
  type funcname(va_alist)
  va_dcl
  这种形式不需要提供任何普通的形式参数。type是函数返回值的类型。va_dcl是对
函数原型声明中参数va_alist的详细声明，实际是一个宏定义，对不同的硬件平台采用
不同的类型来定义，但在最后都包括了一个分号。因此va_dcl后不再需要加上分号了。
va_dcl在代码中必须原样给出。va_alist在VC中可以原样给出，也可以略去，但在UNIX
上的CC或GCC中都要省略掉。
  此外，采用头文件stdarg.h编写的程序是符合ANSI标准的，可以在各种操作系统和
硬件上运行；而采用头文件varargs.h的方式仅仅是为了与以前的程序兼容。所以建议大
家使用前者。以下主要就前一种方式对参数的处理做出说明。两种方式的基本原理是一
致的，只是在语法形式上有一些细微的区别。
  va_start使argp指向第一个可选参数。va_arg返回参数列表中的当前参数并使argp
指向参数列表中的下一个参数。va_end把argp指针清为NULL。函数体内可以多次遍历这
些参数，但是都必须以va_start开始，并以va_end结尾。
  调用者在实际调用参数个数可变的函数时，要通过一定的方法指明实际参数的个数
，例如把最后一个参数置为空字符串（系统调用execl()就是这样的）、-1或其他的方式
（函数printf()就是通过第一个参数，即输出格式的定义来确定实际参数的个数的）。

  下面给出一个具体的例子。前一部分是采用了符合ANSI标准的形式的代码，后一部
分是采用了与UNIX System V兼容方式的代码。代码中加了一些注释，这里就不再解释了
。该例子已经在VC/Windows NT4.0、CC/AIX4.3.2.0、GCC/Redhat Linux 6.0环境下编译
并正常运行。
  1、演示如何使用参数个数可变的函数，采用ANSI标准形式
#include < stdio.h >
#include < string.h >
#include < stdarg.h >
/* 函数原型声明，至少需要一个确定的参数，
注意括号内的省略号 */
int demo( char *, ... );
void main( void )
{
  demo("DEMO", "This", "is", "a", "demo!", "\0");
}
/* ANSI标准形式的声明方式，括号内的省略号表示可选参数 */
int demo( char *msg, ... )
{
va_list argp;    /* 定义保存函数参数的结构 */
  int argno = 0;  /* 纪录参数个数 */
  char *para;    /* 存放取出的字符串参数 */
/* argp指向传入的第一个可选参数，
msg是最后一个确定的参数 */
va_start( argp, msg );
  while (1) {
para = va_arg( argp, char *);  /*
取出当前的参数，类型为char *. */
    if ( strcmp( para, "\0") == 0 )
/* 采用空串指示参数输入结束 */
    break;
printf("Parameter #%d is: %s\n", argno, para);
    argno++;
  }
  va_end( argp );  /* 将argp置为NULL */
  return 0;
}
  2、演示如何使用参数个数可变的函数，采用与UNIX System V兼容的方式
#include < stdio.h >
#include < string.h >
#include < varargs.h >
/* 函数原型声明，括号内的类型va_list在
VC/Windows NT4.0可以保留，
但在AIX和Linux下需要去掉，即改成int demo( ) */
int demo( va_list );
void main( void )
{
    demo("This", "is", "a", "demo!", "\0");
}
/* UNIX System V采用的声明方式，括号内是
va_alist，不是va_list，而且
va_dcl后面不需要分号 */
int demo( va_alist )
va_dcl
{
va_list argp;
/* 定义保存函数参数的结构 */
    int argno = 0;
/* 纪录参数个数 */
    char *para;
/* 存放取出的字符串参数 */
va_start( argp );
/* argp指向第一个可选参数 */
while (1) {
para = va_arg( argp, char *);
/* 取出当前的参数，类型为char* */
if ( strcmp( para, "\0") == 0 )
/* 采用空串指示参数输入结束 */
  break;
printf("Parameter #%d is: %s\n", argno, para);
  argno++;
    }
va_end( argp );
/* 将argp置为NULL */
return 0;
}

zhouheng1212

可见，上述的算法和求最大流的Edmonds-Karp标号算法几乎一样，因为这两种算法
都使用宽度优先搜索来来寻找增广路径，所以复杂度也相同，都是O(VE)，其中V是
节点数目，E是边数目。
其他的就不详述了，大家感兴趣的可以查阅TAOCP或者是算法导论的相关内容。
贪心法与拟阵:
贪心法是求解关于独立系统组合优化问题的一种简单算法，求最小生成树的
Kruskal算法就是一种贪心算法。但是贪心法并不总能找到最优独立集。贪心法能
求得最优独立集的充分必要条件是L为一个拟阵。事实上，求最大生成树是关于拟
阵的组合优化问题，而二部图的所有匹配构成的独立系统U不是拟阵。
贪心法的基本思路是:从问题的某一个初始解出发逐步逼近给定的目标，以尽可能
快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。

该算法存在问题:
1. 不能保证求得的最后解是最佳的；
2. 不能用来求最大或最小解问题；
3. 只能求满足某些约束条件的可行解的范围。
实现该算法的过程:
从问题的某一初始解出发；
while 能朝给定总目标前进一步 do
  求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解；
穷举搜索:
  组合算法要解决的问题只有有限种可能，在没有跟好算法时总可以用穷举搜索
的办法解决，即逐个的检查所有可能的情况。可以想象，情况较多时这种方法极为
费时。实际上并不需要机械的检查每一种情况，常常是可以提前判断出某些情况不
可能取到最优解，从而可以提前舍弃这些情况。这样也是隐含的检查了所有可能的
情况，既减少了搜索量，又保证了不漏掉最优解。这方面怒火之炮写过文章，我认
为没必要敖述了。
分支限界法:
这是一种用于求解组合优化问题的排除非解的搜索算法。类似于回溯法，分枝定界
法在搜索解空间时，也经常使用树形结构来组织解空间。然而与回溯法不同的是，
回溯算法使用深度优先方法搜索树结构，而分枝定界一般用宽度优先或最小耗费方
法来搜索这些树。因此，可以很容易比较回溯法与分枝定界法的异同。相对而言，
分枝定界算法的解空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可
能性更大。
算法思想:分枝定界（branch and bound）是另一种系统地搜索解空间的方法，它
与回溯法的主要区别在于对E-节点的扩充方式。每个活节点有且仅有一次机会变成
E-节点。当一个节点变为E-节点时，则生成从该节点移动一步即可到达的所有新节
点。在生成的节点中，抛弃那些不可能导出（最优）可行解的节点，其余节点加入
活节点表，然后从表中选择一个节点作为下一个E-节点。从活节点表中取出所选择
的节点并进行扩充，直到找到解或活动表为空，扩充过程才结束。
有两种常用的方法可用来选择下一个E-节点（虽然也可能存在其他的方法）:
1) 先进先出（F I F O） 即从活节点表中取出节点的顺序与加入节点的顺序相同
，因此活
节点表的性质与队列相同。
2) 最小耗费或最大收益法在这种模式中，每个节点都有一个对应的耗费或收益。
如果查找
一个具有最小耗费的解，则活节点表可用最小堆来建立，下一个E-节点就是具有最
小耗费
的活节点；如果希望搜索一个具有最大收益的解，则可用最大堆来构造活节点表，
下一个
E-节点是具有最大收益的活节点。
动态规划:
动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision

process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究

多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优
化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐
个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的
名著Dynamic Programming，这是该领域的第一本著作。动态规划问世以来，在经
济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线
、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它
方法求解更为方便。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化
问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引
进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。
一般来说，只要问题可以划分成规模更小的子问题，并且原问题的最优解中包含了

子问题的最优解（即满足最优子化原理），则可以考虑用动态规划解决。动态规划
的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、
相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的
算法策略。
由此可知，动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的
、相似的子问题，并通过求解子问题产生一个全局最优解。其中贪心法的当前选择
可能要依赖已经作出的所有选择，但不依赖于有待于做出的选择和子问题。因此贪
心法自顶向下，一步一步地作出贪心选择；而分治法中的各个子问题是独立的 (即
不包含公共的子子问题)，因此一旦递归地求出各子问题的解后，便可自下而上地
将子问题的解合并成问题的解。但不足的是，如果当前选择可能要依赖子问题的解
时，则难以通过局部的贪心策略达到全局最优解；如果各子问题是不独立的，则分
治法要做许多不必要的工作，重复地解公共的子问题。解决上述问题的办法是利用
动态规划。该方法主要应用于最优化问题，这类问题会有多种可能的解，每个解都
有一个值，而动态规划找出其中最优(最大或最小)值的解。若存在若干个取最优值
的解的话，它只取其中的一个。在求解过程中，该方法也是通过求解局部子问题的
解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独
立，(亦即各子问题可包含公共的子子问题)也允许其通过自身子问题的解作出选择
，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复
计算。
因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子
问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第
一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求
解。
设计一个标准的动态规划算法，通常可按以下几个步骤进行:
1.划分阶段:按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干

个阶段一定要是有序的或者是可排序的（即无后向性），否则问题就无法用动态规

划求解。
2.选择状态:将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示

出来。当然，状态的选择要满足无后效性。
确定决策并写出状态转移方程:之所以把这两步放在一起，是因为决策和状态转移

有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。

所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是

反过来做，根据相邻两段的各状态之间的关系来确定决策。
3.写出规划方程（包括边界条件）:动态规划的基本方程是规划方程的通用形式

化表达式。一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较

简单的。 动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会
非常简单。
分治法:
对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解

决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式
相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法
设计策略叫做分治法。 任何一个可以用计算机求解的问题所需的计算时间都与其
规模有关。问题的规模越
小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问

题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作

3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规

模较大的问题，有时是相当困难的。分治法的设计思想是，将一个难以直接解决的
大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
如果原问题可分割成k个子问题，1 < k ≤ n ，且这些子问题都可解，并可利用这
些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问
题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反
复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子
问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对
孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
其基本步骤是:
分解:将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

解决:若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
合并:将各个子问题的解合并为原问题的解。
它的一般的算法设计模式如下:
Divide-and-Conquer(P)
1.if |P|≤n0
2.then return( ADHOC(P) )
3.将P分解为较小的子问题 P1 ,P2 ,...,Pk
4.for i←1 to k
5.do yi ← Divide-and-Conquer(Pi)   △ 递归解决Pi
6.T ← MERGE(y1,y2,...,yk)    △ 合并子问题
7.return(T)
其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已

容易直接解出，不必再继续分解。ADHOC(P)是该分治法中的基本子算法，用于直接

解小规模的问题P。因此，当P的规模不超过n0时，直接用算法ADHOC(P)求解。算法

MERGE(y1,y2,...,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,...

,Pk的相应的解y1,y2,...,yk合并为P的解。
根据分治法的分割原则，原问题应该分为多少个子问题才较适宜？各个子问题的规

模应该怎样才为适当？这些问题很难予以肯定的回答。但人们从大量实践中发现，

在用分治法设计算法时，最好使子问题的规模大致相同。换句话说，将一个问题分

成大小相等的k个子问题的处理方法是行之有效的。许多问题可以取k=2。这种使子

问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是

比子问题规模不等的做法要好。
分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显，有些问题合
并方法比较复杂，或者是有多种合并方案，或者是合并方案不明显，究竟应该怎样
合并，没有统一的模式，需要具体问题具体分析。
  其他的一些经典的算法，如快速傅里叶变换，大家都非常熟悉，这里就不再
涉及。如果想深入学习不妨参考San Diego 州立大学的相关课程主页
http://www.eli.sdsu.edu/courses/fall95/cs660/notes/
组合算法的设计是一门艺术，需要高度的技巧和灵感。算法分析的任务是分析算法
的优劣，算法分析的任务是分析算法的优劣，主要是讨论算法的时间复杂性和空间
复杂性。它的理论基础是组合分析，包括计数和枚举。计算复杂性理论，特别是
NP完全性理论，与组合算法是紧密相关的。NP完全性概念的提出，正是为了刻画包
括旅行商问题、图着色问题、图着色问题、整数规划等一大批组合问题的计算难度
。计算复杂性理论研究算法在时间和空间限制下的能力以及问题的难度，使组合算
法的研究有了更加清晰的框架，将组合算法的研究提高到一个新的水平。