博文
快速排序(2006-05-16 20:15:00)
摘要：分而治之方法还可以用于实现另一种完全不同的排序方法，这种排序法称为快速排序（quick sort）。在这种方法中， n 个元素被分成三段（组）：左段l e f t，右段r i g h t和中段m i d d l e。中段仅包含一个元素。左段中各元素都小于等于中段元素，右段中各元素都大于等于中段元素。因此l e f t和r i g h t中的元素可以独立排序，并且不必对l e f t和r i g h t的排序结果进行合并。m i d d l e中的元素被称为支点( p i v o t )。图1 4 - 9中给出了快速排序的伪代码。/ /使用快速排序方法对a[ 0 :n- 1 ]排序从a[ 0 :n- 1 ]中选择一个元素作为m i d d l e，该元素为支点把余下的元素分割为两段left 和r i g h t，使得l e f t中的元素都小于等于支点，而right 中的元素都大于等于支点递归地使用快速排序方法对left 进行排序递归地使用快速排序方法对right 进行排序所得结果为l e f t + m i d d l e + r i g h t图14-9 快速排序的伪代码考察元素序列[ 4 , 8 , 3 , 7 , 1 , 5 , 6 , 2 ]。假设选择元素6作为支点，则6位于m i d d l e；4，3，1，5，2位于l e f t；8，7位于r i g h t。当left 排好序后，所得结果为1，2，3，4，5；当r i g h t排好序后，所得结果为7，8。把right 中的元素放在支点元素之后， l e f t中的元素放在支点元素之前，即可得到最终的结果[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ]。把元素序列划分为l e f t、m i d d l e和r i g h t可以就地进行（见程序1 4 - 6）。在程序1 4 - 6中，支点总是取位置1中的元素。也可以采用其他选择方式来提高排序性能，本章稍后部分将给出这样一种选择。程序14-6 快速排序templatevoid QuickSort(T*a, int n){// 对a[0:n-1] 进行快速排序{// 要求a[n] 必需有最大关键值quickSort(a, 0, n-1);templatevoid quickSort(T a[], int l, int r){// 排序......
关于volatile关键字的说明以及测试 (转)(2006-05-01 16:26:00)
摘要：
volatile关键字是一种类型修饰符，用它声明的类型变量表示可以被某些编译器未知的因素更改，比如
操作系统、硬件或者其它线程等。遇到这个关键字声明的变量，编译器对访问该变量的代码就不再进行
优化，从而可以提供对特殊地址的稳定访问。
使用该关键字的例子如下：
int volatile nVint;
当要求使用volatile 声明的变量的值的时候，系统总是重新从它所在的内存读取数据，即使它前面的指
令刚刚从该处读取过数据。而且读取的数据立刻被保存。
例如：
volatile int i=10;int a = i;。。。//其他代码，并未明确告诉编译器，对i进行过操作int b = i;
volatile 指出 i是随时可能发生变化的，每次使用它的时候必须从i的地址中读取，因而编译器生成的
汇编代码会重新从i的地址读取数据放在b中。而优化做法是，由于编译器发现两次从i读数据的代码之间
的代码没有对i进行过操作，它会自动把上次读的数据放在b中。而不是重新从i里面读。这样以来，如果
i是一个寄存器变量或者表示一个端口数据就容易出错，所以说volatile可以保证对特殊地址的稳定访问
。
注意，在vc6中，一般调试模式没有进行代码优化，所以这个关键字的作用看不出来。下面通过插入汇编
代码，测试有无volatile关键字，对程序最终代码的影响：
首先用classwizard建一个win32 console工程，插入一个voltest.cpp文件，输入下面的代码：
#include <stdio.h>void main(){ int i=10; int a = i;
printf("i= %d\n",a); //下面汇编语句的作用就是改变内存中i的值，但是又不让编译器知道 __asm { mov dword ptr [ebp-4], 20h }
int b = i; printf("i= %d\n",b);}
然后，在调试版本模式运行程......
辗转相除法 求最大公约数(转)(2006-05-01 15:52:00)
摘要：辗转相除法 「辗转相除法」又叫做「欧几里得算法」,是公元前 300 年左右的希腊数学家欧几里得在他的著作《几何原本》提出的.利用这个方法,可以较快地求出两个自然数的最大公因数,即 HCF 或叫做 gcd.所谓最大公因数,是指几个数的共有的因数之中最大的一个,例如 8 和 12 的最大公因数是 4,记作 gcd(8,12)=4. 在介绍这个方法之前,先说明整除性的一些特点,注以下文的所有数都是正整数,以后不再重覆. 我们可以这样给出整除以的定义: 对於两个自然数 a 和 b,若存在正整数 q,使得 a=bq,则 b 能整除 a,记作 b | a,我们叫 b 是 a 的因数,而 a 是 b 的倍数. 那麼如果 c | a,而且 c | b,则 c 是 a 和 b 的公因数. 由此,我们可以得出以下一些推论: 推论一:如果 a | b,若 k 是整数,则 a | kb.因为由 a | b 可知 ha=b,所以 (hk)a=kb,即 a | kb. 推论二:如果 a | b 以及 a | c,则 a | (b±c).因为由 a | b 以及 a | c,可知 ha=b,ka=c,二式相加,得 (h+k)a=b+c,即 a | (b+c).同样把二式相减可得 a | (b-c). 推论三:如果 a | b 以及 b | a,则 a=b.因为由 a | b 以及 b | a,可知 ha=b,a=kb,因此 a=k(ha),hk=1,由於 h 和 k 都是正整数,故 h=k=1,因此 a=b. 辗转相除法是用来计算两个数的最大公因数,在数值很大时尤其有用而且应用在电脑程式上也十分简单.其理论如下: 如果 q 和 r 是 m 除以 n 的商及余数,即 m=nq+r,则 gcd(m,n)=gcd(n,r). 证明是这样的: 设 a=gcd(m,n),b=gcd(n,r) 则有 a | m 及 a | n,因此 a | (m-nq)(这是由推论一及推论二得出的),即 a | r 及 a | n,所以 a | b 又 b | r 及 b | n,所以 b | (nq+r),即 b | m 及 b | n,所以b | a.因为 a | b 并且 b | a,所以 a=b,即 gcd(m,n)=gcd(n,r). 例如计算 gcd(546, 429),由於 546=1(429)+117,42......