JAVA中的传递都是值传递吗？有没有引用传递呢？

在回答这两个问题前，让我们首先来看一段代码：

public class ParamTest {
// 初始值为0
protected int num = 0;
// 为方法参数重新赋值
public void change(int i) {
i = 5;
}
// 为方法参数重新赋值
public void change(ParamTest t) {
ParamTest tmp = new ParamTest();
tmp.num = 9;
t = tmp;
}
// 改变方法参数的值
public void add(int i) {
i += 10;
}
// 改变方法参数属性的值
public void add(ParamTest pt) {
pt.num += 20;
}
public static void main(String[] args) {
ParamTest t = new ParamTest();
System.out.println("参数--基本类型");
System.out.println("原有的值：" + t.num);
// 为基本类型参数重新赋值
t.change(t.num);
System.out.println("赋值之后：" + t.num);
// 为引用型参数重新赋值
t.change(t);
System.out.println("运算之后：" + t.num);
System.out.println();
t = new ParamTest();
System.out.println("参数--引用类型");
System.out.println("原有的值：" + t.num);
// 改变基本类型参数的值
t.add(t.num);
System.out.println("赋引用后：" + t.num);
// 改变引用类型参数所指向对象的属性值
t.add(t);
System.out.println("改属性后：" + t.num);
}
}

这段代码的运行结果如下：

1. 参数--基本类型
2. 原有的值：0
3. 赋值之后：0
4. 运算之后：0
5. 
   
6. 参数--引用类型
7. 原有的值：0
8. 赋引用后：0
9. 改属性后：20

从上面这个直观的结果中我们很容易得出如下结论：

1. 对于基本类型，在方法体内对方法参数进行重新赋值，并不会改变原有变量的值。
2. 对于引用类型，在方法体内对方法参数进行重新赋予引用，并不会改变原有变量所持有的引用。
3. 方法体内对参数进行运算，不影响原有变量的值。
4. 方法体内对参数所指向对象的属性进行运算，将改变原有变量所指向对象的属性值。

上面总结出来的不过是我们所看到的表面现象。那么，为什么会出现这样的现象呢？这就要说到值传递和引用传递的概念了。这个问题向来是颇有争议的。

大家都知道，在JAVA中变量有以下两种：

1. 基本类型变量，包括char、byte、short、int、long、float、double、boolean。
2. 引用类型变量，包括类、接口、数组（基本类型数组和对象数组）。

当基本类型的变量被当作参数传递给方法时，JAVA虚拟机所做的工作是把这个值拷贝了一份，然后把拷贝后的值传递到了方法的内部。因此在上面的例子中，我们回头来看看这个方法：

// 为方法参数重新赋值
public void change(int i) {
i = 5;
}

在这个方法被调用时，变量i和ParamTest型对象t的属性num具有相同的值，却是两个不同变量。变量i是由JAVA虚拟机创建的作用域在 change(int i)方法内的局部变量，在这个方法执行完毕后，它的生命周期就结束了。在JAVA虚拟机中，它们是以类似如下的方式存储的：

很明显，在基本类型被作为参数传递给方式时，是值传递，在整个过程中根本没有牵扯到引用这个概念。这也是大家所公认的。对于布尔型变量当然也是如此，请看下面的例子：

public class BooleanTest {
// 布尔型值
boolean bool = true;
// 为布尔型参数重新赋值
public void change(boolean b) {
b = false;
}
// 对布尔型参数进行运算
public void calculate(boolean b) {
b = b && false;
// 为了方便对比，将运算结果输出
System.out.println("b运算后的值：" + b);
}
public static void main(String[] args) {
BooleanTest t = new BooleanTest();
System.out.println("参数--布尔型");
System.out.println("原有的值：" + t.bool);
// 为布尔型参数重新赋值
t.change(t.bool);
System.out.println("赋值之后：" + t.bool);
// 改变布尔型参数的值
t.calculate(t.bool);
System.out.println("运算之后：" + t.bool);
}
}

输出结果如下：

1. 参数--布尔型
2. 原有的值：true
3. 赋值之后：true
4. b运算后的值：false
5. 运算之后：true

那么当引用型变量被当作参数传递给方法时JAVA虚拟机又是怎样处理的呢？同样，它会拷贝一份这个变量所持有的引用，然后把它传递给JAVA虚拟机为方法 创建的局部变量，从而这两个变量指向了同一个对象。在篇首所举的示例中，ParamTest类型变量t和局部变量pt在JAVA虚拟机中是以如下的方式存 储的：

有一种说法是当一个对象或引用类型变量被当作参数传递时，也是值传递，这个值就是对象的引用，因此JAVA中只有值传递，没有引用传递。还有一种说法是引 用可以看作是对象的别名，当对象被当作参数传递给方法时，传递的是对象的引用，因此是引用传递。这两种观点各有支持者，但是前一种观点被绝大多数人所接 受，其中有《Core Java》一书的作者，以及JAVA的创造者James Gosling，而《Thinking in Java》一书的作者Bruce Eckel则站在了中立的立场上。

我个人认为值传递中的值指的是基本类型的数值，即使对于布尔型，虽然它的表现形式为true和false，但是在栈中，它仍然是以数值形式保存的，即0表 示false，其它数值表示true。而引用是我们用来操作对象的工具，它包含了对象在堆中保存地址的信息。即使在被作为参数传递给方法时，实际上传递的 是它的拷贝，但那仍是引用。因此，用引用传递来区别与值传递，概念上更加清晰。

最后我们得出如下的结论：

1. 基本类型和基本类型变量被当作参数传递给方法时，是值传递。在方法实体中，无法给原变量重新赋值，也无法改变它的值。
2. 对象和引用型变量被当作参数传递给方法时，在方法实体中，无法给原变量重新赋值，但是可以改变它所指向对象的属性。至于到底它是值传递还是引用传递，这并不重要，重要的是我们要清楚当一个引用被作为参数传递给一个方法时，在这个方法体内会发生什么。

什么叫引用?只因为这个变量的值和其它的不一样.


首先理解:都是变量
int i;
ArrayList b;
i和b都是变量.
但i是基本变量,也叫原始变量.
其它的就叫引用变量,因为它的值是一个内存地址值.引用对象的.但记住:它们都是有一个值的!i是一个数字,而b是一个内存地址值(简单的说是一个十六进 制的值).除了基本变量之外的变量都是引用变量.Vector a;这里的a也是一个变量.它也是有值的,它的值是一个十六进制的值.

变量的赋值:
int i=10;
int j=i;
//这里把i的值10给了j,所以j的值也是10

ArrayList b=new ArrayList();
ArrayList c=b;
//首先,b是一个引用变量,它的"值":是一个内存地址值!!! new ArrayList()要分配一段内存保存它们,怎么样找到这段内存?那就是通过b里的值了.b的值就是new ArrayList()所占内存的首地址.然后c也是一个引用变量,它的值(地址值)和b是一样的.也就是new ArrayList()所占内存的首地址.所以当通过b或者c进行操作时,它们都是操作同一个对象的.

在方法调用的时候,方法的参数实际也就是一个变量.如果是基本类型变量的时候,假设有方法method(int aa);
int j=10;
method(j);
这里边,int aa实际也是定义了一个变量,调用的时候把j的值:10也给了aa.所以aa也是10,改变了aa的值并不会改变j的值.

如果是引用变量的时候,假设有方法methodA(ArrayList aa);
ArrayList b = new ArrayList();
methodA(b);
//方法定义了变量aa,调用的时候把b的值(地址值!!!!!)给了aa,所以aa与b有一样的值(地址值!!!!),在方法里通过aa去操作的时候,b所引用的对象也就被改变了,因为它们引用同一个对象.

纸 a = new 银行帐户();//开一个银行帐户,返回一个卡号给你,写在你的纸a里边.

用一张纸(引用变量),把你的银行卡号写在上边,然后调用我的时候,我用另外一张纸(引用变量---方法的形数),把你的号码抄过来.然后我通过这个卡号,去到银行找到你的帐号,给你存点钱.

然后你用你的纸(引用变量)上的卡号 <没变,还是那个卡号>再去查询银行帐号的时候就会发现了多了一些钱了.....

说说我对值传递和引用传递的看法：
首先我认为，大家对Java传递参数的行为是清楚的，这个争论只是一个语义上的争论。
也就是我们是否需要区分值传递和应用传递呢？或者说这样的区分有没有意义？是否合理？

博主认为存在引用传递的关键点在于，传递的对象地址值，本质上它是一个引用，无论它是否被copy过。
认为只有值传递的关键点在于，传递的对象地址值，它是一个值的copy，这个值代表的意义无所谓。

引用是c++里的概念，由于java跟c++是有一定关系的，这里把引用迁移过来，如果合理未尝不可。
c++中关于引用的解释一般喜欢说是看作“别名”，我查了几本书，大部分提到引用并不会分配内存空间，也有一本书提到，某些编译器会分配存储空间来存储被引用对象的地址。
那么还是回到语义上来，c++里的这个引用，语义上是“别名”的意思，我的理解是，一组指向同一个对象的别名应该只存储一份内存地址。当然具体实现可能会 把引用当做一个不可变的指针来处理（每个别名都存储自己的对象地址）。但是请注意，我们应该关注于它的语义，即：它没有任何值的copy，即使是一个地 址，只是另外一个名字而已。

但是java里面没有这样的概念，所有的地址传递其行为是值的传递方式，语义上统一成值传递更为清晰，我们只需要考虑这个值具体是什么，无非两种，要么是基本类型值，要么是个地址。
所以我认为这个“引用”的概念放到java中并不合适。只有值传递的说法更合理。

Linux 发展到今天，可用的软件已经非常多了。这样自然会有一些软件的功能大致上相同。例如，同样是编辑器，就有 nvi、vim、emacs、nano，而且我说的这些还只是一部分。大多数情况下，这样的功能相似的软件都是同时安装在系统里的，可以用它们的名称来执 行。例如，要执行 vim，只要在终端下输入 vim 并按回车就可以了。不过，有些情况下我们需要用一个相对固定的命令调用这些程序中的一个。例如，当我们写一个脚本程序时，只要写下 editor，而不希望要为“编辑器是哪个”而操心。Debian 提供了一种机制来解决这个问题，而 update-alternatives 就是用来实现这种机制的。

在说明 update-alternatives 的详细内容之间，先让我们看看系统中已有的例子。打开终端，执行下面的命令：

herbert@natsu:~$ ls -l /usr/bin/editor
lrwxrwxrwx 1 root root 24 2004-09-26 08:48 /usr/bin/editor -> /etc/alternatives/editor
herbert@natsu:~$ ls -l /etc/alternatives/editor
lrwxrwxrwx 1 root root 12 2004-10-27 16:24 /etc/alternatives/editor -> /usr/bin/vim
herbert@natsu:~$

我 们看到，editor 这个可执行命令实际上是个符号链接，它指向 /etc/alternatives/editor；而 /etc/alternatives/editor 也是个符号链接，它指向 /usr/bin/vim。这样，当我输入 editor 并回车时，将执行 vim。之所以要在 /usr/bin 和 /etc/alternatives 中费心建立这样两个链接，就是要实现上面说到的特性：方便脚本
程序的编写和系统的管理。

下面我们就来看看 update-alternatives 的功能。当然，如果你觉得我说得不详细，可以看看这个命令的 manpage：UPDATE-ALTERNATIVES(8)。

首先要介绍的参数是 --display。它使我们可以看到一个命令的所有可选命令。执行

natsu:/home/herbert# update-alternatives --display editor
editor - status is auto.
 link currently points to /usr/bin/vim
/bin/ed - priority -100
 slave editor.1.gz: /usr/share/man/man1/ed.1.gz
/usr/bin/nvi - priority 19
 slave editor.1.gz: /usr/share/man/man1/nvi.1.gz
/bin/nano - priority 40
 slave editor.1.gz: /usr/share/man/man1/nano.1.gz
/usr/bin/vim - priority 120
 slave editor.1.gz: /usr/share/man/man1/vim.1.gz
/usr/bin/emacs21 - priority 0
 slave editor.1.gz: /usr/share/man/man1/emacs.1emacs21.gz
Current `best' version is /usr/bin/vim.
natsu:/home/herbert#

你可以看到我的机器上的所有可以用来被 editor 链接的命令。

下面说说 --config。这个选项使我们可以选择其中一个命令：

natsu:/home/herbert# update-alternatives --config editor

There are 5 alternatives which provide `editor'.

  Selection Alternative
-----------------------------------------------
      1 /bin/ed
      2 /usr/bin/nvi
      3 /bin/nano
*+    4 /usr/bin/vim
      5 /usr/bin/emacs21

Press enter to keep the default[*], or type selection number: 4
Using `/usr/bin/vim' to provide `editor'.
natsu:/home/herbert#

我并没有修改它，因为我还是比较喜欢 vim 的。当然，你可以选择别的程序。

说 到这里我们就要介绍一些概念了。首先，update-alternatives 在一般情况下是由 postinst 和 prerm 这样的安装脚本自动调用的，所以一个 alternative 的状态有两种：自动和手动。每个 alternative 的初始状态都是自动。如果系统发现管理员手动修改了一个 alternative，它的状态就从自动变成了手动，这样安装脚本就不会更新它了。如果你希望将一个 alternative 变回自动，只要执行

update-alternatives --auto editor

就可以了。你注意到了吗？我们说到了“名字”。该怎样写名字呢？这就是我们要介绍的第二个概念：
general name -- 这是指一系列功能相似的程序的“公用”名字（包括绝对路径），比如 /usr/bin/editor。
link -- 这是指一个 alternative 在 /etc/alternative 中的名字，比如 editor。
alternative -- 顾名思义，这是指一个可选的程序所在的路径（包括绝对路径），比如 /usr/bin/vim。
-- auto，--display 和 --config 跟的都是 link。我们要说的第三个概念是优先级。这个比较简单，当然优先级越高的程序越好啦（在大多数情况下，我不想争论）最后一个概念是主和从的 alternative。想想看，你将 /usr/bin/editor 链接到了 vim，可是当你执行 man editor 时看到的却是 emacs 的 manpage，你会做何感想呢？这就引出了主和从 alternative 的概念了：当更新主的 alternative 时，从的 alternative 也会被更新。

说完这四个重要的概念后，我们介绍另外两个选项。至于其他的。。。。我相信你会去看手册页的，对吗？

第一个是 --install。它的格式是：

update-alternatives --install gen link alt pri [--slave sgen slink salt] ...

gen， link，alt，pri 分别是我们上面说过的。如果需要从的 alternative，你可以用 --slave 加在后面。如果你在向一个已经存在的 alternative 组中添加新的 alternatives，该命令会把这些 alternatives 加入到这个已经存在的 alternative 组的
列表中，并用新的可选命令作为新的命令；否则，将会建立一个新的自动的 alternative 组。

呜呼！我加入了一个错误的 alternative。我不想要这个 alternative 了。在这种情况 下，可以执行下面的命令：

update-alternatives --remove name path

name 是一个在 /etc/alternatives 中的名字，也就是上面的 link，而 path 是希望删除的可选程序名的绝对路径名（放心，这样只是从列表中删除了这个程序，并不会真的从硬盘上删除程序的可执行文件）。如果从一个 alternative 组中删除了一个正在被链接的程序并且这个组仍然没有变成空的，update-alternatives 会自动用一个具有其他优先级的可选程序代替原来的程序。如果这个组变成空的了，那么连这个 alternative 组都会被移除。如果删除的程序没有被链接，则只有有关这个程序的信息会被移除。

说个例子吧。我下载了 Eclipse，并且安装了 gcj 和 gij。可是我发现 GNU 的 java 工具还不足以运行 Eclipse。我只好到 Sun 公司的网页上下载了它的 java 工具 jdk。因为是自己安装的，我将它们安装在 /usr/local 上，以便将来重新安装 Linux 系统时这些程序仍然可以使用。于是我要做的就是用这个 jdk 中的 java 和 javac 来代替系统原来的。执行

natsu:/home/herbert# update-alternatives --display java
java - status is auto.
 link currently points to /usr/local/j2sdk1.4.2_06/bin/java
/usr/bin/gij-wrapper-3.3 - priority 33
 slave java.1.gz: /usr/share/man/man1/gij-wrapper-3.3.1.gz
/usr/local/j2sdk1.4.2_06/bin/java - priority 100
 slave java.1.gz: /usr/local/j2sdk1.4.2_06/man/man1/java.1
Current `best' version is /usr/local/j2sdk1.4.2_06/bin/java.
natsu:/home/herbert# update-alternatives --display javac
javac - status is auto.
 link currently points to /usr/local/j2sdk1.4.2_06/bin/javac
/usr/bin/gcj-wrapper-3.3 - priority 33
 slave javah: /usr/bin/gcjh-wrapper-3.3
 slave javac.1.gz: /usr/share/man/man1/gcj-wrapper-3.3.1.gz
 slave javah.1.gz: /usr/share/man/man1/gcjh-wrapper-3.3.1.gz
/usr/bin/gcj-wrapper-3.4 - priority 33
 slave javah: /usr/bin/gcjh-wrapper-3.4
 slave javac.1.gz: /usr/share/man/man1/gcj-wrapper-3.4.1.gz
 slave javah.1.gz: /usr/share/man/man1/gcjh-wrapper-3.4.1.gz
/usr/local/j2sdk1.4.2_06/bin/javac - priority 100
 slave javah: /usr/local/j2sdk1.4.2_06/bin/javah
 slave javac.1.gz: /usr/local/j2sdk1.4.2_06/man/man1/javac.1
 slave javah.1.gz: /usr/local/j2sdk1.4.2_06/man/man1/javah.1
Current `best' version is /usr/local/j2sdk1.4.2_06/bin/javac.
natsu:/home/herbert#

（你看到的是我更新以后的）就可以得到关于要更新哪些 alternatives 的信息。我是这么更新的：

update-alternatives --install /usr/bin/javac javac /usr/local/j2sdk1.4.2_06/bin/javac 100 --slave /usr/bin/javah javah /usr/local/j2sdk1.4.2_06/bin/javah --slave /usr/share/man/man1/javac.1.gz javac.1.gz /usr/local/j2sdk1.4.2_06/man/man1/javac.1 --slave /usr/share/man/man1/javah.1.gz javah.1.gz /usr/local/j2sdk1.4.2_06/man/man1/javah.1
update-alternatives --install /usr/bin/java java /usr/local/j2sdk1.4.2_06/bin/java 100 --slave /usr/share/man/man1/java.1.gz java.1.gz /usr/local/j2sdk1.4.2_06/man/man1/java.1
1, insert Ubuntu 7.10 CD
a, format disc(primary 10G ext3; extend 59G ext3; swap 1G)

b, install(timezone shanghai; en_US; "prepare disc space" manual, or the system will partition autoly)

c, auto restart, go on install system(remenber cut off the net line except the netwidth is large, or it will cost long time to download from far away)

2, config
a, sources list
sudo vim /etc/apt/sources.list
# add "deb http://debian.exoweb.net/debian.cn99.com/debian etch main" into it
sudo apt-get update
sudo apt-get upgrade

b, vedio card driver
在ubuntu7.10下装nvidia 7 series显卡并配置双屏显示：

一，显卡驱动 ＋ 双显示器
(修改X配置命令：sudo dpkg-reconfigure xserver-xorg)

1，到nvidia网站下载7系列显卡的最新驱动

2，ensure that the linux-restricted-modules or linux-restricted-modules-common packages have been uninstalled. Alternatively, you can edit the /etc/default/linux-restricted-modules or /etc/default/linux-restricted-modules-common configuration file and disable the NVIDIA linux-restricted kernel modules (nvidia, nvidia_legacy) via:

DISABLED_MODULES="nv nvidia_new"

3,
sudo apt-get remove --purge nvidia-glx nvidia-glx-new
sudo rm /etc/init.d/nvidia-glx /etc/init.d/nvidia-kernel /lib/linux-restricted-modules/.nvidia_new_installed

4，然后ctrl+alt+1进入tty1
sudo /etc/init.d/gdm stop
sudo sh NVIDIA-Linux-x86-100.14.23-pkg1.run
(这时会出现错误提示，说少了“libc header file...libc development package”)
sudo apt-get install sudo apt-get install build-essential xorg-dev pkg-config linux-headers-$(uname -r), libc6-dev
sudo sh NVIDIA-Linux-x86-100.14.23-pkg1.run
sudo /etc/init.d/gdm start

用application -> system tools里的nvidia工具去配置双显示器

c, multi-language
System -> Administration -> Language support: install English and Chinese
check "input method"

d, Wen Quan Yi font
browse http://wenq.org/, and download 文泉驿点阵宋体 and 文泉驿矢量正黑, then install them
System -> Preference -> Appearance -> Fonts 前四项选择：点阵宋体（WenQuanYi Bitmap Song）， 第五项不改（Monospace）
sudo fc-cache -f -v (刷新字体缓存，每次修改字体都要这样，不然Xorg会很慢)

e, stardict                   
sudo apt-get install stardict
(http://stardict.sourceforge.net/Dictionaries_zh_CN.php 下载朗道英汉，汉英字典)
tar -xjvf *** --directory /usr/share/stardict/dic/

f, pidgin internet messager
sudo apt-get install gaim-guifications
config: Tools -> Plugins -> (check) Guifications; then, config it to uncheck on "Chat message"

3, install and config Software
sudo apt-get install postgresql-8.1 python2.4 ipython vim-gnome sun-java5-jdk eclipse subversion build-essential ssh build-essential meld kompare

a, postgresql
sudo su - postgres (for user postgres has Null password, so you can't just "su - postgres", or you can sudo "sudo passwd postgres" to set password for postgres, then "su - postgres")
createuser (enter username and password.)
config postgresql as below:
In /etc/postgresql/8.1/main/postgresql.conf, Change listen_addresses to '*' and change datestyle to 'ISO,European' and uncomment them.
In /etc/postgresql/8.1/main/pg_hba.conf, 最后加入一行“host        all    justin        127.0.0.1/16        trust”

b, eclipse
sudo eclipse, exit, eclipse

c, ssh
When other mathines want to ssh or scp your mathine which is new OS, it should "rm ~/.ssh/known_hosts" to reload the new Cert.

d, kompare
add a file svndiff in src with context
"""
if [ $1 ] ; then
    svn up -r $1
    svn st -q
    svn log -r $1
    PRE=`expr $1 - 1`
    svn diff --diff-cmd=diff -x "-U 10000" -r$PRE:$1 > /tmp/$1.diff
    cat /tmp/$1.diff | kompare -
else
    svn up
    svn st
    svn diff --diff-cmd=diff -x "-U 10000" | kompare -
fi
"""
then, in src, ./svndiff 9827 will show diff about r9827

e, firefox add-ons
firebug, flashblock

3, chroot
a,
sudo apt-get install debootstrap
sudo debootstrap --arch i386 etch /home/etch http://debian.exoweb.net/debian.cn99.com/debian/
(if in 64 bit system, use --arch amd64)
sudo chroot /home/etch
#in etch as root
apt-get install locales
dpkg-reconfigure locales #(choose en_us UTF8 as before)
apt-get install vim vim-gnome xbase-clients less sudo postgresql-client subversion
echo "etch" > /etc/debian-chroot
visudo (add user justin to sudo)
adduser justin (删除的命令是userdel justin)

在ubuntu的/usr/bin/etch加入：
sudo cp /etc/passwd /home/etch/etc/
sudo cp /etc/shadow /home/etch/etc/
sudo cp /etc/group /home/etch/etc/
sudo cp /etc/sudoers /home/etch/etc/
sudo cp /etc/resolv.conf /home/etch/etc/
sudo cp /etc/hosts /home/etch/etc/

在/etc/fstab加入：
/home   /home/etch/home    none    bind 0 0
/tmp    /home/etch/tmp     none    bind 0 0
/dev    /home/etch/dev     none    bind 0 0
/proc   /home/etch/proc    none    bind 0 0
sudo chroot /home/etch/  su - justin

现在就可一享受chroot的双系统了

b, run X in etch 3 steps
b1, (etch)mkdir /tmp/.X11-unix
(ubuntu)sudo echo "/tmp/.X11-unix/x0 /home/justin/etch/tmp/.X11-unix/x0 none bind 0 0" >> /etc/fstab
# another way is write it in to /etc/fstab, or sudo mount --bind /tmp/*** /home/justin/etch/tmp/***
b2, (etch)vim ~/.bashrc # add "export DISPLAY=:0.0"
b3, (ubuntu) cp ~/.Xauthority ~/etch/home/justin/ （其实这步不需要，因为上面已经把/home mount到了/home/etch/home了）

c, install java
#download jdk-1_5_0_14-linux-i586.bin to /opt/, and into etch/opt/
sudo chmod +x jdk-1_5_0_14-linux-i586.bin
sudo ./jdk-1_5_0_14-linux-i586.bin
vim ~/.bashrc
#add below in the end of .bashrc
#export JAVA_HOME=/opt/jdk1.5.0_14
#export CLASSPATH=.:$JAVA_HOME/lib/tools.jar:$JAVA_HOME/lib/dt.jar
#export PATH=$JAVA_HOME/bin:$PATH

java -version
#java version "1.5.0_14"
#Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0_14-b03)
#Java HotSpot(TM) Client VM (build 1.5.0_14-b03, mixed mode, sharing)
配置默认Java使用哪个 sudo update-alternatives --config java
一，两个数的最大公约数：

1、欧几里德算法

欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理：

定理：gcd(a,b) = gcd(b,a mod b)

证明：a可以表示成a = kb + r，则r = a mod b
假设d是a,b的一个公约数，则有
d|a, d|b，而r = a - kb，因此d|r
因此d是(b,a mod b)的公约数

假设d 是(b,a mod b)的公约数，则
d | b , d |r ，但是a = kb +r
因此d也是(a,b)的公约数

因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证

欧几里德算法就是根据这个原理来做的，其算法用C++语言描述为：

void swap(int & a, int & b){
     int c = a;
       a = b;
       b = c;
}

int gcd(int a,int b){
     if(0 == a ){
         return b;
     }
     if( 0 == b){
         return a;
     }
     if(a > b){
         swap(a,b);
     }
     int c;
     for(c = a % b ; c > 0 ; c = a % b){
           a = b;
           b = c;
     }
     return b;
}

2、Stein算法
欧几里德算法是计算两个数最大公约数的传统算法，它无论从理论还是从效率上都是很好的。但是有一个致命的缺陷，这个缺陷只有在大素数时才会显现出来。

考虑现在的硬件平台，一般整数最多也就是64位，对于这样的整数，计算两个数之间的模是很简单的。对于字长为32位的平台，计算两个不超过32位的整数的 模，只需要一个指令周期，而计算64位以下的整数模，也不过几个周期而已。但是对于更大的素数，这样的计算过程就不得不由用户来设计，为了计算两个超过 64位的整数的模，用户也许不得不采用类似于多位数除法手算过程中的试商法，这个过程不但复杂，而且消耗了很多CPU时间。对于现代密码算法，要求计算 128位以上的素数的情况比比皆是，设计这样的程序迫切希望能够抛弃除法和取模。

Stein算法由J. Stein 1961年提出，这个方法也是计算两个数的最大公约数。和欧几里德算法 算法不同的是，Stein算法只有整数的移位和加减法，这对于程序设计者是一个福音。

为了说明Stein算法的正确性，首先必须注意到以下结论：

gcd(a,a) = a，也就是一个数和它自身的公约数是其自身
gcd(ka,kb) = k gcd(a,b)，也就是最大公约数运算和倍乘运算可以交换，特殊的，当k=2时，说明两个偶数的最大公约数必然能被2整除

C++/java 实现

// c++/java stein 算法
int gcd(int a,int b){
     if(a<b){//arrange so that a>b
         int temp = a;
           a = b;
           b=temp;
     }
     if(0==b)//the base case
        return a;
     if(a%2==0 && b%2 ==0)//a and b are even
         return 2*gcd(a/2,b/2);
     if ( a%2 == 0)// only a is even
         return gcd(a/2,b);
     if ( b%2==0 )// only b is even
         return gcd(a,b/2);
     return gcd((a+b)/2,(a-b)/2);// a and b are odd
}

二，多个数的最大公约数：(python实现：取出数组a中最小的，从2到最小的循环，找出其中最大的能被数组中所有数整除的那个数，就是最大公约数)
def gcd(a):
    a.sort()
    min = a[0]
    result = 1
    for i in range(2, min+1):
        flag = True
        for j in a:
            if j % i != 0:
                flag = False
        if flag == True:
            result = i
    return result
Catalan数：(for http://acm.pku.edu.cn/JudgeOnline/problem?id=2084)

C_n = ΣC_i*C_(n-i)，其中0≤i<n；
C_n = C(2n,n) / (n+1)； 其中C(2n, n) 表示组合数，公式为：C(n, k) = n! / (k!(n-k)!)
C_n=C_(n-1)*(4n-2)/(n+1)。

它的意义有很多，例如：n+1边形用对角线划分成 三角形的方法数；n个+1和n个-1满足所有部分和不小于零的排列数；具有n个节点的二叉树的数量……

（详细说明参考：http://hi.baidu.com/kikoqiu/blog/item/81d792015ab13e01738da51d.html）
指令語法

crontab [ -u user ] file
crontab [ -u user ] { -l | -r | -e }

指令說明

crontab 提供我們在固定的間隔時間執行自訂的程式、系統指令或 shell secrip。時間間隔的單位可以是分鐘、小時、日、週、月及以上的任意組合。允許使用者離線執行，並且可以將執行結果以 email 通知使用者。因此，非常設合對週期性的管理分析或資料備份等工作。

基本上，crontab 的指令格式分為六個部分，前五個為時間間隔，最後則是執行的指令。每一個部分用空格來區隔。

分 -- 0-59
時 -- 0-23
日 -- 1-31
月 -- 1-12 或使用英文名稱
星期 -- 0-7 或使用英文名稱
工作命令 -- 指令，shell script，程式....(建議使用絕對路徑)
以上是 crontab 的基本格式。

選項說明

-u user
以指定的使用者身份，執行 crontab 工作。此選項僅供 root 使用。


-l
顯示使用者現行的 crontab 檔。

-r
移除現行的 crontab 檔。

-e
進入 vi 編輯 crontab 檔(如有設定 VISUAL 或 EDITOR 環境變數，怎使用該環境變數所設定的編輯器來編輯)。在使用者退出編輯器後，會自動將所編輯 crontab 檔，置入 crontab 執行。
相關檔案

/etc/cron.allow
/etc/cron.deny

實例說明

# crontab -l
# DO NOT EDIT THIS FILE - edit the master and reinstall.
# (/tmp/crontab.3672 installed on Thu Jan 1 15:55:18 2004)
# (Cron version -- $Id: crontab.c,v 2.13 1994/01/17 03:20:37 vixie Exp $)
0 0-23/6 * * * /usr/bin/webalizer
30 3 * * * /root/fbin/bak-web
#

先前曾提到，crontab 的格式分成六個部分，前五個是時間參數。在上例中你會發現除了數字與英文名稱，有使用到符號"*"，這個符號代表每一單位的意思，譬如 30 3 * * * 既代表 30分 3點 每日 每月 星期的每天。

時間的指定，可以是單一的數字，或幾個數字用逗號來連接。看下例

30 3,12 * * * /root/fbin/bak-web

其中的第二項為 3,12，這代表 3 以及 12 小時的意思。再來看下例

30 */6 * * * /root/fbin/bak-web

我把第二項改成 */6 這代表每 6 小時，也相當於 6,12,18,24 的作用。此外還有一個區段的做法

30 8-18/2 * * * /root/fbin/bak-web

我把第二項改成 8-18/2 這代表在 8 小時到 18 小時之間每 2 小時，也相當於 8,10,12,14,16,18 的作用。

在認知的以上介紹各項時間用法後，你可以視實際的需要自行組合。使用上的彈性是相當自由的。這篇暫時到此。


(转自：http://blog.chinaunix.net/u/24474/showart_217098.html)

diff和patch是一对工具，在数学上来说，diff是对两个集合的差运算，patch是对两个集合的和运算。
diff比较两个文件或文件集合的差异，并记录下来，生成一个diff文件，这也是我们常说的patch文件，即补丁文件。
patch能将diff文件运用于 原来的两个集合之一，从而得到另一个集合。举个例子来说文件A和文件B,经过diff之后生成了补丁文件C,那么着个过程相当于 A -B = C ,那么patch的过程就是B+C = A 或A-C =B。
因此我们只要能得到A, B, C三个文件中的任何两个，就能用diff和patch这对工具生成另外一个文件。

这就是diff和patch的妙处。下面分别介绍一下两个工具的用法:

1. diff的用法

diff后面可以接两个文件名或两个目录名。 如果是一个目录名加一个文件名，那么只作用在那么个目录下的同名文件。

如果是两个目录的话，作用于该目录下的所有文件，不递归。如果我们希望递归执行，需要使用-r参数。

命令diff A B > C ,一般A是原始文件，B是修改后的文件，C称为A的补丁文件。
不加任何参数生成的diff文件格式是一种简单的格式，这种格式只标出了不一样的行数和内容。我们需要一种更详细的格式，可以标识出不同之处的上下文环境，这样更有利于提高patch命令的识别能力。这个时候可以用-c开关。


2. patch的用法

patch用于根据原文件和补丁文件生成目标文件。还是拿上个例子来说

patch A C 就能得到B, 这一步叫做对A打上了B的名字为C的补丁。

之一步之后，你的文件A就变成了文件B。如果你打完补丁之后想恢复到A怎么办呢？

patch -R B C 就可以重新还原到A了。

所以不用担心会失去A的问题。

其实patch在具体使用的时候是不用指定原文件的，因为补丁文件中都已经记载了原文件的路径和名称。patch足够聪明可以认出来。但是有时候会有点小 问题。比如一般对两个目录diff的时候可能已经包含了原目录的名字，但是我们打补丁的时候会进入到目录中再使用patch,着个时候就需要你告诉 patch命令怎么处理补丁文件中的路径。可以利用-pn开关，告诉patch命令忽略的路径分隔符的个数。举例如下：

A文件在 DIR_A下，修改后的B文件在DIR_B下，一般DIR_A和DIR_B在同一级目录。我们为了对整个目录下的所有文件一次性diff,我们一般会到DIR_A和DIR_B的父目录下执行以下命令

diff -rc DIR_A DIR_B > C

这个时候补丁文件C中会记录了原始文件的路径为 DIR_A/A

现在另一个用户得到了A文件和C文件，其中A文件所在的目录也是DIR_A。 一般，他会比较喜欢在DIR_A目录下面进行patch操作，它会执行

patch < C

但是这个时候patch分析C文件中的记录，认为原始文件是./DIR_A/A，但实际上是./A，此时patch会找不到原始文件。为了避免这种情况我们可以使用-p1参数如下

patch -p1 < C

此时，patch会忽略掉第1个”/”之前的内容，认为原始文件是 ./A，这样就正确了。
使用patch

patch附带有一个很好的帮助，其中罗列了很多选项，但是99%的时间只要两个选项就能满足我们的需要：

patch -p1 < [patchfile]

patch -R < [patchfile] (used to undo a patch)

-p1选项代表patchfile中      文件名左边目录的层数，顶层目录在不同的机器上有所不同。要使用这个选项，就要把你的patch放在要被打补丁的目录下，然后在这个目录中运行path -p1 < [patchfile]。      摘要: Python基础篇 整理：Jims of 肥肥世家 <jims.yang@gmail.com> Copyright © 2004，2005，2006 本文遵从GNU 的自由文档许可证(Free Document License)的条款，欢迎转载、修改、散布。 发布时间：2004年07月10日 更新时间：20...  阅读全文 /etc/profile:此文件为系统的每个用户设置环境信息,当用户第一次登录时,该文件被执行.并从/etc/profile.d目录的配置文件中搜集shell的设置.

/etc/bashrc:为每一个运行bash shell的用户执行此文件.当bash shell被打开时,该文件被读取.

~/.bash_profile:每个用户都可使用该文件输入专用于自己使用的shell信息,当用户登录时,该文件仅仅执行一次!默认情况下,他设置一些环境变量,执行用户的.bashrc文件.

~/.bashrc:该文件包含专用于你的bash shell的bash信息,当登录时以及每次打开新的shell时,该该文件被读取.

~/.bash_logout:当每次退出系统(退出bash shell)时,执行该文件.

另外,/etc/profile中设定的变量(全局)的可以作用于任何用户,而~/.bashrc等中设定的变量(局部)只能继承/etc/profile中的变量,他们是"父子"关系.

~/.bash_profile 是交互式、login 方式进入 bash 运行的

~/.bashrc 是交互式 non-login 方式进入 bash 运行的

通常二者设置大致相同，所以通常前者会调用后者。 一，安装jdk：

（这里的方法是用于ubuntu或debian的，把下载的jdk构建成deb包，我觉得是为了便于包管理，否则删除的时候都不知道删除哪些文件，很麻烦。）
1. 获取JDK
可以选择从Java官方下载: ::URL::http://java.sun.com 或者从其它网站下载.我用的版本是:jdk-1_5_0-linux-i586.bin

2. 构建打包环境
Debian专门提供了SDK 的DEB包构建工具: java-package,而Ubuntu是基于Debian的,所以
# apt-get install -u java-package fakeroot

在apt-get之前最好update一下

3. 创建.deb 软件包

这一步要以普通用户运行,如果以Root运行是不允许的.会有下面的提示:

You are real root -- unfortunately, some Java distributions have
install scripts that directly manipulate /etc, and may cause some
inconsistencies on your system. Instead, you should become a
non-root user and run:

fakeroot make-jpkg jdk-1_5_0-linux-i586.bin

which will allow no damage to be done to your system files and
still permit the Java distribution to successfully extract.

Aborting.

以普通用户执行:
＄ fakeroot make-jpkg jdk-1_5_0_06-linux-i586.bin
接下来做一些必要的选择.几分钟后,就应当出现软件包创建成功的提示.你在当前目录下会发现类似:
sun-j2sdk1.5_1.5.0+update00_i386.deb的软件包

4. 安装
切换回root执行以下命令:
# dpkg -i sun-j2sdk1.5_1.5.0+update06_i386.deb

5.配置环境

在 ~/.bashrc脚本文件中加入类似如下内容

PATH=＄PATH:/usr/lib/j2sdk1.5-sun/bin:/usr/lib/j2sdk1.5-sun/jre/bin
JAVA_HOME=/usr/lib/j2sdk1.5-sun
JRE_HOME=/usr/lib/j2sdk1.5-sun/jre
CLASSPATH=.:/usr/lib/j2sdk1.5-sun/lib/tools.jar:/usr/lib/j2sdk1.5-sun/lib/dt.jar
export PATH
export JRE_HOME
export JAVA_HOME
export CLASSPATH

6. 测试
创建一个简单的java程序(Hello.java)
public class Hello
{
public Hello()
{
}

public static void main(String[] args)
{
System.out.println("Hello World!";
}

}
然后
＄javac Hello.java
检查当前目录会生成一个Hello.class的文件, 然后运行
＄java Hello
Hello World!
OK,测试成功!

7. 中文化安装中文字体:
在 ＄JAVA_HOME/jre/lib/fonts/ 目录下创建一个fallback目录.
复制中文字体(例如:simsun.ttf 至此目录.

8. 安装插件
对于此种方法安装的Java环境, 浏览器插件文件位置应当位于:
/usr/lib/j2sdk1.5-sun/jre/plugin/i386/ns7/libjavaplugin_oji.so

以 firefox1.5.0.1为例:
# cd /usr/lib/mozilla-firefox/plugins
# ln -s \
/usr/lib/j2sdk1.5-sun/jre/plugin/i386/ns7/libjavaplugin_oji.so

卸载JDK:
# apt-get remove --purge sun-j2sdk1.5
卸载插件, 直接删除符号链接:
# rm /usr/lib/mozilla-firefox/plugins/libjavaplugin_oji.so

二，安装jython：

1，http://www.jython.org/Project/installation.html下载jython安装文件，运行命令“java -jar jython_installer-2.2rc2.jar”，jython即安装成功。比如安装在/home/justin/java/jython2.2目录下

2，把jython包加入classpath，即把上面的classpath改为：CLASSPATH=.:/usr/lib/j2sdk1.5-sun/lib/tools.jar:/usr/lib/j2sdk1.5-sun/lib/dt.jar:/home/justin/java/jython2.2/jython.jar
此后就可以在java文件中加入python库了，例如：

3，将选择的/home/justin/java/jython2.2/jython安装路径添加到 PATH 环境变量。现在只要输入“jython”就可以运行交互式 PATH ：
$ jython
Jython 2.1 on java1.4.0_01 (JIT: null)
Type "copyright", "credits" or "license" for more information.
>>># 通过 Jython 访问标准 Java 库
>>> from java.util import Random
>>> rng = Random()
>>> i = rng.nextBoolean()
>>> print i

jython 解释器对于快速检查和作提示都很方便，但您不必在这其中完成所有工作 ― Jython 还允许您在源文件中编写代码，并随后运行该代码（
from java.util import Random
rng = Random()
#This is a comment in Jython
print "Flipping a coin..."
if rng.nextBoolean():
    print "Came up heads"
else:
    print "Came up tails"
用jython运行该文件，即可
一，网络时间服务：

1. 与一个已知的时间服务器同步
公司配置：
#synchronize time with fw.exoweb.net
00 0 1 * * root rdate -s fw.exoweb.net

2. 配置网络时间协议（ntp）

1. 让linux自动同步时间

vi /etc/crontab
加上一句：
00 0 1 * * root rdate -s time.nist.gov

time.nist.gov 是一个时间服务器.

2. 时间服务器配置(192.168.10.1)

1）. # rpm -ivh ntp-4.1.2-4.EL3.1.i386.rpm
2）. # vi /etc/ntp.conf
注释一行
restrict default ignore
加入一行
restrict 192.168.10.0 mask 255.255.255.0 notrust nomodify notrap
3）. # vi /etc/ntp/step-tickers
加入一行
pool.ntp.org
这样每次ntpd启动时，会自动连接该国际标准时间服务器；
4）. # service ntpd start
5）. # netstat -an |grep 123
确保该端口以udp方式开放

时间客户端配置(192.168.10.2)
1）. # ntpdate 192.168.10.2
应该显示同步成功
2）. # crond -e
加入
0-59/10 * * * * /usr/sbin/ntpdate 192.168.10.1
表示每隔10分钟同步一次时间

二, 出现  must be setuid root 错误
解决办法：

ls -l  /usr/bin/sudo
chown root:root /usr/bin/sudo
chmod 4755 /usr/bin/sudo
reboot

三，用nohup命令让Linux下程序永远在后台执行

Unix/Linux下一般想让某个程序在后台运行，很多都是使用 & 在程序结尾来让程序自动运行。比如我们要运行mysql在后台：

         /usr/local/mysql/bin/mysqld_safe --user=mysql &

但是我们很多程序并不象mysqld一样可以做成守护进程，可能我们的程序只是普通程序而已，一般这种程序即使使用 & 结尾，如果终端关闭，那么程序也会被关闭。为了能够后台运行，我们需要使用nohup这个命令，比如我们有个start.sh需要在后台运行，并且希望在 后台能够一直运行，那么就使用nohup：

            nohup /root/start.sh &

四， python反编译工具
decompyle

五，rpm包转deb包工具： fakeroot and alien
fakeroot alien -d *.rpm

六， 保存ftest信息并查看
nohup ./nordicbetsite ftest -v2 >ftest_result 2>&1 &
tail -f ftest_result

七， ip信息
ifconfig

八， dpkg命令
查看python2.5是否安装： dpkg -l python2.5
查看名称含有python的所有软件： dpkg -l | grep python
查看python2.5软件包的位置： dpkg -L python2.5

九， 分区情况
查看所有分区情况： df -h
查看某个软件在哪个分区： df -h ***


命令行下载工具 ，转自：http://blog.chinaunix.net/u/9465/showart.php?id=186155，方便在虚拟机上开发，不用再从外面拷贝到虚拟机上了。

   对于喜欢命令行操作及追求高效率、高速度下载的朋友，推荐使用命令行下载工具。命令行工具不但使用方便，而且大多具有很高的下载速度及下载效率，尤其适合 于大批量下载文件。下面就为大家详细介绍一下这些工具。

    Wget     Wget是一个十分常用命令行下载工具，多数Linux发行版本都默认包含这个工具。如果没有安装可在http://www.gnu.org/software/wget/wget.html下 载最新版本，并使用如下命令编译安装：
    #tar zxvf wget-1.9.1.tar.gz
    #cd wget-1.9.1 #./configure
    #make #make install
它的用法很简单，Wget使用格式如下： #wget [选项] [下载地址] 1.Wget常用参数 ◆-b：后台下载，Wget默认的是把文件下载到当前目录。 ◆-O：将文件下载到指定的目录中。 ◆-P：保存文件之前先创建指定名称的目录。 ◆-t：尝试连接次数，当Wget无法与服务器建立连接时，尝试连接多少次。 ◆-c：断点续传，如果下载中断，那么连接恢复时会从上次断点开始下载。     除了上述常用功能，Wget还支持HTTP和FTP代理功能，编辑其配置文件“/etc/wgetrc”即可。具体方法是使用VI编辑器打开上述文件，将 “http_proxy”和“ftp_proxoy”前的#去掉，然后在这两项后输入相应的代理服务器的地址，保存退出即可。此外，Wget还可下载整个 网站，如下载http://man.chinaunix.net整个Man手册中心。只需输入如下命令即可： #wget -r -p -np -k http://man.chinaunix.net 其中-r参数是指使用递归下载，-p是指下载所有显示完整网页所以需要的文件，如图片等，-np是指不搜索上层目录，-k则是指将绝对链接转换为相对链 接。

     Prozilla     Prozilla也是一个十分流行的命令行下载工具，支持多线程下载和断点续传功能。可到http://prozilla.genesys.ro/下 载最新的1.3.7.4安装包，下载安装包后使用如下命令进行安装：
    #tar zxvf prozilla-1.3.7.4.tar.gz
    #cd prozilla-1.3.7.4
    #./configure #make
    #make install
Prozilla命令格式如下： #proz [参数] [下载地址] 常用的选项有： ◆-k=n ：设置n个线程下载。不加此参数指定线程数，Prozilla默认为4线程下载。 ◆-P, --directory-prefix=DIR：指定将下载的文件保存在DIR/目录。 ◆-r, --resume：继续下载未完成的文件。如果要指定线程数下载可用如下命令： #proz -k=5 http://64.12.204.21/pub/mozilla.org/firefox/releases/1.0/linux-i686/zh-CN/firefox-1.0.installer.tar.gz 这样便以5线程进行文件的下载，并将文件保存到当前目录。和Wget一样，Prozilla也提供了续传功能，下载中断后，重新输入上述命令，就会出现提 示续传，按R键就可继续下载了。

     MyGet     MyGet目标设计成一个可扩展的，拥有丰富界面的多线程下载工具，它支持HTTP、FTP、HTTPS、MMS、RTSP等协议。在http://myget.sourceforge.net/release/myget-0.1.0.tar.bz2下 载其最新版本0.1.0，下载后使用如下命令安装：
     #tar jxvf myget-0.1.0.tar.bz2
    #cd myget-0.1.0 #./configure
    #make
    #make install
MyGet命令格式如下： #mytget [选项] [下载地址] 常用的选项： ◆-d [目录]：指定下载到的文件在本地存放的位置，默认当前目录。 ◆-f [文件]：指定下载文件名称。 ◆-h：帮助选项。 ◆-n [线程数]：下载线程数量，默认为4个。 ◆-x [代理服务器地址]：设置代理服务器地址，如“-x http://user:password@host:port”。 MyGet常用的形式如下： #mytget －d /root/ -n 10 http://lumaqq.linuxsir.org/download/patch/lumaqq_2004t_patch_2005.07.21.00.00.zip        

    Linuxdown     Linuxdown是一个命令行多线程下载工具，最多可支持30线程的下载。在https://gro.clinux.org/frs/download.php/1015/linuxdown-1.0.0.tar.gz下 载最新的1.1.0版本。然后使用如下命令进行编译安装：
    #tar zxvf linuxdown-1.1.0.tar.gz
    #cd dandelion/
    #make
    #make install
linuxdown格式为： #linuxdown [下载地址] [选项] [线程数]     需要注意的是下载地址和选项都需要西文引号括起来，线程数不可超过30个。一个典型的下载如下： #linuxdown "http://lumaqq.linuxsir.org/download/patch/lumaqq_2004t_patch_2005.07.21.00.00.zip" 30

    Curl     Curl也是Linux下不错的命令行下载工具，小巧、高速，唯一的缺点是不支持多线程下载。在http://curl.haxx.se/download/curl-7.14.0.tar.gz下 载最新版本。下载后便可使用如下命令编译安装：         #tar zxvf curl-7.14.0.tar.gz
    #cd curl-7.14.0/
    #./configure
    #make
    #make test
    #make install
Curl使用格式如下： #curl [选项][下载地址] Curl典型下载如下： #curl -O http://10.1.27.10/~kennycx/tools/lumaqq_2004-linux_gtk2_x86_with_jre.tar.gz     使用Curl下载一个文件并保存到当前目录。此外，Curl虽然不支持多线程下载，但它可同时下载多个文件或下载文件的某一部分，可使用如下命令实现： #curl -r 0-199 http://www.netscape.com/ 获得文件的前200 bytes。     对于常用的代理下载Curl也可轻松实现，具体操作如下： #curl -x 10.1.27.10:1022 ftp://ftp.funet.fi/README 使用代理地址为10.1.27.10端口为1022的代理服务器下载一个文件。 #curl -U user:passwd -x 10.1.27.10:1022 ftp://ftp.funet.fi/README 如果代理服务器需要特别的验证，则需要在user:passwd处输入合法的帐号和密码。

    Axel     Axel是命令行下的多线程下载工具，支持断点续传，速度通常情况下是Wget的几倍。可在http://www.linuxfans.org/nuke/modules.php?name=Site_Downloads&op=mydown&did=1697下 载。下载后使用如下命令编译安装：
    #tar zxvf axel-1.0a.tar.gz
    #cd axel-1.0a/
    #./configure
    #make
    #make install
基本的用法如下： #axel [选项] [下载目录] [下载地址] 一个典型下载如下： #alex -n 10 -o /home/kennycx/ http://10.1.27.10/~kennycx/tools/lumaqq_2004-linux_gtk2_x86_with_jre.tar.gz 用10线程将指定路径的文件下载到/home/kennycx/这个目录下。     本文详细介绍了Linux中常用的下载工具，这些下载工具功能上各有千秋，使用上都比较简单，所以无论是初学者还是Linux高手总有一款适合你。

Hashtable和HashMap类有三个重要的不同之处。第一个不同主要是历史原因。Hashtable是基于陈旧的Dictionary类的，HashMap是Java 1.2引进的Map接口的一个实现。 也许最重要的不同是Hashtable的方法是同步的，而HashMap的方法不是。这就意味着，虽然你可以不用采取任何特殊的行为就可以在一个多线程的应用程序中用一个Hashtable，但你必须同样地为一个HashMap提供外同步。一个方便的方法就是利用Collections类的静态的synchronizedMap()方法，它创建一个线程安全的Map对象，并把它作为一个封装的对象来返回。这个对象的方法可以让你同步访问潜在的HashMap。这么做的结果就是当你不需要同步时，你不能切断Hashtable中的同步（比如在一个单线程的应用程序中），而且同步增加了很多处理费用。 第三点不同是，只有HashMap可以让你将空值作为一个表的条目的key或value。HashMap中只有一条记录可以是一个空的key，但任意数量的条目可以是空的value。这就是说，如果在表中没有发现搜索键，或者如果发现了搜索键，但它是一个空的值，那么get()将返回null。如果有必要，用containKey()方法来区别这两种情况。 一些资料建议，当需要同步时，用Hashtable，反之用HashMap。但是，因为在需要时，HashMap可以被同步，HashMap的功能比Hashtable的功能更多，而且它不是基于一个陈旧的类的，所以有人认为，在各种情况下，HashMap都优先于Hashtable。 关于Properties 有时侯，你可能想用一个hashtable来映射key的字符串到value的字符串。DOS、Windows和Unix中的环境字符串就有一些例子，如key的字符串PATH被映射到value的字符串C:\WINDOWS;C:\WINDOWS\SYSTEM。Hashtables是表示这些的一个简单的方法，但Java提供了另外一种方法。 Java.util.Properties类是Hashtable的一个子类，设计用于String keys和values。Properties对象的用法同Hashtable的用法相象，但是类增加了两个节省时间的方法，你应该知道。 Store()方法把一个Properties对象的内容以一种可读的形式保存到一个文件中。Load()方法正好相反，用来读取文件，并设定Properties对象来包含keys和values。 注意，因为Properties扩展了Hashtable，你可以用超类的put()方法来添加不是String对象的keys和values。这是不可取的。另外，如果你将store()用于一个不包含String对象的Properties对象，store()将失败。作为put()和get()的替代，你应该用setProperty()和getProperty()，它们用String参数。 好了，我希望你现在可以知道如何用hashtables来加速你的处理了。     下面再转一篇关于两个类的区别，比较简单的过一下 最近同学找工作，经常被问到这个问题rt，所以。。。。。。   HashTable的应用非常广泛，HashMap是新框架中用来代替HashTable的类，也就是说建议使用HashMap，不要使用HashTable。   这里简单分析他们的区别。  1.HashTable的方法是同步的，HashMap未经同步，所以在多线程场合要手动同步HashMap这个区别就像Vector和ArrayList一样。（最主要的区别） 2.HashTable不允许null值(key和value都不可以),HashMap允许null值(key和value都可以，只容许有一个null值的key，可以有多个null值的value)。 3.HashTable有一个contains(Object value)，功能和containsValue(Object value)功能一样。 4.HashTable使用Enumeration，HashMap使用Iterator。 以上只是表面的不同，它们的实现也有很大的不同。 5.HashTable中hash数组默认大小是11，增加的方式是 old*2+1。HashMap中hash数组的默认大小是16，而且一定是2的指数。 6.哈希值的使用不同，HashTable直接使用对象的hashCode，代码是这样的： int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; 而HashMap重新计算hash值，而且用与代替求模： int hash = hash(k); int i = indexFor(hash, table.length); static int hash(Object x) { 　　 int h = x.hashCode(); 　　 h += ~(h << 9); 　　 h ^= (h >>> 14); 　　 h += (h << 4); 　　 h ^= (h >>> 10); 　　 return h; } static int indexFor(int h, int length) { 　　 return h & (length-1); } 以上只是一些比较突出的区别，当然他们的实现上还是有很多不同的，比如 HashMap对null的操作。

java.math.Math类常用的常量和方法：

Math.PI 记录的圆周率
Math.E记录e的常量
Math.abs 求绝对值
Math.sin 正弦函数 Math.asin 反正弦函数
Math.cos 余弦函数 Math.acos 反余弦函数
Math.tan 正切函数 Math.atan 反正切函数&nbsp;Math.atan2 商的反正切函数
Math.toDegrees 弧度转化为角度 Math.toRadians 角度转化为弧度
Math.ceil 得到不小于某数的最大整数
Math.floor 得到不大于某数的最大整数
Math.IEEEremainder 求余
Math.max 求两数中最大
Math.min 求两数中最小
Math.sqrt 求开方
Math.pow 求某数的任意次方, 抛出ArithmeticException处理溢出异常
Math.exp 求e的任意次方
Math.log10 以10为底的对数
Math.log 自然对数
Math.rint 求距离某数最近的整数（可能比某数大，也可能比它小）
Math.round 同上，返回int型或者long型（上一个函数返回double型）
Math.random 返回0，1之间的一个随机数

java.math.BigInteger(大整数)：
BigInteger bi1=new BigInteger("1234567890123456890");
BigInteger bi2=BigInteger.valueOf(123L);
bi1=bi1.add(bi2);//b1+b2
bi1=bi1.multiply(bi2);//b1*b2
bi1=bi1.subtract(bi2);//b1-b2
bi1=bi1.divide(bi2);// b1/b2

java.math.BigDecimal(大浮点数):
BigDecimal bd = new BigDecimal("3.1415926");
bd = bd.setScale(2,BigDecimal.ROUND_DOWN);//取3.1415926小数点后面二位

1、classpath不用再定义.;***\lib\tools.jar;***\lib\rt.jar，因为jre会自动寻找lib目录

2、如果想要用jdk5.0编译出jdk1.4可运行的class文件需要带-source和-target两个参数
eg: javac -source 1.4 -target 1.4 Hello.java

3、命令行读入int i = System.in.read();//读入输入字符串的第一个字符的int值；
读整个字符串时：
public class Test{
 public static void main(String[] args){
  byte[] a = new byte[100];
  try {
   System.in.read(a);
  } catch (IOException e) {
   e.printStackTrace();
  }
  System.out.println(new String(a));
 }
}

jdk5.0中命令行读入的方法更好，可以读成不同类型的数据：
//Scanner取得输入的依据是：空格键、Tab键或Enter键
import java.util.Scanner;

public class ScannerDemo{
 public static void main(String[] args){
  Scanner scanner = new Scanner(System.in);
  System.out.print("请输入姓名");
  System.out.printf("您好%s!\n", scanner.next());
  System.out.print("请输入年龄");
  System.out.printf("您好%d!\n", scanner.nextInt());
  //还有scanner.nextFloat(),scanner.nextBoolean();
 }
}

//BufferReader取得输入的依据是：Enter键
import java.io.*;

public class BufferReaderDemo{
 public static void main(String[] args){
  BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
  System.out.print("请输入一系列文字");
  String text = bufferedReader.readLine();
  System.out.print("您输入的是：" + text);
 }
 }
}

4、aotuboxing和unboxing，jdk5.0可以自动对基本类型和它们的包装类型自动转换。

5、数组
数组的索引值:由0开始的原因：索引值表示偏移量，第一个值的偏移为0.

数组的初始化：byte/short/int = 0; long = ol; float = o.0f; double = 0.0d; char = \u0000; boolean = false; Objective = null;

一维数组：
法一：int[] i = {1,2,3};
法二：int[] i = new int[]{1,2,3};
法三：int[] i = new int[3]; i[0] = 1; i[1] = 2; i[2] = 3;

多维数组：
法一：int[][] i = {{...},...,{...}};
法二：int[][] i = int[][]{{...},...,{...}};
法三：int[][] i = int[3][]; i[0] = {1,2,3}; i[0] = {1,2,3}; i[0] = {1,2,3};
法四：int[][] i = int[3][3];

不规则数组：行列不等

数组的常用方法：都是java.util.Arrays类的方法
sort()//制定数组快速排序
binarySearch()//对已排序的数组搜索，找到返回索引，否则返回负值
fill()//根据数组的数据类型填默认值
equals()//比较两数组
jdk1.5中新增:
deepEquals()//深度比较
deepToString()//深度输出

foreach与数组：
String[] a = {"asd","efge","efg"};
for(String s : a)
 System.out.println(s);

5、字符串
java.lang.StringBuilder是jdk5.0新增的类，它与StringBuffer具有相同接口，只是单机非多线程情况下用StringBuilder效率较高，因为StringBuilder没处理同步问题；多线程下用StringBuffer好。

字符串分离：
 String s = "23/twomen/tlai/t jeje";
 String[] a = s.split("/t");
 for(int i = 0; i < a.length; i++){
  System.out.print(a[i] +　" ");
 }
输出结构：23 women lai  jeje

由于工作关系学习jdk5.0的步伐暂时停止，以后有机会继续看《jdk5.0学习笔记》，回来写我的总结。

1 术语定义

在字符串匹配问题中，我们期待察看串T中是否含有串P。
其中串T被称为目标串，串S被称为模式串。

2 朴素匹配算法

进行字符串匹配，最简单的一个想法是：

可以看见，这个算法（假定m>>n）的复杂度是O(mn)，其中m是T的长度，n是P的长度。这种算法的缺陷是匹配过程中带有回溯——准确地说是T串存在回溯，也就是当匹配不成功的时候，之前进行的匹配完全变为无用功，所有的比较需要重新开始。

3 KMP算法

KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt提出的无回溯的字符串匹配算法，算法的核心思想就是设法在匹配失败的时候，尽量利用之前的匹配结果，消除T串的回溯问题。那么如何消除回溯呢？请看下面的例子：

假设P=abacd，如果T=abax...，当从头开始匹配到字符c时，若c=x，显然，匹配过程继续；当c≠x时，按照朴素的匹配算法，T串会发生回溯，之后T串会从第2个字符b开始重新匹配，而不是从匹配失败的字符x开始继续。但是显然，对于上述的匹配过程，T串不需要从b开始重新匹配，它只需要从x开始和P的b字符继续匹配即可。如下：
匹配过程：
P=abacd
T=abax....
     ^----比较到此处时发生匹配失败
朴素匹配算法：
P= abacd
T=abax...
   ^----回溯到b，重新开始和P的匹配
KMP算法：
P=  abacd
T=abax...
     ^----T串不回溯，从x处继续匹配

现在的问题是，按照KMP算法，匹配失败的时候，P串需要重新调整位置，但是调整的依据是什么？Knuth等人发现，P调整位置的依据和P的构造有关，和T无关。具体来说，定义失效函数：f(j)=k，其中0<=k<=j，且k是使得p₀p₁...p_k-1 = p_j-k+1p_j-k+2...p_j成立的最大整数。建立失效函数的算法如下：
public void Build() {
 if(pattern == null)
  throw new Exception("KMP Exception : null pattern");
 array = new int[pattern.Length];
 int i = 0, s = pattern.Length;
 if(s > 1)
  array[0] = 0;
 for(i = 1; i < s; i++) {
  if(pattern[i] == pattern[array[i - 1]])
   array[i] = array[i - 1] + 1;
  else
   array[i] = 0;
 }
}

匹配过程如下：
public int Match(String target, int start) {
 if(array == null || pattern == null || target == null)
  return -1;
 int target_index = start;
 int pattern_index = 0;
 int token_length = target.Length;
 int pattern_length = pattern.Length;
 while(target_index < token_length && pattern_index < pattern_length) {
  if(target[target_index] == pattern[pattern_index]) {
   target_index++;
   pattern_index++;
  } else {
   if(pattern_index == begin)
    target_index++;
   else
    pattern_index = array[pattern_index - 1];
  }
 }
 if(pattern_index == pattern_length)
  return target_index - pattern_length;
 return -1;
}

4 支持通配符?和*的KMP算法

KMP算法虽然能够进行字符串匹配，但是，在实践中字符串匹配往往还要支持通配符，MS系统中最常见的通配符是?和*。其中，?可以代表一个字符（不能没有），*可以代表任意多个字符（可以为空）。经典的KMP算法针对通配符是无能为力的，但是经过简单的改造，KMP算法也可以识别通配符。

首先是?，根据?的功能，?表示任意字符，也就是说在匹配过程中，?永远匹配成功。因此对匹配函数的修改十分简单：
...
 while(target_index < token_length && pattern_index < pattern_length) {
  if(target[target_index] == pattern[pattern_index]|| pattern[pattern_index] == '?') {
   target_index++;
   pattern_index++;
  } else {
...
建立失效函数的过程和匹配过程类似，修改如下：
...
 for(i = 1; i < s; i++) {
  if(pattern[i] == pattern[array[i - 1]]|| pattern[i] == '?' || pattern[array[i - 1]] == '?')
   array[i] = array[i - 1] + 1;
...

本质上，?并没有修改算法，而仅仅修改了匹配规则——遇到?则一定匹配。然而*与此不同，*的作用是匹配任意多个字符，显然我们不能简单的修改匹配过程而满足要求。如果我们重新思考*的作用，我们会发现*的另一个作用就是分割P串，即如果P=P₁*P₂，那么与其说*代表匹配任意多个字符，不如说P的匹配条件是在匹配P₁子串后再匹配P₂子串。

现在回顾失效函数的作用，如果当匹配到P的j+1位时匹配失败，那么重新开始匹配的时候，P串的位置调整到f(j)位，直到P串的位置调整到0，则匹配重新开始。但当P=P₁*P₂，假如P₁已经匹配成功，而在P₂中发生匹配失败，那么P串要需要调整位置，但P串无论如何调整，此时也不应该调整到0，最多调整到P₂的开始处，因为P₁已经匹配，只需匹配P₂即可。假如P=abcab*abcab，失效函数应该是（注意之前提到*的作用）：
a b c a b * a b c a b
0 0 0 1 2 - 6 6 6 7 8

因此，要想让KMP支持*，那么关键是要重新设计失效函数的建立算法，如下：
public void Build() {
 if(pattern == null)
  throw new Exception("KMP Exception : null pattern");
 array = new int[pattern.Length];
 int i = 0, s = pattern.Length;
 if(s > 1)
  array[0] = 0;
 int begin = 0;
 for(i = 1; i < s; i++) {
  if(pattern[i] == '*') {
   array[i] = i;
   begin = i + 1;
  } else if(pattern[i] == pattern[array[i - 1]] || pattern[i] == '?' || pattern[array[i - 1]] == '?')
   array[i] = array[i - 1] + 1;
  else
   array[i] = begin;
 }
} 

算法中begin表示每段字符串的开始位置。此外，匹配过程也应该进行相应的修改，因为字符*对于匹配没有任何帮助，它属于占位符，因此需要跳过，匹配算法如下：
public int Match(String target, int start) {
 if(array == null || pattern == null || target == null)
  return -1;
 int target_index = start;
 int pattern_index = 0;
 int token_length = target.Length;
 int pattern_length = pattern.Length;
 int begin = 0;
 while(target_index < token_length && pattern_index < pattern_length) {
  if(pattern[pattern_index] == '*') {
   begin = pattern_index + 1;
   pattern_index++;
  } else if(target[target_index] == pattern[pattern_index] || pattern[pattern_index] == '?') {
   target_index++;
   pattern_index++;
  } else {
   if(pattern_index == begin)
    target_index++;
   else
    pattern_index = array[pattern_index - 1];
  }
 }
 if(pattern_index == pattern_length)
  return target_index - pattern_length + begin;
 return -1;
}

5 正则语言和确定状态自动机

一个数字逻辑的问题：设计一个识别11011的电路，解这个问题的关键就是设计出这个电路的DFA，如下：

仔细看看这个状态机，是不是和KMP的算法有几分类似呢？这并不是巧合，因为KMP算法中的失效函数总可以等价的转化为一个DFA。当然KMP的DFA远比识别11011的DFA要复杂，原因在于KMP接受的输入是全体字符集合，识别11011的DFA只接受0和1这两个输入。我们知道，一个正则语言和一个DFA是等价的，而KMP计算失效函数的算法，实际上等价于求DFA的过程，f(j)的值实际上表明状态j+1接受到不正确的字符时应该回溯到的状态（注意此时输入流并没有前进）。普通的字符串都能看成是一个正则语言，含有通配符?和*的字符串也可以等价的转换为一个正则表达式。但是，正则语言的集合远比KMP算法所能支持的模式集合的更大，期间原因还是刚才提过的输入问题。试想P=p₁p₂...p_n，当匹配到p_j的时候，如果下一个输入字符正是p_j，那么状态机进入下一个状态，如果不是p_j，那么状态机按照实效函数的指示转移到状态f(j-1)，也就是说KMP状态机的每个状态只能根据输入是否为p_j来进行转移。而正则表达式所对应的状态机则有所不同，如果正则语言L=l₁l₂...l_n，假设这些都是字母，当匹配到l_j位的时候，如果下一个输入字符正是l_j，那么状态机进入下一个状态，否则它还可以根据输入的值进行转移，例如l_j=c₁时转换到状态x，l_j=c₂时状态转换到y等等。

6 结语

字符串匹配问题是老问题了，并没有太多新意可言，只不过虽然KMP算法十分简单，但它的内在含义还是十分深刻的。横向比较KMP、DFA和正则语言、正则表达式我们会发现，它们之间存在很多的关联，而这种比较也有利于我们更好的理解这些算法，或者改进这些算法。最后说一句，试图利用目前的框架使得KMP算法支持全部种类的通配符（对应于正则表达式就是x?、x*、x+、{m,n}等等）是不可能，而我们也不需要这么做，因为我们还有正则表达式嘛。

只要这样定义图，根本不用在代码中写IF ELSE语句。
实际上基于图的算法好处在于，只要你能定义好满足题目要求的图结构，遍历的结果就是你要的结果，不用任何对遍历结果做任何处理。包括本题中的：4不能在第三位置，3，5不能相连，唯一性要求，其实都可以在体现在构造的图形结构里，然后直接遍历图取得自己要的结果。而不用再次处理结果集。只是说这里实际上对其它要求要体现在图结构里有困难（理论上是可以的），但起码3，5不能相接是很好构造的，就是上面的代码段来解释的。

关于图形数据结构建议先看看数据结构的书，主要是将如何利用二维数组描述图结构，再看看图的深度遍历实现原理。最后再应用到这个问题上来，自然就不难明白了。

（转自：http://chinavery.100steps.net/chengxuyuan/4759.html）
动态规划是本书介绍的五种算法设计方法中难度最大的一种，它建立在最优原则的基础上。采用动态规划方法，可以优雅而高效地解决许多用贪婪算法或分而治之算法无法解决的问题。在介绍动态规划的原理之后，本章将分别考察动态规划方法在解决背包问题、图象压缩、矩阵乘法链、最短路径、无交叉子集和元件折叠等方面的应用。

3.1 算法思想

和贪婪算法一样，在动态规划中，可将一个问题的解决方案视为一系列决策的结果。不同的是，在贪婪算法中，每采用一次贪婪准则便做出一个不可撤回的决策，而在动态规划中，还要考察每个最优决策序列中是否包含一个最优子序列。

例3-1 [最短路经] 考察图1 2 - 2中的有向图。假设要寻找一条从源节点s= 1到目的节点d= 5的最短路径，即选择此路径所经过的各个节点。第一步可选择节点2，3或4。假设选择了节点3，则此时所要求解的问题变成：选择一条从3到5的最短路径。如果3到5的路径不是最短的，则从1开始经过3和5的路径也不会是最短的。例如，若选择的子路径（非最短路径）是3，2，5 (耗费为9 )，则1到5的路径为1，3，2，5 (耗费为11 )，这比选择最短子路径3，4，5而得到的1到5的路径1，3，4，5 (耗费为9) 耗费更大。

所以在最短路径问题中，假如在的第一次决策时到达了某个节点v，那么不管v 是怎样确定的，此后选择从v 到d 的路径时，都必须采用最优策略。

例3-2 [0/1背包问题] 考察1 3 . 4节的0 / 1背包问题。如前所述，在该问题中需要决定x1 .. xn的值。假设按i = 1，2，.，n 的次序来确定xi 的值。如果置x1 = 0，则问题转变为相对于其余物品（即物品2，3，.，n），背包容量仍为c 的背包问题。若置x1 = 1，问题就变为关于最大背包容量为c-w1 的问题。现设r?{c，c-w1 } 为剩余的背包容量。

在第一次决策之后，剩下的问题便是考虑背包容量为r 时的决策。不管x1 是0或是1，[x2 ，.，xn ] 必须是第一次决策之后的一个最优方案，如果不是，则会有一个更好的方案[y2，.，yn ]，因而[x1，y2，.，yn ]是一个更好的方案。

假设n=3, w=[100,14,10], p=[20,18,15], c= 11 6。若设x1 = 1，则在本次决策之后，可用的背包容量为r= 116-100=16 。[x2，x3 ]=[0,1] 符合容量限制的条件，所得值为1 5，但因为[x2，x3 ]= [1，0] 同样符合容量条件且所得值为1 8，因此[x2，x3 ] = [ 0，1] 并非最优策略。即x= [ 1，0，1] 可改进为x= [ 1，1，0 ]。若设x1 = 0，则对于剩下的两种物品而言，容量限制条件为11 6。总之，如果子问题的结果[x2，x3 ]不是剩余情况下的一个最优解，则[x1，x2，x3 ]也不会是总体的最优解。

例3-3 [航费] 某航线价格表为：从亚特兰大到纽约或芝加哥，或从洛杉矶到亚特兰大的费用为$ 1 0 0；从芝加哥到纽约票价$ 2 0；而对于路经亚特兰大的旅客，从亚特兰大到芝加哥的费用仅为$ 2 0。从洛杉矶到纽约的航线涉及到对中转机场的选择。如果问题状态的形式为（起点，终点），那么在选择从洛杉矶到亚特兰大后，问题的状态变为（亚特兰大，纽约）。从亚特兰大到纽约的最便宜航线是从亚特兰大直飞纽约，票价$ 1 0 0。而使用直飞方式时，从洛杉矶到纽约的花费为$ 2 0 0。不过，从洛杉矶到纽约的最便宜航线为洛杉矶-亚特兰大-芝加哥-纽约，其总花费为$ 1 4 0（在处理局部最优路径亚特兰大到纽约过程中选择了最低花费的路径：亚特兰大-芝加哥-纽约）。

如果用三维数组（t a g，起点，终点）表示问题状态，其中t a g为0表示转飞， t a g为1表示其他情形，那么在到达亚特兰大后，状态的三维数组将变为（ 0，亚特兰大，纽约），它对应的最优路径是经由芝加哥的那条路径。

当最优决策序列中包含最优决策子序列时，可建立动态规划递归方程（ d y n a m i c -programming recurrence equation），它可以帮助我们高效地解决问题。

例3-4 [0/1背包] 在例3 - 2的0 / 1背包问题中，最优决策序列由最优决策子序列组成。假设f (i,y) 表示例1 5 - 2中剩余容量为y，剩余物品为i，i + 1，.，n 时的最优解的值，即：和利用最优序列由最优子序列构成的结论，可得到f 的递归式。f ( 1 ,c) 是初始时背包问题的最优解。可使用（ 1 5 - 2）式通过递归或迭代来求解f ( 1 ,c)。从f (n, * )开始迭式， f (n, * )由（1 5 - 1）式得出，然后由（ 1 5 - 2）式递归计算f (i,*) ( i=n- 1，n- 2，.， 2 )，最后由（ 1 5 - 2）式得出f ( 1 ,c)。

对于例1 5 - 2，若0≤y＜1 0，则f ( 3 ,y) = 0；若y≥1 0，f ( 3 ,y) = 1 5。利用递归式（1 5 - 2），可得f (2, y) = 0 ( 0≤y＜10 )；f（2，y）= 1 5（1 0≤y＜1 4）；f（2，y）= 1 8（1 4≤y＜2 4）和f（2，y）= 3 3（y≥2 4）。因此最优解f ( 1 , 11 6 ) = m a x {f（2，11 6），f（2，11 6 - w1）+ p1} = m a x {f（2，11 6），f（2，1 6）+ 2 0 } = m a x { 3 3，3 8 } = 3 8。

现在计算xi 值，步骤如下：若f ( 1 ,c) =f ( 2 ,c)，则x1 = 0，否则x1 = 1。接下来需从剩余容量c-w1中寻求最优解，用f (2, c-w1) 表示最优解。依此类推，可得到所有的xi (i= 1.n) 值。

在该例中，可得出f ( 2 , 11 6 ) = 3 3≠f ( 1 , 11 6 )，所以x1 = 1。接着利用返回值3 8 -p1=18 计算x2 及x3，此时r = 11 6 -w1 = 1 6，又由f ( 2 , 1 6 ) = 1 8，得f ( 3 , 1 6 ) = 1 4≠f ( 2 , 1 6 )，因此x2 = 1，此时r= 1 6 -w2 = 2，所以f (3,2) =0，即得x3 = 0。

动态规划方法采用最优原则（ principle of optimality）来建立用于计算最优解的递归式。所谓最优原则即不管前面的策略如何，此后的决策必须是基于当前状态（由上一次决策产生）的最优决策。由于对于有些问题的某些递归式来说并不一定能保证最优原则，因此在求解问题时有必要对它进行验证。若不能保持最优原则，则不可应用动态规划方法。在得到最优解的递归式之后，需要执行回溯（t r a c e b a c k）以构造最优解。

编写一个简单的递归程序来求解动态规划递归方程是一件很诱人的事。然而，正如我们将在下文看到的，如果不努力地去避免重复计算，递归程序的复杂性将非常可观。如果在递归程序设计中解决了重复计算问题时，复杂性将急剧下降。动态规划递归方程也可用迭代方式来求解，这时很自然地避免了重复计算。尽管迭代程序与避免重复计算的递归程序有相同的复杂性，但迭代程序不需要附加的递归栈空间，因此将比避免重复计算的递归程序更快。

3.2 应用

3.2.1 0/1背包问题

1. 递归策略

在例3 - 4中已建立了背包问题的动态规划递归方程，求解递归式（ 1 5 - 2）的一个很自然的方法便是使用程序1 5 - 1中的递归算法。该模块假设p、w 和n 为输入，且p 为整型，F(1,c) 返回f ( 1 ,c) 值。

程序15-1 背包问题的递归函数

int F(int i, int y)

{// 返回f ( i , y ) .

if (i == n) return (y < w[n]) ? 0 : p[n];

if (y < w[i]) return F(i+1,y);

return max(F(i+1,y), F(i+1,y-w[i]) + p[i]);

}

程序1 5 - 1的时间复杂性t (n)满足：t ( 1 ) =a；t（n）≤2t（n- 1）+b（n＞1），其中a、b 为常数。通过求解可得t (n) =O( 2n)。

例3-5 设n= 5，p= [ 6 , 3 , 5 , 4 , 6 ]，w=[2,2,6,5,4] 且c= 1 0 ,求f ( 1 , 1 0 )。为了确定f ( 1 , 1 0 )，调用函数F ( 1 , 1 0 )。递归调用的关系如图1 5 - 1的树型结构所示。每个节点用y值来标记。对于第j层的节点有i=j，因此根节点表示F ( 1 , 1 0 )，而它有左孩子和右孩子，分别对应F ( 2 , 1 0 )和F ( 2 , 8 )。总共执行了2 8次递归调用。但我们注意到，其中可能含有重复前面工作的节点，如f ( 3 , 8 )计算过两次，相同情况的还有f ( 4 , 8 )、f ( 4 , 6 )、f ( 4 , 2 )、f ( 5 , 8 )、f ( 5 , 6 )、f ( 5 , 3 )、f (5,2) 和f ( 5 , 1 )。如果保留以前的计算结果，则可将节点数减至1 9，因为可以丢弃图中的阴影节点。

正如在例3 - 5中所看到的，程序1 5 - 1做了一些不必要的工作。为了避免f (i,y)的重复计算，必须定义一个用于保留已被计算出的f (i,y)值的表格L，该表格的元素是三元组(i,y,f (i,y) )。在计算每一个f (i,y)之前，应检查表L中是否已包含一个三元组(i,y, * )，其中*表示任意值。如果已包含，则从该表中取出f (i,y)的值，否则，对f (i,y)进行计算并将计算所得的三元组(i,y,f (i,y) )加入表L。L既可以用散列（见7 . 4节）的形式存储，也可用二叉搜索树(见11章)的形式存储。

2. 权为整数的迭代方法

当权为整数时，可设计一个相当简单的算法（见程序1 5 - 2）来求解f ( 1 ,c)。该算法基于例3 - 4所给出的策略，因此每个f (i,y) 只计算一次。程序1 5 - 2用二维数组f [ ][ ]来保存各f 的值。而回溯函数Tr a c e b a c k用于确定由程序1 5 - 2所产生的xi 值。函数K n a p s a c k的复杂性为( n c），而Tr a c e b a c k的复杂性为( n )。

程序15-2 f 和x 的迭代计算

template<class T>

void Knapsack(T p[], int w[], int c, int n, T** f)

{// 对于所有i和y计算f [ i ] [ y ]

// 初始化f [ n ] [ ]

for (int y = 0; y <= yMax; y++)

f[n][y] = 0;

for (int y = w[n]; y <= c; y++)

f[n][y] = p[n];

// 计算剩下的f

for (int i = n - 1; i > 1; i--) {

for (int y = 0; y <= yMax; y++)

f[i][y] = f[i+1][y];

for (int y = w[i]; y <= c; y++)

f[i][y] = max(f[i+1][y], f[i+1][y-w[i]] + p[i]);

}

f[1][c] = f[2][c];

if (c >= w[1])

f[1][c] = max(f[1][c], f[2][c-w[1]] + p[1]);

}

template<class T>

void Traceback(T **f, int w[], int c, int n, int x[])

{// 计算x

for (int i = 1; i < n; i++)

if (f[i][c] == f[i+1][c]) x[i] = 0;

else {x[i] = 1;

c -= w[i];}

x[n] = (f[n][c]) ? 1 : 0;

}

3. 元组方法（ 选读）

程序1 5 - 2有两个缺点：1) 要求权为整数；2) 当背包容量c 很大时，程序1 5 - 2的速度慢于程序1 5 - 1。一般情况下，若c＞2n，程序1 5 - 2的复杂性为W (n2n )。可利用元组的方法来克服上述两个缺点。在元组方法中，对于每个i，f (i, y) 都以数对(y, f (i, y)) 的形式按y的递增次序存储于表P(i)中。同时，由于f (i, y) 是y 的非递减函数，因此P(i) 中各数对(y, f (i, y)) 也是按f (i, y) 的递增次序排列的。

例3-6 条件同例3 - 5。对f 的计算如图1 5 - 2所示。当i= 5时，f 由数对集合P( 5 ) = [ ( 0 , 0 ) , ( 4 , 6 ) ]表示。而P( 4 )、P( 3 )和P( 2 )分别为[ ( 0 , 0 ) , ( 4 , 6 ) , ( 9 , 1 0 ) ]、[ ( 0 , 0 ) ( 4 , 6 ) , ( 9 , 1 0 ) , ( 1 0 , 11)] 和[ ( 0 , 0 ) ( 2 , 3 ) ( 4 , 6 ) ( 6 , 9 ) ( 9 , 1 0 ) ( 1 0 , 11 ) ]。

为求f ( 1 , 1 0 )，利用式（1 5 - 2）得f ( 1 , 1 0 ) = m a x｛f ( 2 , 1 0 )，f ( 2 , 8 ) + p 1｝。由P( 2 )得f ( 2 , 1 0 ) = 11、f (2,8)=9 (f ( 2 , 8 ) = 9来自数对( 6，9 ) )，因此f ( 1 , 1 0 ) = m a x｛11 , 1 5｝= 1 5。现在来求xi 的值，因为f ( 1 , 1 0 ) =f ( 2 , 6 ) +p1，所以x1 = 1；由f ( 2 , 6 ) =f ( 3 , 6 - w 2 ) +p2 =f ( 3 , 4 ) +p2，得x2 = 1；由f ( 3 , 4 ) =f ( 4 , 4 ) =f ( 5 , 4 )得x3=x4 = 0；最后，因f ( 5 , 4 )≠0得x5= 1。

检查每个P(i) 中的数对，可以发现每对(y,f (i,y)) 对应于变量xi , ., xn 的0/1 赋值的不同组合。设（a,b）和（c,d）是对应于两组不同xi , ., xn 的0 / 1赋值，若a≥c且b＜d，则(a, b) 受(b, c) 支配。被支配者不必加入P(i)中。若在相同的数对中有两个或更多的赋值，则只有一个放入P(i)。假设wn≤C，P(n)=[(0,0), (wn , pn ) ]，P（n）中对应于xn 的两个数对分别等于0和1。对于每个i，P(i)可由P(i+ 1 )得出。首先，要计算数对的有序集合Q，使得当且仅当wi≤s≤c且(s-wi , t-pi )为P(i+1) 中的一个数对时，（s,t）为Q中的一个数对。现在Q中包含xi = 1时的数对集，而P(i+ 1 )对应于xi = 0的数对集。接下来，合并Q和P(i+ 1 )并删除受支配者和重复值即可得到P(i)。

例3-7 各数据同例1 5 - 6。P(5)=[(0,0),(4,6)], 因此Q= [ ( 5 , 4 ) , ( 9 , 1 0 ) ]。现在要将P( 5 )和Q合并得到P( 4 )。因( 5 , 4 )受( 4 , 6 )支配，可删除( 5 , 4 )，所以P（4）=[(0,0), (4,6), (9,10)]。接着计算P( 3 )，首先由P( 4 )得Q=[(6,5), (10,11 ) ]，然后又由合并方法得P(3)=[(0,0), (4,6), (9,10), (10,11 ) ]。最后计算P( 2 )：由P( 3 )得Q= [ ( 2 , 3 )，( 6 , 9 ) ]，P( 3 )与Q合并得P(2)=[(0,0), (2,3), (4,6), (6,9), (9,10). (10,11 ) ]。因为每个P(i) 中的数对对应于xi , ., xn 的不同0 / 1赋值，因此P(i) 中的数对不会超过2n-i+ 1个。计算P(i) 时，计算Q需消耗( |P(i+ 1 ) |）的时间，合并P(i+1) 和Q同样需要( |P(i+ 1 ) | )的时间。计算所有P(i) 时所需要的总时间为： (n ?i=2|P(i + 1)|= O ( 2n )。当权为整数时，|P(i) |≤c+1, 此时复杂性为O ( m i n {n c, 2n } )。

如6 . 4 . 3节定义的，数字化图像是m×m的像素阵列。假定每个像素有一个0 ~ 2 5 5的灰度值。因此存储一个像素至多需8位。若每个像素存储都用最大位8位，则总的存储空间为8m2 位。为了减少存储空间，我们将采用变长模式（ variable bit scheme），即不同像素用不同位数来存储。像素值为0和1时只需1位存储空间；值2、3各需2位；值4，5，6和7各需3位；以此类推，使用变长模式的步骤如下：

1) 图像线性化根据图15-3a 中的折线将m×m维图像转换为1×m2 维矩阵。

2) 分段将像素组分成若干个段，分段原则是：每段中的像素位数相同。每个段是相邻像素的集合且每段最多含2 5 6个像素，因此，若相同位数的像素超过2 5 6个的话，则用两个以上的段表示。

3) 创建文件创建三个文件：S e g m e n t L e n g t h, BitsPerPixel 和P i x e l s。第一个文件包含在2 )中所建的段的长度(减1 )，文件中各项均为8位长。文件BitsPerPixel 给出了各段中每个像素的存储位数（减1），文件中各项均为3位。文件Pixels 则是以变长格式存储的像素的二进制串。

4) 压缩文件压缩在3) 中所建立的文件，以减少空间需求。

上述压缩方法的效率（用所得压缩率表示）很大程度上取决于长段的出现频率。

例3-8 考察图15-3b 的4×4图像。按照蛇形的行主次序，灰度值依次为1 0，9，1 2，4 0，5 0，3 5，1 5，1 2，8，1 0，9，1 5，11，1 3 0，1 6 0和2 4 0。各像素所需的位数分别为4，4，4，6，6，6，4，4，4，4，4，4，4，8，8和8，按等长的条件将像素分段，可以得到4个段[ 1 0，9，1 2 ]、[ 4 0，5 0，3 5 ]、[15, 12, 8, 10, 9, 15, 11] 和［130, 160, 240］。因此，文件SegmentLength 为2，2，6，2；文件BitsPerSegment 的内容为3，5，3，7；文件P i x e l s包含了按蛇形行主次序排列的1 6个灰度值，其中头三个各用4位存储，接下来三个各用6位，再接下来的七个各用4位，最后三个各用8位存储。因此存储单元中前3 0位存储了前六个像素：

1010 1001 1100 111000 110010 100011

这三个文件需要的存储空间分别为：文件SegmentLength 需3 2位；BitsPerSegment 需1 2位；Pixels 需8 2位，共需1 2 6位。而如果每个像素都用8位存储，则存储空间需8×1 6 = 1 2 8位，因而在本例图像中，节省了2位的空间。

假设在2) 之后，产生了n 个段。段标题（segment header）用于存储段的长度以及该段中每个像素所占用的位数。每个段标题需11位。现假设li 和bi 分别表示第i 段的段长和该段每个像素的长度，则存储第i 段像素所需要的空间为li *bi 。在2) 中所得的三个文件的总存储空间为11 n+n ?i = 1li bi。可通过将某些相邻段合并的方式来减少空间消耗。如当段i 和i+ 1被合并时，合并后的段长应为li +li + 1。此时每个像素的存储位数为m a x {bi，bi +1 } 位。尽管这种技术增加了文件P i x e l s的空间消耗，但同时也减少了一个段标题的空间。

例3-9 如果将例1 5 - 8中的第1段和第2段合并，合并后，文件S e g m e n t L e n g t h变为5，6，2，BitsPerSegment 变为5，3，7。而文件Pixels 的前3 6位存储的是合并后的第一段：001010 001001 001100 111000 110010 100011其余的像素（例1 5 - 8第3段）没有改变。因为减少了1个段标题，文件S e g m e n t L e n g t h和BitsPerPixel 的空间消耗共减少了11位，而文件Pixels 的空间增加6位，因此总共节约的空间为5位，空间总消耗为1 2 1位。

我们希望能设计一种算法，使得在产生n 个段之后，能对相邻段进行合并，以便产生一个具有最小空间需求的新的段集合。在合并相邻段之后，可利用诸如L Z W法（见7 . 5节）和霍夫曼编码（见9 . 5 . 3节）等其他技术来进一步压缩这三个文件。

令sq 为前q 个段的最优合并所需要的空间。定义s0 = 0。考虑第i 段(i＞0 )，假如在最优合并C中，第i 段与第i- 1，i- 2，.，i-r+1 段相合并，而不包括第i-r 段。合并C所需要的空间消耗等于：第1段到第i-r 段所需空间+ l s u m (i-r+ 1 ,i) * b m a x (i-r+ 1 ,i) + 11

其中l s u m(a, b)=b ?j =a

lj，bmax (a, b)= m a x {ba , ..., bb }。假如在C中第1段到第i-r 段的合并不是最优合并，那么需要对合并进行修改，以使其具有更小的空间需求。因此还必须对段1到段i-r 进行最优合并，也即保证最优原则得以维持。故C的空间消耗为：

si = si-r +l s u m（i-r+1, i）*b m a x（i-r+1, i）+ 11

r 的值介于1到i 之间，其中要求l s u m不超过2 5 6 (因为段长限制在2 5 6之内)。尽管我们不知道如何选择r，但我们知道，由于C具有最小的空间需求，因此在所有选择中， r 必须产生最小的空间需求。

假定k a yi 表示取得最小值时k 的值，sn 为n 段的最优合并所需要的空间，因而一个最优合并可用kay 的值构造出来。

例3-10 假定在2) 中得到五个段，它们的长度为[ 6，3，1 0，2，3 ]，像素位数为[ 1，2，3，2，1 ]，要用公式（1 5 - 3）计算sn，必须先求出sn-1，.，s0 的值。s0 为0，现计算s1：s1 =s0 +l1 *b1+ 11 = 1 7k a y1 = 1s2 由下式得出：

s2 = m i n {s1 +l2 b2 , s0 + (l1 +l2 ) * m a x {b1 , b2} } + 11 = m i n { 1 7 + 6 , 0 + 9 * 2 } + 11 = 2 9

k a y2 = 2

以此类推，可得s1.s5 = [ 1 7，2 9，6 7，7 3，82] ，k a y1.k a y5 = [ 1，2，2，3，4 ]。因为s5 = 8 2，所以最优空间合并需8 2位的空间。可由k a y5 导出本合并的方式，过程如下：因为k a y5 = 4，所以s5 是由公式（1 5 - 3）在k=4 时取得的，因而最优合并包括：段1到段( 5 - 4 ) = 1的最优合并以及段2，3，4和5的合并。最后仅剩下两个段：段1以及段2到段5的合并段。

1. 递归方法

用递归式（1 5 - 3）可以递归地算出si 和k a yi。程序1 5 - 3为递归式的计算代码。l，b，和k a y是一维的全局整型数组，L是段长限制（ 2 5 6），h e a d e r为段标题所需的空间( 11 )。调用S ( n )返回sn 的值且同时得出k a y值。调用Tr a c e b a c k ( k a y, n )可得到最优合并。

现讨论程序1 5 - 3的复杂性。t( 0 ) =c（c 为一个常数）： （n＞0），因此利用递归的方法可得t (n) = O ( 2n )。Tr a c e b a c k的复杂性为(n)。

程序15-3 递归计算s , k a y及最优合并

int S(int i)

{ / /返回S ( i )并计算k a y [ i ]

if (i == 0 ) return 0;

//k = 1时, 根据公式（ 1 5 - 3）计算最小值

int lsum = l[i],bmax = b[i];

int s = S(i-1) + lsum * bmax;

kay[i] = 1;

/ /对其余的k计算最小值并求取最小值

for (int k = 2; k <= i && lsum+l[i-k+1] <= L; k++) {

lsum += l[i-k+1];

if (bmax < b[i-k+1]) bmax = b[i-k+1];

int t = S(i-k);

if (s > t + lsum * bmax) {

s = t + lsum * bmax;

kay[i] = k;}

}

return s + header;

}

void Traceback(int kay[], int n)

{// 合并段

if (n == 0) return;

Tr a c e b a c k ( k a y, n-kay[n]);

cout << "New segment begins at " << (n - kay[n] + 1) << endl;

}

2. 无重复计算的递归方法

通过避免重复计算si，可将函数S的复杂性减少到(n)。注意这里只有n个不同的si。

例3 - 11 再考察例1 5 - 1 0中五个段的例子。当计算s5 时，先通过递归调用来计算s4，.，s0。计算s4 时，通过递归调用计算s3，.，s0，因此s4 只计算了一次，而s3 计算了两次，每一次计算s3要计算一次s2，因此s2 共计算了四次，而s1 重复计算了1 6次！可利用一个数组s 来保存先前计算过的si 以避免重复计算。改进后的代码见程序1 5 - 4，其中s为初值为0的全局整型数组。

程序15-4 避免重复计算的递归算法

int S(int i)

{ / /计算S ( i )和k a y [ i ]

/ /避免重复计算

if (i == 0) return 0;

if (s[i] > 0) return s[i]; //已计算完

/ /计算s [ i ]

/ /首先根据公式（1 5 - 3）计算k = 1时最小值

int lsum = l[i], bmax = b[i];

s[i] =S(i-1) + lsum * bmax;

kay[i] = 1;

/ /对其余的k计算最小值并更新

for (int k = 2; k <= i && lsum+l[i-k+1] <= L; k++) {

lsum += l[i-k+1];

if (bmax < b[i-k+1]) bmax = b[i-k+1];

int t = S(i-k);

if (s[i] > t + lsum * bmax) {

s[i] = t + lsum * bmax;

kay[i] = k;}

}

s[i] += header;

return s[i];

}

为了确定程序1 5 - 4的时间复杂性，我们将使用分期计算模式（ amortization scheme）。在该模式中，总时间被分解为若干个不同项，通过计算各项的时间然后求和来获得总时间。当计算si 时，若sj 还未算出，则把调用S(j) 的消耗计入sj ；若sj 已算出，则把S(j) 的消耗计入si (这里sj依次把计算新sq 的消耗转移至每个sq )。程序1 5 - 4的其他消耗也被计入si。因为L是2 5 6之内的常数且每个li 至少为1，所以程序1 5 - 4的其他消耗为( 1 )，即计入每个si 的量是一个常数，且si 数目为n，因而总工作量为(n)。

3. 迭代方法

倘若用式（1 5 - 3）依序计算s1 , ., sn，便可得到一个复杂性为(n)的迭代方法。在该方法中，在si 计算之前， sj 必须已计算好。该方法的代码见程序1 5 - 5，其中仍利用函数Tr a c e b a c k（见程序1 5 - 3）来获得最优合并。

程序15-5 迭代计算s和k a y

void Vbits (int l[], int b[], int n, int s[], int kay[])

{ / /计算s [ i ]和k a y [ i ]

int L = 256, header = 11 ;

s[0] = 0;

/ /根据式（1 5 - 3）计算s [ i ]

for (int i = 1; i <= n; i++) {

// k = 1时,计算最小值

int lsum = l,

bmax = b[i];

s[i] = s[i-1] + lsum * bmax;

kay[i] = 1;

/ /对其余的k计算最小值并更新

for (int k=2; k<= i && lsum+l[i-k+1]<= L; k++) {

lsum += l[i-k+1];

if (bmax < b[i-k+1]) bmax = b[i-k+1];

if (s[i] > s[i-k] + lsum * bmax){

s[i] = s[i-k] + lsum * bmax;

kay[i] = k; }

}

s[i] += header;

}

}

3.2.3 矩阵乘法链

m×n矩阵A与n×p矩阵B相乘需耗费(m n p)的时间（见第2章练习1 6）。我们把m n p作为两个矩阵相乘所需时间的测量值。现假定要计算三个矩阵A、B和C的乘积，有两种方式计算此乘积。在第一种方式中，先用A乘以B得到矩阵D，然后D乘以C得到最终结果，这种乘法的顺序可写为(A*B) *C。第二种方式写为A* (B*C) ,道理同上。尽管这两种不同的计算顺序所得的结果相同，但时间消耗会有很大的差距。

例3-12 假定A为1 0 0×1矩阵，B为1×1 0 0矩阵，C为1 0 0×1矩阵，则A*B的时间耗费为10 0 0 0，得到的结果D为1 0 0×1 0 0矩阵，再与C相乘所需的时间耗费为1 000 000，因此计算(A*B) *C的总时间为1 010 000。B*C的时间耗费为10 000，得到的中间矩阵为1×1矩阵，再与A相乘的时间消耗为1 0 0，因而计算A*（B*C）的时间耗费竟只有10 100！而且，计算（ A*B）*C时，还需10 000个单元来存储A*B，而A*（B*C）计算过程中，只需用1个单元来存储B*C。

下面举一个得益于选择合适秩序计算A*B*C矩阵的实例：考虑两个3维图像的匹配。图像匹配问题的要求是，确定一个图像需旋转、平移和缩放多少次才能逼近另一个图像。实现匹配的方法之一便是执行约1 0 0次迭代计算，每次迭代需计算1 2×1个向量T：

T=?A(x, y, z) *B(x, y, z)*C(x, y, z )

其中A，B和C分别为1 2×3，3×3和3×1矩阵。(x , y, z) 为矩阵中向量的坐标。设t 表示计算A(x , y, z) *B(x , y, z) *C(x , y, z)的计算量。假定此图像含2 5 6×2 5 6×2 5 6个向量，在此条件中，这1 0 0个迭代所需的总计算量近似为1 0 0 * 2 5 63 * t≈1 . 7 * 1 09 t。若三个矩阵是按由左向右的顺序相乘的，则t = 1 2 * 3 * 3 + 1 2 * 3 *1= 1 4 4；但如果从右向左相乘， t = 3 * 3 * 1 + 1 2 * 3 * 1 = 4 5。由左至右计算约需2 . 4 * 1 011个操作，而由右至左计算大概只需7 . 5 * 1 01 0个操作。假如使用一个每秒可执行1亿次操作的计算机，由左至右需4 0分钟，而由右至左只需1 2 . 5分钟。

在计算矩阵运算A*B*C时，仅有两种乘法顺序（由左至右或由右至左），所以可以很容易算出每种顺序所需要的操作数，并选择操作数比较少的那种乘法顺序。但对于更多矩阵相乘来说，情况要复杂得多。如计算矩阵乘积M1×M2×.×Mq，其中Mi 是一个ri×ri + 1 矩阵( 1≤i≤q)。不妨考虑q=4 的情况，此时矩阵运算A*B*C*D可按以下方式（顺序）计算：

A* ( (B*C) *D) A* (B* (C*D)) (A*B) * (C*D) (A* (B*C) ) *D

不难看出计算的方法数会随q 以指数级增加。因此，对于很大的q 来说，考虑每一种计算顺序并选择最优者已是不切实际的。

现在要介绍一种采用动态规划方法获得矩阵乘法次序的最优策略。这种方法可将算法的时间消耗降为(q3 )。用Mi j 表示链Mi×.×Mj （i≤j）的乘积。设c(i,j) 为用最优法计算Mi j 的消耗，k a y(i, j) 为用最优法计算Mi j 的最后一步Mi k×Mk+1, j 的消耗。因此Mij 的最优算法包括如何用最优算法计算Mik 和Mkj 以及计算Mik×Mkj 。根据最优原理，可得到如下的动态规划递归式：k a y(i,i+s)= 获得上述最小值的k. 以上求c 的递归式可用递归或迭代的方法来求解。c( 1，q) 为用最优法计算矩阵链的消耗，k a y( 1 ,q) 为最后一步的消耗。其余的乘积可由k a y值来确定。

1. 递归方法

与求解0 / 1背包及图像压缩问题一样，本递归方法也须避免重复计算c (i, j) 和k a y(i, j)，否则算法的复杂性将会非常高。

例3-13 设q= 5和r =（1 0 , 5 , 1 , 1 0 , 2 , 1 0），式中待求的c 中有四个c的s= 0或1，因此用动态规划方法可立即求得它们的值： c( 1 , 1 ) =c( 5 , 5 ) = 0 ;c(1,2)=50; c( 4 , 5 ) = 2 0 0。现计算C( 2，5 )：c( 2 , 5 ) = m i n {c( 2 , 2 ) +c(3,5)+50, c( 2 , 3 ) +c(4,5)+500, c( 2 , 4 ) +c( 5 , 5 ) + 1 0 0 } （1 5 - 5）其中c( 2 , 2 ) =c( 5 , 5 ) = 0；c( 2 , 3 ) = 5 0；c(4,5)=200 。再用递归式计算c( 3 , 5 )及c( 2 , 4 ) :c( 3 , 5 ) = m i n {c( 3 , 3 ) +c(4,5)+100, c( 3 , 4 ) +c( 5 , 5 ) + 2 0 } = m i n { 0 + 2 0 0 + 1 0 0 , 2 0 + 0 + 2 0 } = 4 0c( 2 , 4 ) = m i n {c( 2 , 2 ) +c( 3 , 4 ) + 1 0 ,c( 2 , 3 ) +c( 4 , 4 ) + 1 0 0 } = m i n { 0 + 2 0 + 1 0 , 5 0 + 1 0 + 2 0 } = 3 0由以上计算还可得k a y( 3 , 5 ) = 4，k ay( 2 , 4 ) = 2。现在,计算c(2,5) 所需的所有中间值都已求得，将它们代入式（1 5 - 5）得：

c(2,5)=min{0+40+50, 50+200+500, 30+0+100}=90且k a y( 2 , 5 ) = 2

再用式（1 5 - 4）计算c( 1 , 5 )，在此之前必须算出c( 3 , 5 )、c(1,3) 和c( 1 , 4 )。同上述过程，亦可计算出它们的值分别为4 0、1 5 0和9 0，相应的k a y 值分别为4、2和2。代入式（1 5 - 4）得：

c(1,5)=min{0+90+500, 50+40+100, 150+200+1000, 90+0+200}=190且k a y( 1 , 5 ) = 2

此最优乘法算法的消耗为1 9 0，由k a y(1,5) 值可推出该算法的最后一步， k a y(1,5) 等于2，因此最后一步为M1 2×M3 5，而M12 和M35 都是用最优法计算而来。由k a y( 1 , 2 ) = 1知M12 等于M11×M2 2，同理由k a y( 3 , 5) = 4得知M35 由M3 4×M55 算出。依此类推，M34 由M3 3×M44 得出。因而此最优乘法算法的步骤为：

M11×M2 2 = M1 2

M3 3×M4 4 = M3 4

M3 4×M5 5 = M3 5

M1 2×M3 5 = M1 5

计算c(i, j) 和k a y (i, j) 的递归代码见程序1 5 - 6。在函数C中，r 为全局一维数组变量， k a y是全局二维数组变量，函数C返回c(i j) 之值且置k a y [a] [b] =k ay (a , b) (对于任何a , b)，其中c(a , b)在计算c(i,j) 时皆已算出。函数Traceback 利用函数C中已算出的k a y值来推导出最优乘法算法的步骤。

设t(q)为函数C的复杂性，其中q=j-i+ 1（即Mij 是q个矩阵运算的结果）。当q为1或2时，t(q) =d，其中d 为一常数；而q> 2时，t (q)=2q-1?k = 1t (k ) +e q，其中e 是一个常量。因此当q＞2时，t(q)＞2t (q- 1 ) +e，所以t (q)= W ( 2q)。函数Traceback 的复杂性为(q)。

程序15-6 递归计算c (i, j) 和kay (i, j)

int C(int i, int j)

{ / /返回c(i,j) 且计算k(i,j) = kay[i][j]

if (i==j) return 0; //一个矩阵的情形

if (i == j-1) { //两个矩阵的情形

kay[i][i+1] = i;

return r[i]*r[i+1]*r[r+2];}

/ /多于两个矩阵的情形

/ /设u为k = i 时的最小值

int u = C(i,i) + C(i+1,j) + r[i]*r[i+1]*r[j+1];

kay[i][j] = i;

/ /计算其余的最小值并更新u

for (int k = i+1; k < j; k++) {

int t = C(i,k) + C(k+1,j) + r[i]*r[k+1]*r[j+1];

if (r < u) {//小于最小值的情形

u = t;

kay[i][j] = k;

}

return u;

}

void Traceback (int i, int j ,int **kay)

{ / /输出计算Mi j 的最优方法

if ( i == j) return;

Traceback(i, kay[i][j], kay);

Traceback(kay[i][j]+1, j, kay);

cout << "Multiply M" << i << ", "<< kay[i][j];

cout << " and M " << (kay[i][j]+1) << ", " << j << end1;

}

2. 无重复计算的递归方法

若避免再次计算前面已经计算过的c（及相应的k a y），可将复杂性降低到（q3）。而为了避免重复计算，需用一个全局数组c[ ][ ]存储c(i, j) 值，该数组初始值为0。函数C的新代码见程序1 5 - 7：

程序15-7 无重复计算的c (i, j) 计算方法

int C(int i,int j)

{ / /返回c(i,j) 并计算k a y ( i , j ) = k a y [ I ] [ j ]

/ /避免重复计算

/ /检查是否已计算过

if （c[i][j] >） return c[i][j];

/ /若未计算,则进行计算

if(i==j) return 0; //一个矩阵的情形

i f ( i = = j - 1 ) { / /两个矩阵的情形

kay[i][i+1]=i;

c [ i ] [ j ] = r [ i ] * r [ i + 1 ] * r [ i + 2 ] ;

return c[i][j];}

/ /多于两个矩阵的情形

/ /设u为k = i 时的最小值

int u=C(i,i)+C(i+1,j)+r[i]*r[i+1]*r[j+1];

k a y [ i ] [ j ] = i ;

/ /计算其余的最小值并更新u

for (int k==i+1; k<j;k++){

int t=C(i,k)+C(k+1,j)+r[i]*r[k+1]*r[j+1];

if (t<u) {// 比最小值还小

u = t ;

k a y [ i ] [ j ] = k ; }

}

c [ i ] [ j ] = u ;

return u;

}

为分析改进后函数C 的复杂性，再次使用分期计算方法。注意到调用C(1, q) 时每个c (i, j)（1≤i≤j≤q）仅被计算一次。要计算尚未计算过的c(a,b)，需附加的工作量s =j-i＞1。将s 计入第一次计算c (a, b) 时的工作量中。在依次计算c(a, b) 时，这个s 会转计到每个c (a, b) 的第一次计算时间c 中，因此每个c (i, i) 均被计入s。对于每个s，有q-s+ 1个c(i, j) 需要计算，因此总的工作消耗为q-1 ?s=1(q-s+ 1) = (q3 )。

3. 迭代方法

c 的动态规划递归式可用迭代的方法来求解。若按s = 2，3，.，q-1 的顺序计算c (i, i+s)，每个c 和kay 仅需计算一次。

例3-14 考察例3 - 1 3中五个矩阵的情况。先初始化c (i, i) (0≤i≤5) 为0，然后对于i=1, ., 4分别计算c (i, i+ 1 )。c (1, 2)= r1 r2 r3 = 5 0，c (2, 3)= 5 0，c ( 3,4)=20 和c (4, 5) = 2 0 0。相应的k ay 值分别为1，2，3和4。

当s= 2时，可得：

c( 1 , 3 ) = m i n {c( 1 , 1 ) +c(2,3)+ r1 r2 r4 , c( 1 , 2 ) +c( 3 ,3 )+r1r3r4 }=min

=150

且k a y( 1 , 3 ) = 2。用相同方法可求得c( 2 , 4 )和c( 3 , 5 )分别为3 0和4 0，相应k a y值分别为2和3。

当s= 3时，需计算c(1,4) 和c( 2 , 5 )。计算c(2,5) 所需要的所有中间值均已知(见( 1 5 - 5 )式)，代入计算公式后可得c( 2 , 5 ) = 9 0，k a y( 2 , 5 ) = 2。c( 1 , 4 )可用同样的公式计算。最后，当s= 4时，可直接用（1 5 - 4）式来计算c( 1 , 5 )，因为该式右边所有项都已知。

计算c 和kay 的迭代程序见函数M a t r i x C h a i n（见程序1 5 - 8），该函数的复杂性为(q3 )。计算出kay 后同样可用程序1 5 - 6中的Traceback 函数推算出相应的最优乘法计算过程。

程序15-8 c 和kay 的迭代计算

void MatrixChain(int r[], int q, int **c, int **kay)

{// 为所有的Mij 计算耗费和k a y

// 初始化c[i][i], c[i][i+1]和k a y [ i ] [ i + 1 ]

for (int i = 1; i < q; i++) {

c[i][i] = 0;

c[i][i+1] = r[i]*r[i+1]*r[i+2];

kay[i][i+1] = i;

}

c[q][q] = 0;

/ /计算余下的c和k a y

for (int s = 2; s < q; s++)

for (int i = 1; i <= q - s; i++) {

// k = i时的最小项

c[i][i+s] = c[i][i] + c[i+1][i+s] + r[i]*r[i+1]*r[i+s+1];

kay[i][i+s] = i;

// 余下的最小项

for (int k = i+1; k < i + s; k++) {

int t = c[i][k] + c[k+1][i+s] + r[i]*r[k+1]*r[i+s+1];

if (t < c[i][i+s]) {// 更小的最小项

c[i][i+s] = t;

kay[i][i+s] = k;}

}

}

}

3.2.4 最短路径

假设G为有向图，其中每条边都有一个长度（或耗费），图中每条有向路径的长度等于该路径中各边的长度之和。对于每对顶点(i, j)，在顶点i 与j 之间可能有多条路径，各路径的长度可能各不相同。我们定义从i 到j 的所有路径中，具有最小长度的路径为从i 到j 的最短路径。

例3-15 如图1 5 - 4所示。从顶点1到顶点3的路径有

1) 1,2,5,3

2) 1,4,3

3) 1,2,5,8,6,3

4) 1,4,6,3

由该图可知,各路径相应的长度为1 0、2 8、9、2 7，因而路径3) 是该图中顶点1到顶点3的最短路径。

在所有点对最短路径问题（ a l l - p a i r sshorest-paths problem）中，要寻找有向图G中每对顶点之间的最短路径。也就是说，对于每对顶点(i, j)，需要寻找从i到j 的最短路径及从j 到i 的最短路径。因此对于一个n 个顶点的图来说，需寻找p =n(n-1) 条最短路径。假定图G中不含有长度为负数的环路，只有在这种假设下才可保证G中每对顶点(i, j) 之间总有一条不含环路的最短路径。当有向图中存在长度小于0的环路时，可能得到长度为－∞的更短路径，因为包含该环路的最短路径往往可无限多次地加上此负长度的环路。

设图G中n 个顶点的编号为1到n。令c (i, j, k)表示从i 到j 的最短路径的长度，其中k 表示该路径中的最大顶点。因此，如果G中包含边<i, j>，则c(i, j, 0) =边<i, j> 的长度；若i= j ，则c(i,j, 0)=0；如果G中不包含边<i, j>，则c (i, j, 0)= +∞。c(i, j, n) 则是从i 到j 的最短路径的长度。

例3-16 考察图1 5 - 4。若k=0, 1, 2, 3，则c (1, 3, k)= ∞；c (1, 3, 4)= 2 8；若k = 5, 6, 7，则c (1, 3,k) = 1 0；若k=8, 9, 10，则c (1, 3, k) = 9。因此1到3的最短路径长度为9。对于任意k＞0，如何确定c (i, j, k) 呢？中间顶点不超过k 的i 到j 的最短路径有两种可能：该路径含或不含中间顶点k。若不含，则该路径长度应为c(i, j, k- 1 )，否则长度为c(i, k, k- 1) +c (k, j, k- 1 )。c(i, j, k) 可取两者中的最小值。因此可得到如下递归式：

c( i, j, k)= m i n {c(i, j, k-1), c (i, k, k- 1) +c (k, j, k- 1 ) }，k＞0

以上的递归公式将一个k 级运算转化为多个k-1 级运算，而多个k-1 级运算应比一个k 级运算简单。如果用递归方法求解上式，则计算最终结果的复杂性将无法估量。令t (k) 为递归求解c (i, j, k) 的时间。根据递归式可以看出t(k) = 2t(k- 1 ) +c。利用替代方法可得t(n) = ( 2n )。因此得到所有c (i, j, n) 的时间为(n2 2n )。

当注意到某些c (i, j, k-1) 值可能被使用多次时，可以更高效地求解c (i, j, n)。利用避免重复计算c(i, j, k) 的方法，可将计算c 值的时间减少到(n3 )。这可通过递归方式（见程序1 5 - 7矩阵链问题）或迭代方式来实现。出迭代算法的伪代码如图1 5 - 5所示。

 

/ /寻找最短路径的长度

/ /初始化c（i，j，1）

for （int i=1； i < = n ; i + +）

for (int j=1; j<=n; j+ + )

c ( i ,j, 0 ) = a ( i ,j); // a 是长度邻接矩阵

/ /计算c ( i ,j, k ) ( 0 < k < = n )

for(int k=1;k<=n;k++)

for (int i=1;i<=n;i++)

for (int j= 1 ;j< = n ;j+ + )

if (c(i,k,k-1)+c(k,j, k - 1 ) < c ( i ,j, k - 1 ) )

c ( i ,j, k ) = c ( i , k , k - 1 ) + c ( k ,j, k - 1 ) ;

else c(i,j, k ) = c ( i ,j, k - 1 ) ;

图15-5 最短路径算法的伪代码

 

注意到对于任意i，c(i,k,k) =c(i,k,k- 1 )且c(k,i,k) =c(k,i,k- 1 )，因而，若用c(i,j)代替图1 5 - 5的c(i,j,k)，最后所得的c(i,j) 之值将等于c(i,j,n) 值。此时图1 5 - 5可改写成程序1 5 - 9的C + +代码。程序1 5 - 9中还利用了程序1 2 - 1中定义的AdjacencyWDigraph 类。函数AllPairs 在c 中返回最短路径的长度。若i 到j 无通路，则c [i] [j]被赋值为N o E d g e。函数AllPairs 同时计算了k a y [ i ] [ j ]，其中kay[i][j] 表示从i 到j 的最短路径中最大的k 值。在后面将看到如何根据kay 值来推断出从一个顶点到另一顶点的最短路径（见程序1 5 - 1 0中的函数O u t p u t P a t h）。

程序1 5 - 9的时间复杂性为(n3 )，其中输出一条最短路径的实际时间为O (n)。

程序15-9 c 和kay 的计算

template<class T>

void AdjacencyWDigraph<T>::Allpairs(T **c, int **kay)

{ / /所有点对的最短路径

/ /对于所有i和j，计算c [ i ] [ j ]和k a y [ i ] [ j ]

/ /初始化c [ i ] [ j ] = c（i，j，0）

for (int i = 1; i <= n; i++)

for (int j = 1; j <= n; j++) {

c[i][j] = a[i][j];

kay[i][j] = 0;

}

for (i = 1; i <= n; i++)

c[i][i] = 0;

// 计算c[i][j] = c(i,j,k)

for (int k = 1; k <= n; k++)

for (int i = 1; i <= n; i++)

for (int j = 1; j <= n; j++) {

T t1 = c[i][k];

T t2 = c[k][j];

T t3 = c[i][j];

if (t1 != NoEdge && t2 != NoEdge && (t3 == NoEdge || t1 + t2 < t3)) {

c[i][j] = t1 + t2;

kay[i][j] = k;}

}

}

程序15-10 输出最短路径

void outputPath(int **kay, int i, int j)

{// 输出i 到j 的路径的实际代码

if (i == j) return;

if (kay[i][j] == 0) cout << j << ' ';

else {outputPath(kay, i, kay[i][j]);

o u t p u t P a t h ( k a y, kay[i][j], j);}

}

template<class T>

void OutputPath(T **c, int **kay, T NoEdge, int i, int j)

{// 输出从i 到j的最短路径

if (c[i][j] == NoEdge) {

cout << "There is no path from " << i << " to " << j << endl;

r e t u r n ; }

cout << "The path is" << endl;

cout << i << ' ';

o u t p u t P a t h ( k a y, i , j ) ;

cout << endl;

}

例3-17 图15-6a 给出某图的长度矩阵a，15-6b 给出由程序1 5 - 9所计算出的c 矩阵，15-6c 为对应的k a y值。根据15-6c 中的kay 值，可知从1到5的最短路径是从1到k a y [ 1 ] [ 5 ] = 4的最短路径再加上从4到5的最短路径，因为k a y [ 4 ] [ 5 ] = 0，所以从4到5的最短路径无中间顶点。从1到4的最短路径经过k a y [ 1 ] [ 4 ] = 3。重复以上过程，最后可得1到5的最短路径为：1，2，3，4，5。

3.2.5 网络的无交叉子集

在11 . 5 . 3节的交叉分布问题中，给定一个每边带n 个针脚的布线通道和一个排列C。顶部的针脚i 与底部的针脚Ci 相连，其中1≤i≤n，数对(i, Ci ) 称为网组。总共有n 个网组需连接或连通。假设有两个或更多的布线层，其中有一个为优先层，在优先层中可以使用更细的连线，其电阻也可能比其他层要小得多。布线时应尽可能在优先层中布设更多的网组。而剩下的其他网组将布设在其他层。当且仅当两个网组之间不交叉时，它们可布设在同一层。我们的任务是寻找一个最大无交叉子集（Maximum Noncrossing Su b s e t，M N S )。在该集中，任意两个网组都不交叉。因(i, Ci ) 完全由i 决定，因此可用i 来指定(i, Ci )。

例3-18 考察图1 5 - 7（对应于图1 0 - 1 7）。( 1 , 8 )和( 2 , 7 )（也即1号网组和2号网组）交叉，因而不能布设在同一层中。而( 1 , 8 )，(7,9) 和(9,10) 未交叉，因此可布设在同一层。但这3个网组并不能构成一个M N S，因为还有更大的不交叉子集。图1 0 - 1 7中给出的例子中，集合｛ ( 4 , 2 ) ,( 5 , 5 ) , ( 7 , 9 ) , ( 9 , 1 0 )｝是一个含4个网组的M N S。

设M N S(i, j) 代表一个M N S，其中所有的(u, Cu ) 满足u≤i，Cu≤j。令s i z e(i,j) 表示M N S(i,j)的大小(即网组的数目)。显然M N S(n,n)是对应于给定输入的M N S，而s i z e(n,n)是它的大小。

例3-19 对于图1 0 - 1 7中的例子，M N S( 1 0 , 1 0 )是我们要找的最终结果。如例3 - 1 8中所指出的，s i z e( 1 0 , 1 0 ) = 4，因为( 1 , 8 )，( 2 , 7 )，( 7 , 9 )，( 8 , 3 )，( 9 , 1 0 )和( 1 0 , 6 )中要么顶部针脚编号比7大，要么底部针脚编号比6大，因此它们都不属于M N S( 7 , 6 )。因此只需考察剩下的4个网组是否属于M N S( 7 , 6 )，如图1 5 - 8所示。子集｛( 3 , 4 ) , ( 5 , 5 )｝是大小为2的无交叉子集。没有大小为3的无交叉子集，因此s i z e( 7 , 6) = 2。

当i= 1时，( 1 ,C1) 是M N S( 1 ,j) 的唯一候选。仅当j≥C1 时，这个网组才会是M N S( 1 ,j) 的一个成员.

下一步，考虑i＞1时的情况。若j＜Ci，则(i,Ci ) 不可能是M N S( i,j) 的成员，所有属于M N S(i,j) 的(u, Cu ) 都需满足u＜i且Cu＜j，因此：s i z e(i,j) =s i z e(i- 1 ,j), j<Ci （1 5 - 7）

若j≥Ci，则(i,Ci ) 可能在也可能不在M N S(i,j) 内。若(i,Ci ) 在M N S(i,j) 内，则在M N S(i,j)中不会有这样的(u,Cu )：u＜i且Cu＞Ci，因为这个网组必与(i, Ci ) 相交。因此M N S(i,j) 中的其他所有成员都必须满足条件u＜i且Cu＜Ci。在M N S(i,j) 中这样的网组共有Mi- 1 , Ci- 1 个。若(i,Ci ) 不在M N S(i,j)中，则M N S(i,j) 中的所有(u, Cu ) 必须满足u＜i；因此s i z e(i,j)=s i z e(i- 1 ,j)。虽然不能确定(i, Ci )是否在M N S(i,j) 中，但我们可以根据获取更大M N S的原则来作出选择。因此：s i z e(i,j) = m a x {s i z e(i-1 ,j), s i z e(i- 1 ,Ci-1)+1}, j≥Ci （1 5 - 8）

虽然从（1 5 - 6）式到（ 1 5 - 8）式可用递归法求解，但从前面的例子可以看出，即使避免了重复计算，动态规划递归算法的效率也不够高，因此只考虑迭代方法。在迭代过程中先用式（1 5 - 6）计算出s i ze ( 1 ,j)，然后再用式（1 5 - 7）和（1 5 - 8）按i=2, 3, ., n 的顺序计算s i ze (i,j)，最后再用Traceback 来得到M N S(n, n) 中的所有网组。

例3-20 图1 5 - 9给出了图1 5 - 7对应的s i z e(i,j) 值。因s i z e( 1 0 , 1 0) = 4，可知M N S含4个网组。为求得这4个网组，先从s i ze ( 1 0 , 1 0 )入手。可用（1 5 - 8）式算出s i z e( 1 0 , 1 0 )。根据式（1 5 - 8）时的产生原因可知s i ze ( 1 0 , 1 0)=s i z e( 9 , 1 0 )，因此现在要求M NS ( 9 , 1 0 )。由于M NS ( 1 0 , 1 0 )≠s i z e( 8 , 1 0 )，因此M NS (9,10) 中必包含9号网组。M N S(9,10) 中剩下的网组组成M NS ( 8 , C9- 1)=M N S( 8 , 9 )。由M N S( 8 , 9 ) =M NS (7,9) 知，8号网组可以被排除。接下来要求M N S( 7 , 9 )，因为s i z e( 7 , 9 )≠s i z e( 6 , 9 )，所以M N S中必含7号网组。M NS (7,9) 中余下的网组组成M NS ( 6 , C7- 1 ) =M N S( 6 , 8 )。根据s i z e( 6 , 8 ) =s i z e( 5 , 8 )可排除6号网组。按同样的方法， 5号网组，3号网组加入M N S中，而4号网组等其他网组被排除。因此回溯过程所得到的大小为4的M N S为{ 3 , 5 , 7 , 9 }。

注意到在回溯过程中未用到s i z e( 1 0 ,j) (j≠1 0 )，因此不必计算这些值。

程序1 5 - 11给出了计算s i z e ( i , j ) 的迭代代码和输出M N S的代码。函数M N S用来计算s i ze (i,j) 的值，计算结果用一个二维数组M N来存储。size[i][j] 表示s i z e(i,j)，其中i=j= n 或1≤i＜n，0≤j≤n，计算过程的时间复杂性为(n2 )。函数Traceback 在N et［0 : m - 1］中输出所得到的M N S，其时间复杂性为(n)。因此求解M M S问题的动态规划算法的总的时间复杂性

为(n2 )。

程序1 5 - 11 寻找最大无交叉子集

void MNS(int C[], int n, int **size)

{ / /对于所有的i 和j，计算s i z e [ i ] [ j ]

/ /初始化s i z e [ 1 ] [ * ]

for (int j = 0; j < C[1]; j++)

size[1][j] = 0;

for (j = C[1]; j <= n; j++)

size[1][j] = 1;

// 计算size[i][*], 1 < i < n

for (int i = 2; i < n; i++) {

for (int j = 0; j < C[i]; j++)

size[i][j] = size[i-1][j];

for (j = C[i]; j <= n; j++)

size[i][j] = max(size[i-1][j], size[i-1][C[i]-1]+1);

}

size[n][n] = max(size[n-1][n], size[n-1][C[n]-1]+1);

}

void Traceback(int C[], int **size, int n, int Net[], int& m)

{// 在N e t [ 0 : m - 1 ]中返回M M S

int j = n; // 所允许的底部最大针脚编号

m = 0; // 网组的游标

for (int i = n; i > 1; i--)

// i 号n e t在M N S中?

if (size[i][j] != size[i-1][j]){// 在M N S中

Net[m++] = i;

j = C[i] - 1;}

// 1号网组在M N S中?

if (j >= C[1])

Net[m++] = 1; // 在M N S中

}

3.2.6 元件折叠

在设计电路的过程中，工程师们会采取多种不同的设计风格。其中的两种为位－片设计（bit-slice design）和标准单元设计（standard-cell design）。在前一种方法中，电路首先被设计为一个元件栈（如图15-10a 所示）。每个元件Ci 宽为wi ，高为hi ，而元件宽度用片数来表示。图15-10a 给出了一个四片的设计。线路是按片来连接各元件的，即连线可能连接元件Ci 的第j片到元件Ci+1 的第j 片。如果某些元件的宽度不足j 片，则这些元件之间不存在片j 的连线。当图1 5 -10a 的位－片设计作为某一大系统的一部分时，则在V L SI ( Very Large Scale Integrated) 芯片上为它分配一定数量的空间单元。分配是按空间宽度或高度的限制来完成的。现在的问题便是如何将元件栈折叠到分配空间中去，以便尽量减小未受限制的尺度（如，若高度限制为H时，必须折叠栈以尽量减小宽度W）。由于其他尺度不变，因此缩小一个尺度（如W）等价于缩小面积。可用折线方式来折叠元件栈，在每一折叠点，元件旋转1 8 0°。在图15-10b 的例子中，一个1 2元件的栈折叠成四个垂直栈，折叠点为C6 , C9 和C1 0。折叠栈的宽度是宽度最大的元件所需的片数。在图15-10b 中，栈宽各为4，3，2和4。折叠栈的高度等于各栈所有元件高度之和的最大值。在图15-10b 中栈1的元件高度之和最大，该栈的高度决定了包围所有栈的矩形高度。

实际上，在元件折叠问题中，还需考虑连接两个栈的线路所需的附加空间。如，在图1 5 -10b 中C5 和C6 间的线路因C6 为折叠点而弯曲。这些线路要求在C5 和C6 之下留有垂直空间，以便能从栈1连到栈2。令ri 为Ci 是折叠点时所需的高度。栈1所需的高度为5 ?i =1hi +r6，栈2所需高度为8 ?i=6hi +r6+r9。

在标准单元设计中，电路首先被设计成为具有相同高度的符合线性顺序的元件排列。假设此线性顺序中的元件为C1，.，Cn，下一步元件被折叠成如图1 5 - 11所示的相同宽度的行。在此图中， 1 2个标准单元折叠成四个等宽行。折叠点是C4，C6 和C11。在相邻标准单元行之间，使用布线通道来连接不同的行。折叠点决定了所需布线通道的高度。设li 表示当Ci 为折叠点时所需的通道高度。在图1 5 - 11的例子中，布线通道1的高度为l4，通道2的高度为l6，通道3的高度为l11。位－片栈折叠和标准单元折叠都会引出一系列的问题，这些问题可用动态规划方法来解决。

1. 等宽位－片元件折叠

定义r1 = rn+1 =0。由元件Ci 至Cj 构成的栈的高度要求为j ?k= ilk+ ri+ rj + 1。设一个位－片设计中所有元件有相同宽度W。首先考察在折叠矩形的高度H给定的情况下，如何缩小其宽度。设Wi

为将元件Ci 到Cn 折叠到高为H的矩形时的最小宽度。若折叠不能实现（如当ri +hi＞H时），取Wi =∞。注意到W1 可能是所有n 个元件的最佳折叠宽度。

当折叠Ci 到Cn 时，需要确定折叠点。现假定折叠点是按栈左到栈右的顺序来取定的。若第一点定为Ck+ 1，则Ci 到Ck 在第一个栈中。为了得到最小宽度，从Ck+1 到Cn 的折叠必须用最优化方法，因此又将用到最优原理，可用动态规划方法来解决此问题。当第一个折叠点k+ 1已知时，可得到以下公式：

Wi =w+ Wk + 1 （1 5 - 9）

由于不知道第一个折叠点，因此需要尝试所有可行的折叠点，并选择满足（ 1 5 - 9）式的折叠点。令h s u m(i,k)=k ?j = ihj。因k+ 1是一个可行的折叠点，因此h s u m(i, k) +ri +rk+1 一定不会超过H。

根据上述分析，可得到以下动态规划递归式：

这里Wn+1 =0，且在无最优折叠点k+ 1时Wi 为∞。利用递归式（1 5 - 1 0），可通过递归计算Wn , Wn- 1., W2 , W1 来计算Wi。Wi 的计算需要至多检查n-i+ 1个Wk+ 1，耗时为O (n-k)。因此计算所有Wi 的时间为O (n2 )。通过保留式（1 5 - 1 0）每次所得的k 值，可回溯地计算出各个最优的折叠点，其时间耗费为O (n)。

现在来考察另外一个有关等宽元件的折叠问题：折叠后矩形的宽度W已知，需要尽量减小其高度。因每个折叠矩形宽为w，因此折叠后栈的最大数量为s=W / w。令Hi, j 为Ci , ., Cn 折叠成一宽度为jw 的矩形后的最小高度， H1, s 则是所有元件折叠后的最小高度。当j= 1时，不允许任何折叠，因此：Hi,1 =h s u m(i,n) +ri , 1≤i≤n

另外，当i=n 时，仅有一个元件，也不可能折叠，因此：Hn ,j=hn+rn , 1≤j≤s

在其他情况下，都可以进行元件折叠。如果第一个折叠点为k+ 1，则第一个栈的高度为

h s u m(i,k) +ri +rk+ 1。其他元件必须以至多(j- 1 ) *w 的宽度折叠。为保证该折叠的最优性，其他元件也需以最小高度进行折叠.

因为第一个折叠点未知，因此必须尝试所有可能的折叠点，然后从中找出一个使式（1 5 - 11）的右侧取最小值的点，该点成为第一个折叠点。

可用迭代法来求解Hi, j ( 1≤i≤n, 1≤j≤s)，求解的顺序为：先计算j=2 时的H i, j，再算j= 3，.，以此类推。对应每个j 的Hi, j 的计算时间为O (n2 )，所以计算所有H i, j 的时间为O(s n2 )。通过保存由（ 1 5 - 1 2）式计算出的每个k 值，可以采用复杂性为O (n) 的回溯过程来确定各个最优的折叠点。

2. 变宽位－片元件的折叠

首先考察折叠矩形的高度H已定，欲求最小的折叠宽度的情况。令Wi 如式（1 5 - 1 0）所示，按照与（1 5 - 1 0）式相同的推导过程，可得：

Wi = m i n {w m i n(i, k) +Wk+1 | h s u m(i,k)+ ri +rk+ 1≤H, i≤k≤n} （1 5 - 1 3）

其中Wn+1=0且w m i n(i,k)= m ini≤j≤k{wj }。可用与（1 5 - 1 0）式一样的方法求解（1 5 - 1 3）式，所需时间为O(n2 )。

当折叠宽度W给定时，最小高度折叠可用折半搜索方法对超过O(n2 )个可能值进行搜索来实现，可能的高度值为h(i,j)+ri +rj + 1。在检测每个高度时，也可用（ 1 5 - 1 3）式来确定该折叠的宽度是否小于等于W。这种情况下总的时间消耗为O (n2 l o gn)。

3. 标准单元折叠

用wi 定义单元Ci 的宽度。每个单元的高度为h。当标准单元行的宽度W 固定不变时，通过减少折叠高度，可以相应地减少折叠面积。考察Ci 到Cn 的最小高度折叠。设第一个折叠点是Cs+ 1。从元件Cs+1 到Cn 的折叠必须使用最小高度，否则，可使用更小的高度来折叠Cs+1 到Cn，从而得到更小的折叠高度。所以这里仍可使用最优原理和动态规划方法。

令Hi , s 为Ci 到Cn 折叠成宽为W的矩形时的最小高度，其中第一个折叠点为Cs+ 1。令w s u m(i, s)=s ?j = iwj。可假定没有宽度超过W的元件，否则不可能进行折叠。对于Hn,n 因为只有一个元件，不存在连线问题，因此Hn, n =h。对于H i, s（1≤i＜s≤n）注意到如果w s u m(i, s )＞W，不可能实现折叠。若w s u m(i,s)≤W，元件Ci 和C j + 1 在相同的标准单元行中，该行下方布线通道的高度为ls+ 1（定义ln+1 = 0）。因而：Hi, s = Hi+1, k （1 5 - 1 4）

当i=s＜n 时，第一个标准单元行只包含Ci 。该行的高度为h 且该行下方布线通道的高度为li+ 1。因Ci+ 1 到Cn 单元的折叠是最优的.

为了寻找最小高度折叠，首先使用式（ 1 5 - 1 4）和（1 5 - 1 5）来确定Hi, s （1≤i≤s≤n）。最小高度折叠的高度为m in｛H1 , s｝。可以使用回溯过程来确定最小高度折叠中的折叠点。

讲解：一个寻找关键字－－searchkey
另一个是插入一个结点：insertTree
另外这是一个完全的先序遍历二叉树的语法。先根结点，再左结点，如无再右结点，如些加归至搜索完毕。