有效文本编辑的七种习惯
Bram Moolenaar
 
如果你的很多时间是用来敲纯文本，写程序或HTML，那么有效地使用一个好的编辑器能节省你不少时间。这篇文章里的指导和提示将有助于你更快工作，更少犯错误。

文中采用开源文本编辑器Vim(Vi IMproved)说明有效编辑的思路，但这些思路同样适用于其他编辑器。选择合适的编辑器只是有效编辑的第一步，对于哪个编辑器更
好的讨论将占很大地方，这里就不提了。如果你不知道该用哪个编辑器，或者对现在所使用的不太满意，不妨试试Vim；你是不会失望的。
 
第一部分：编辑一个文件
 
1.快速定位
 
编辑中大部分时间是花费在阅读、查错和定位上，而不是插入新文字或进行修改。在文件中不断定位(navigate)是经常要做的，所以最好学会如何快速地进行。
 
你常会搜寻文档中的一些文字。或者找出包含特定词或词组的行。你当然可以使用搜寻命令 /pattern，不过还有更聪明的方法：
 -- 如果你看到一个特定词，想看看其他地方是不是出现过同样的词，可以使用* 命令。它将对光标所指的词进行搜寻。
 -- 如果设置了 ' incsearch' 选项，Vim将在你正在输入搜寻模式的时候就显示搜寻的结果（而不是等到你敲了回车之后）。这能够使你更快地找出拼写
    错误。
 -- 如果设置了 ' hlsearch' 选项，Vim将使用黄色背景对搜寻结果进行高亮显示。你可以对搜寻的结果一目了然。应用在程序代码中可以显示变量的所有
    引用。你甚至不需要移动鼠标就能看到所有的搜寻结果。
 
对于结构化的文本，快速定位的办法就更多了。Vim提供专门针对C程序（以及C++、Java等类似语言）的特殊命令：
 -- 使用 %可以从开始括号跳到对应的关闭括号。或者从 ``#if'' 跳到对应的 ``#endif''。事实上， % 可以完成许多对应项之间的跳转。可
 以用来检查if()和{}结构是否平衡。
 -- 使用 [{可以在代码段(block)中跳回到段起始的 ``{``。
 -- 使用 gb 可以从引用某个变量的地方跳转到它的局部声明。
 
定位的方法当然不止这些。关键是你需要知道有这些命令。你也许会说不可能学会所有命令 — Vim里有成百个定位命令，有的很简单，有的很聪明 — 这需要
几星期的学习。不过，你不必如此；你只需要了解自己的编辑特点，然后掌握相关的定位命令就可以了。
 
可以采取三个基本步骤：
 1. 在你进行编辑的时候，注意那些重复进行的操作。
 2. 找出能快速进行这些操作的编辑命令。阅读文档，问问朋友，或者看看其他人是如何做的。
 3. 进行练习，知道熟练为止。
 
让我们通过以下这个例子说明一下：
 1. 你发现在写C程序时，经常要查找函数定义。你目前使用 * 命令对函数名进行搜寻，但得到的往往是函数的引用而不是函数定义。你觉得一定会有更好的办法。
 2. 读过一篇快速参考以后，你发现关于定位标记的说明，里面说明了如何定位函数定义，这正是你要找的！
 3. 你试着使用Vim自带的ctags程序,生成了一个tags文件。你学会了使用 CTRL-] 命令，发现这省了不少事。为了更方便，你在 Makefile 里加入了几行以自动生成标记文件。
 
当你使用以上三个步骤时，有几点需要注意的地方：
 -- ``我只想完成任务，不想去读那些文档来找新的命令。''。如果你真的是这么想的，那么你将永远停留在计算的石器时代。有些人编写什么都用
 Notepad，却总不明白为什么其他人总能用他一半的时间成任务。
 -- 不要过分。如果你总为一点小事也要去找完美的命令，你就没法集中精力到你本要完成的任务上了。只要找出那些耗费过多时间的操作，然后使用相关
 的命令直到熟练就可以了。这以后你就能集中精力到自己的文本上了。
 
下面这些章节给出了大多数人遇到的操作。你仿照它们在实际工作中使用三个基本步骤。
 
2.不要敲两次
 
我们所使用的字词集合是有限的。既使是词组和句子也不过是有限的几个。对于程序来说更是如此。很明显，你不想把同样的东西敲上两遍。

你经常会想把一个词替换成另一个。如果是全文件替换，你可以使用:s (substitute)命令。如果只是几个位置需要被替换，一个快速办法是使
用 * 命令找出下一个词，使用 cw 来进行替换。然后敲n 找到下个词，再用 . 重复 cw 命令。
 
. 命令重复上一个改变。这里的改变是插入、删除或替换操作。能够重复进行操作是个极为强大的机制。如果好好使用它，那么你大部分的编辑工作可能只不过是敲几下 . 的事。小心不要在两次重复之间做其他修改，因为这将改变你要重复的操作。如果确实需要如此，可以使用 m 命令记住要修改的位置，等重复操作进行完毕之后再回过头来修改它。
 
有些函数名和变量名可能很难敲。你能准确无误地输入``XpmCreatePixmapFromData''么？Vim的自动补齐机制能给你省不少事。它查看你正在编辑的文件以及#include文件，你可以只敲入``XpmCr''，然后使用CTRL-N 命令让Vim把它补齐为``XpmCreatePixmapFromData''。这不但节省了输入时间，而且减少了输入的错误。

如果你有同样的词组或句子需要输入多次，还有个更简单的办法。Vim可以进行录制宏。使用 qa 命令开始在'a'寄存器里录制宏。然后正常地输入编
辑命令，最后用 q 退出录制状态。如果你想重复所录制的命令，只需执行 @a 命令。Vim总共提供26个这样的宏寄存器。
 
使用宏录制功能可以记录各种操作，不只限于插入操作。如果你想重复一些东西，不妨一试。
 
需要注意的是记录的命令会被原封不动地重复执行。在进行定位时简单的重复宏操作可能不是你想要的结果。比如对于一个词这里可能需要左移4个字符，在下
个地方可能就要左移5个字符。所以必须定位到合适的位置再重复进行宏操作。
 
如果你要重复的命令很复杂，把它们一次敲进去会很困难。这时你可以写一个脚本或宏。这常被用于建立代码模板；比如，一个函数头。你想做得多聪明就可以
做得多聪明。
 
3.知错就改
 
编辑时经常会出错。无人能免。关键是快速发现并进行改正。编辑器应该提供这方面的支持，不过你必须告诉它什么是对什么是错。
 
你可能常常会重复同样的错误，你的手指所做的并非是你要它做的。可以使用缩
写(abbreviation)进行修正。下面是一些例子：
  :abbr Lunix Linux
  :abbr accross across
  :abbr hte the
这些词会在编辑时被自动改正。
 
同样的机制也可以用于对很长的词语进行缩写。特别适用于输入那些你觉得很难敲的词，它可以避免出错。比如：
  :abbr pn pinguin
  :abbr MS Mandrake Software
但有时候你想要的正是那些缩写，比如想插入``MS''。所以缩写中最好使用那些不会出现在文中的词。
 
Vim提供了一个很聪明的高亮机制，一般用于程序的语法高亮，不过也可以用来查错。
 
语法高亮会使用颜色显示注释。这听上去不是什么特别重要的功能，不过一旦用起来就会发现这其实很有用。你能够快速地发现那些没有高亮却本应作为注释的
文字（可能是因为忘了敲注释符）。也可以发现一些被错误当成注释的代码（可能是因为忘了敲``*/''）。这些错误在黑白方式下是很难被发现的，浪费了不少
调试时间。
 
语法高亮也可以用来查找不匹配的括号。一个未被匹配的``)''会被亮红色背景加以标识。你可以使用 % 命令他们是被如何匹配的，然后把``(''或
``)''插入到合适的位置。
 
另一类常犯的错误也很容易发现，比如把 ``#include ＜stdio.h＞''敲成了``#included ＜stdio.h＞''。在黑白方式下这是很难发现的，但在语法高亮下
则能很快发现``include''能被高亮而``included''没有。
 
再看一个更复杂的例子：对于英文文本你可以定义一个所要使用的词的长列表。所有未在表中出现的词都可能是错误，并进行高亮显示。可以定义几个用于编辑
词表的宏。这正是字处理器的拼写检查功能。Vim中是靠一些脚本来实现的，你
也可以对它进行定制：比如，只对注释中的文字进行拼写检查。
 
第二部分：编辑多个文件
 
4.文件总是成帮结伙
 
人们很少只编辑一个文件。一般需要顺序或同时编辑一些相关的文件。你应该利用编辑器使多文件编辑工作更为高效。
 
上面提到的标识(tag)机制也支持跨文件搜寻。一般做法是为项目的所有文件生成tags文件，然后在项目的所有文件中搜寻函数、结构、类型(typedefs)等的定
义。这比手工搜寻要快捷的多；我浏览一个程序要做的第一件事便是建立标识文件。
 
另一个强大的功能是使用 :grep 命令对一组文件进行模式搜寻。Vim把搜寻结果做成一个列表，然后跳到第一个结果。使用 :cn 命令跳到下
一个结果。如果你想改变一个函数调用的、参数个数，那么这个功能会很有用。
 
头文件里有很多有用的信息。然而要知道一个声明出现在哪个头文件中却需要花不少时间。Vim能够理解头文件，能够从中找到你需要的东西。把光标移动到函
数名下，然后敲 [I：Vim就会显示出一个头文件中该函数名的所有匹配。如果你想得到更详细的结果，可以直接跳到声明中。一个类似的命令可以用于检
查你所使用的头文件是否正确。
 
你可以把Vim的编辑区域进行分隔，用来编辑不同的文件。你可以对两个或多个文件进行比较，或者进行拷贝/粘贴。有许多命令用于打开关闭窗口，文件间跳
转，暂时隐藏文件等等。可以再使用上面提到的三个基本步骤选择合适的命令进行学习。
 
多窗口还有更多的用法。预览标识(preview-tag)就是个很好的例子。它打开一个特殊的预览窗口，光标还保留在你正在编辑的文件中。预览窗口中可以是光标
所指函数的声明。如果你移动光标到另一个名字下，停留一两秒，预览窗口中就会显示那个名字的定义。名字还可以是头文件中声明的结构或函数。
 
5.让我们一起来工作
 
编辑器可以编辑文件。e-mail程序可以收发消息。操作系统可以运行程序。每个程序都有它自己的任务，而且应该做好。如果能让程序一同工作，那么就会实现
很强大的功能。
 
举个简单的例子：选择一个列表中的结构化的文字，并对它进行排序：!sort。这将使用外部命令``sort''来过滤文件。容易吧？排序功能是可以
添加到编辑器中的。不过看一下``man sort''就知道它有很多选项。它可能用了一个极为精巧的排序算法。你还打算把它加到编辑器中么？更何况还有其他不少
过滤程序。编辑器可能会变得很大。
 
Unix精神的一个体现就是提供独立的程序，各自做好自己的任务，然后组合起来完成更大的任务。不幸的是，许多编辑器不能很好地和其他程序一起工作，比如，
你不能包Netscape的邮件编辑器换成其他编辑器。这样你只能使用那个不顺手的程序。另一个趋势是在编辑器里提供所有的功能，Emacs就是个代表（有人说
Emacs其实是个操作系统，只是可以用来编辑文件）。
 
Vim尽力和其他程序集成，但这需要经过斗争。目前Vim已经可以作为MS-Developer Studio和Sniff的编辑器。一些e-mail程序（比如Mutt）也支持外
部编辑器。和Sun Workshop的集成工作正在进行中。总的来说这个领域还有待提高。将来我们会有一个大于其各部分总和的系统。
 
6.文本结构化
 
你可能经常会遇到有一些结构的文本，这些结构可能同于那些现有命令所支持的结构。这样你不得不利用那些底层的``砖头''创建你自己的宏和脚本。这里说明
的就是这类更复杂的东西。
 
有个简单的办法可以加速编辑-编译-修改这个循环。Vim提供 :make 命令，用于进行编译，并且获取错误输出，把你带到发生错误的地方进行修正。如
果你使用了另一个编译器，那么错误就无法被Vim获得。如果不想自己动手，可以修改' errorformat'选项。告诉Vim错误是什么样子，以及如何从中获
得文件名和行号。它支持复杂的gcc错误信息，所以应该也能支持其他编译器。
 
有时处理一个新的文件类型只需要设置几个选项或写一些宏。比如，为了在man手册中进行跳转，你可以写一个宏获取光标下的词，清除缓冲区，然后读入新的
man手册。这是简单而高效的参照(cross-reference)方法。
 
使用三个基本步骤，你可以更有效地处理各种结构化文件。只需要想想你想对文件采取的操作，然后找到相应的命令去用就是了。就这么简单，你只要去做就成了。
 
第三部分：磨刀
 
7.养成习惯
 
要学会开车必须下功夫。这是不是你只骑自行车的原因么？当然不是，你会发现你必须花时间来获得所需的技术。文本编辑也不例外。你需要学习新的命令和技巧。
 
另一方面，你不应该试图学习编辑器提供的每个命令。这是彻底的浪费时间。大多数人只需要学习10%到20%的命令就足够工作了。但是每个人所需要的命令都
各不相同。你需要不断学习，找出那些可以自动完成的重复操作。如果你只做一次操作，而且以后也不会再去做，那么就不需要进行优化。是如果你发现你在过
去的一小时中重复了好几遍同样的操作，那么就有必要查看一下手册，看看能否更快速地完成。或者写一个宏来做。如果是是个不小的任务，比如对一类文本进
行对齐，你需要阅读一下新闻组或看看Internet上是不是有人已经解决了同样的问题。
 
最根本的步骤是最后的那一个。你可能能够找到一个重复性的任务，找到一个不错的作法，可过了一个周末就彻底忘了自己是怎么做的了。这不成。你必须重复
你的作法直到烂熟于胸。只有这时你才真正获得了你需要的高效。一次不要学得太多。一次只试一些工作得很好的方法。对于那些不常用的技巧，你可能只需要
把它记下来，留待以后查阅。总之，如果抱着这样的目标，你的编辑技能就会更加有效。
 
最后需要指出的是，如果人们忽略了以上几点会发生什么：我仍然可以看到有人盯着屏幕看上半天，用两个指头敲几下，然后继续抬头看着屏幕，还抱怨自己太
累.. 把十个指头都用上！这不光更快，还不累。每天抽出一个小时练习一下指法，只要几星期就足够了。
 
后记
 
想法的名字来自于Stephen R. Covey所著的那本畅销书《高效人的七种习惯》(``The 7habits of highly effective people'')。
我推荐它给那些想解决个人和专业问题的人们（谁不想呢？)。
尽管有些人声称它来自Scott Adams所著的"Seven years of highly defective people"（同样推荐！）。详见：http://www.vim.org/iccf/click1.html。
 
关于作者
 
Bram Moolenaar是Vim的主要作者。他编写了Vim核心功能，并采纳了许多开发者提供的代码。他的e-mail地址是：Bram@Moolenaar.net

翻译来源：http://www.newsmth.net/bbscon.php?bid=731&id=353，文中做了很少的修该。

英文原文：http://www.moolenaar.net/habits_paper.txt

首先，欢迎来到程序员的世界。在这个世界上，不是有很多人想创造软件并解决问题。你是一名hacker，属于那些愿意做一些有挑战性的事情的人。

　　“当你不创造东西时，你只会根据自己的感觉而不是能力去看待问题。” – WhyTheLuckyStiff

　　对于下面的文字你不必完全接受，所有这些来自一个其貌不扬的程序员。我喜欢把事情做到最好，而不是对原来的东西修修补补。

　　仅仅是因为爱好开始做一些创新，这是一个很好的开始！如果你说“我要先学习一下再开始做”那么你永远不会真正开始。每个人都需要从某个地方开始，所以现在打开你的编辑器开始写代码吧。

　 　下面是一些很重要的建议，虽然有人并不认同，但我保证你看完我的分析以后会站在我这一边。一开始，先不要管算法和数据结构。大多数简单的程序不需要用到 算法和数据结构，所以当你真正需要时再去学习。编程一段时间以后，你就会知道在哪些地方用到他们。这时知道算法的名字并了解它们的功能，然后找一些相关的 论文去理解算法并动手编程实践。如果没有现成的函数库（其他程序员提供的可重用代码），你用自己喜欢的编程语言来实现它。

　　0. 选择一门好的编程语言，一门你自认为可以用它快速地做出一些有用东西的语言。

　 　不要选择C语言作为你第一门编程语言。也许选择C语言会给你一种过时的满足感。虽然它比早期的汇编语言提供了更好语法描述，但是今天C（或者C++）不 是能够快速编写软件的语言。毫不偏袒的说，我建议你学习一种动态语言。选择一种你觉得语法（文档）让你使用起来更舒服的编程。为此，你可能需要花费一些时 间来在几种不同的语言之间进行比较。这么做目的不是为了让你感觉更好或者让编程更容易。更快地完成自己的作品并且能够看到成果，才是激励你编程的源动力。 不要选择一门需要某种重量级的IDE（IDE是一种能够帮助你编写并运行代码的工具）才能轻松编程的语言。你所需要的仅仅是一个文本编辑器。（注：原文并 没有标号，是我们加上的，请大家别忘记了哦，我们是从零开始数数的。:) ）

　　1. 选择一个好的编辑器。

　　编辑器对程序员而言，就是像是弓对弓箭手一样重要。这里有一些推荐的编辑器：

• SublimeText 2 – 如果你刚开始编程，推荐使用SublimeText 2

• Emacs – 学习曲线陡峭，快捷键复杂。如果你想定制自己的使用习惯，需要学习Emacs Lisp.

• Vim – 不仅操作简洁而且它默认包含在linux的发行版中，所以深受大家欢迎。我开始使用了2年Emacs。由于Emacs的快捷键操作过于复杂，我的双手开始 经常疼痛，这迫使我转向了Vim阵营。了解Vim的快捷键是非常有必要的。当你在远程的服务器上编辑代码时，你唯一不需要安装的编辑器就是Vim。

　　注意！Emacs和Vim可能已经成为成为古董了。但是，它们都具备一些现代编辑器多不具备的功能。

　　2. 选择一个你可以从中学到东西的操作系统

　 　Windows不会教会你任何东西。使用Windows你唯一学会的就是打开一个exe（可执行）文件来安装软件和使用它。可能刚开始的时候你会觉得很 酷，但是长远来看，如果你立志成为一个web开发人员，可能还是要具备基本的linux知识，尤其是当你要发布程序的时候。Linux也允许你根据自己的 要求来定制程序。Macs也很酷，但是我认为你现在经济上还负担不起。

　　3. 不要通过复制粘贴来做备份

　 　一个新手程序员通常会把文件复制粘贴到一个临时目录下面来进行备份。这也许也是他们唯一知道的方法。不要那么做！你需要使用版本控制软件。我强烈推荐使 用Git，它是个目前很流行的版本控制工具，而且使用起来非常简单。对一个Git新手，有一个良好的社区和很多参考资源来学习。（除了Git之外，还有 mercurial, darcs, fossil等等。但是我还是建议从Git开始，我有很多的理由来支持Git，这里就不多费口舌了。）

　　4. 知道去哪里寻求帮助

　 　参加一个和你相关的（你使用编程工具相关的）程序员社区。比如StackOverflow就是程序员的Facebook。那里没有消息状态和回复，取而 代之的是问题和答案。除此之外还要学会使用IRC。IRC是一种老式的聊天室，现在还在被大多数开发人员用来分享技术信息和帮助解决问题。

　　5. 培养你的礼仪

　 　知道什么时候问问题。你遇到的大多数问题都是别人碰到过并且在Internet上能够找到解答的。在IRC或者任何论坛里发问之前，先搜索一下 google（或者blekko）来看看是不是有现成的答案。在IRC上问问题需要有耐心。永远记住，人们只是处于好心来免费帮助你。有时你发问以后需要 几个小时才能有回复。所以，耐心等待。除此之外，记得问问题的时候要礼貌。世界很小，你怎么对待别人，别人就会怎么对待你。

　　6. 结交朋友，技术书籍只能教你解决常见的问题（他们说：书是死的）

　 　当你在捣鼓一些程序或者从程序的作者那里学习，你能学到一些书本上没有的东西。当你散步的时候，请和遇到的朋友打招呼。你肯定不是唯一的程序员。和其他 的程序员一起交朋友一起工作。你会注意到，当一群技术爱好者在一起的时候，不论话题是从什么地方开始，最后总是以技术话题收尾。这是必然的现象。所以你可 以尽情参与。在你的黄金年龄努力编程，我能告诉你的是，我在开始6年前寻找朋友并开始讨论编程，从那时起才学到那些书本和文章不会我的东西。所以我总是 说，我的编程经验有6年，因为只有那个时候开始，我才开始与人交流并开始感觉真正地开始学习编程。

　　7. 参加开源项目

　 　为开源项目编写代码能带来回报。这不仅仅是帮助别人，你留下的代码会被其他人使用或（可能）改进。当别人给你的代码添加功能或者提出修改意见时，也是在 提高你的编程水平。开源软件项目不一定要是一个大工程，编写一个下载youtube视频的小程序也是很有用的。更重要的是，你会惊奇地发现你编写的代码会 成为与他人有效沟通的桥梁。

　　最后，若干年之后如果本文的内容曾经对你有一点点的帮助，作为回报请写一封类似的信给希望开始编程并不知如何入手的朋友，有可能的话请纠正本文中过时的内容。

　　智者说过，掌握某个东西需要10年或10000个小时，也就是汉语中的“十年磨一剑”，所以不用着急。

　　英文原文：An open letter to those who want to start programming

　　中文翻译：伯乐在线

#!/usr/bin/python
class Graph:
	def __init__(self,nv):
		self.v=nv
		self.e=0
		self.adj=[]
		for ele in range(nv):
			self.adj.append([])
			ele+=1
	
	def insert(self,e):
		u=e[0]
		v=e[1]
		self.adj[u].append(v)
		#self.adj[v].append(u) 
		self.e+=1

	def dfs(self):
		global p
		global c
		global d
		global f
		global time
		global t
		p=[]
		c=[]
		d=[]
		f=[]
		t=[]
		for ele in range(self.v):
			ele+=1
			p.append(-1)
			c.append(0)
			d.append(0)
			f.append(0)
			t.append(0)
		time=0
		m=0
		for elev in range(self.v):
			if c[elev] == 0:
				self.dfs_visit(elev,m)
	
	def dfs_visit(self,u,m):
		global time
		c[u]=1
		t[u]=m
		time+=1
		d[u]=time
		for v in self.adj[u]:
			if c[v] == 0:
				p[v]=u
				t[v]=m
				self.dfs_visit(v,m)
		c[u]=2
		time+=1
		f[u]=time

	
	'''def printpath(self,s,v):
		if s==v:
			print s,
		elif p[v]==-1:
			print 'no path',
		else:
			self.printpath(s,p[v])
			print v,'''
def scc(g):
	g.dfs()
	gt=Graph(g.v)
	for u in range(len(g.adj)):
		for v in g.adj[u]:
			gt.adj[v].append(u)
		u+=1
	f1=[]
	for e in f:
		f1.append(e)
	for i in range(gt.v):
		p[i]=-1
		c[i]=0
		d[i]=0
		f[i]=0
		t[i]=0
	print c
	time=0
	global m
	m=0
	for i in range(gt.v):
		v=max(f1)
		fi=f1.index(v)
		if c[fi] == 0:
			m+=1
			gt.dfs_visit(fi,m)
		f1[fi]=-1

if __name__=='__main__':
	g=Graph(8)
	e=[(0,1),(1,2),(1,4),(1,5),(2,3),(2,6),(3,2),(3,7),(4,0),(4,5),(5,6),(6,5),(6,7),(7,7)]
	for each in e:
		g.insert(each)
	scc(g)
	print t
	for i in range(m+1):
		for v in range(g.v):
			if t[v]==i+1:
				print v,
		print '\n'

在ubuntu下备份mysql数据库是出现：

mysqldump: Got error: 1045: Access denied for user 'root'@'localhost' (using password: YES) when trying to connect

1. mysql -u root -p
2. mysql> update user set password=password('***') where user='root';
3. mysql> flush privileges;
4. sudo service  mysql stop
5. sudo service  mysql start

这样就可以用：mysqldump 来备份了。

解法：回溯法。

思路：在遍历的子集树的过程中，应该注意筛选出可行的解，同时当有更好的解时，不断地更新最优解。

#include<stdio.h>
#define N 4

int x[N];
int p[N];
int w[N];
int c;
int pmax;
int pcur;
int wcur;

int bound(int t){
	int i,pr;
	pr=pcur;
	for(i=t;i<N;i++)
		pr+=p[i];
	if(pr>pmax)
		return 1;
	return 0;
}

void backtrace(int t){
	int i;
	if(t>=N){
		if(pmax<pcur){
			pmax=pcur;
			for(i=0;i<N;i++)
				printf("%d ",x[i]);
			printf("\n");
		}
	}
	else{
	for(i=1;i>=0;i--){
		x[t]=i;
		if(i){
			if(w[t]+wcur<=c){
			wcur+=w[t];
			pcur+=p[t];
			backtrace(t+1);
			wcur-=w[t];
			pcur-=p[t];
			}
		}
		else if(bound(t))
			backtrace(t+1);
	}
	}
}

int main(){
	c=7;
	w[0]=3;
	w[1]=5;
	w[2]=2;
	w[3]=1;

	p[0]=9;
	p[1]=10;
	p[2]=7;
	p[3]=4;

	backtrace(0);
	printf("the max :%d\n",pmax);

	return 0;
}

问题：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线（2条）上，问有多少种摆法。 

解法：采用回溯算法。

#include<stdio.h>
#include<stdlib.h>

#define N 9 
int x[N];
void vswap(int *pi,int *pj){
    int tmp=*pi;
    *pi=*pj;
    *pj=tmp;
}

void out(int * x,int n){
    int i;
    for(i=1;i<n;i++)
        printf("%d ",x[i]);
    printf("\n");
}

void init(int *x,int n){
    int i;

    for(i=1;i<n;i++)
        x[i]=i;
}

int bound(int t){
   int i;
   for(i=1;i<t;i++)
       if(abs(x[i]-x[t])==abs(i-t)||x[t]==x[i])
           return 0;
   return 1;

}

void traceback(int t){
    if(t>=N){
        out(x,N);
    }
    else{
        int i;
        for(i=t;i<N;i++){
            vswap(&x[t],&x[i]);
            if(bound(t))
                traceback(t+1);
            vswap(&x[t],&x[i]);
        }
    }
}

int main(){
    init(x,N);
    traceback(1);
    return 0;
}

运行：

gcc -o 8q 8q.c 

结果：

./8q|wc -l

为：92.

回溯法：从问题的某一种状态（初始状态）出发，搜索从这种状态出发所能达到的所有“状态”，当一条路走到“尽头”的时候（不能再前进），再后退一步或若干步，从另一种可能“状态”出发，继续搜索，直到所有的“路径”（状态）都试探过。这种不断“前进”、不断“回溯”寻找解的方法，就称作“回溯法”。

回溯算法：

1. 形式化解的结构，根据形式描述，建立解树。解树的每个非叶子节点描述一类可行解，而叶子节点通常描述一个可行解。
2. 利用深度优先搜索解空间。算法根据目标函数，确定节点所代表解的优化程度，当访问叶子节点时，解就唯一的确定了；访问中间节点时还没法唯一的确定，无法计算目标函数值。利用启发函数和分支定界，避免移动到不可能产生解的子空间。问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。

解空间：

回溯算法的解空间一般分为：子集树和排列树。

子集树：二叉树来表示，较为熟悉。

排列树：第一层树有n个选择，第二层有n-1个选择，以此类推，直到叶子节点。

子集树和排列树都是“隐式图”。

子集树遍历的伪代码：

void backtrack(int  t)

{
     if(t>n)   
        output(x);
     else
        for(int i=0; i<=1; i++)
      {  
             x[t] = i; 
             backtrack(t+1);
       }  
}

排列树遍历的伪代码：

     void backtrack(int  t)

    {
       if(t>n)  

           output(x);
       else      

          for(int i=t; i<=n; i++)
          {
            swap(x[t], x[i]);
            backtrace(t+1);
            swap(x[t], x[i]);       

         }     

   }

上次记录了，0/1背包问题动态规划的递归实现，下面记录一下也是动态规划的非递归实现。主要是对f函数结果的记录，使得不用像递归中的重复计算。

#include<stdio.h>
#include<stdlib.h>

#define max(a,b) (a)>(b)?(a):(b)
#define min(a,b) (a)<(b)?(a):(b)
#define N 3
#define C 116

int p[N+1];
int w[N+1];
int f[N+1][C+1];
int x[N+1];
void bag(){
    int y,ymax,i;

    ymax=min(w[N]-1,C);
    for(y=0;y<ymax;y++)
        f[N][y]=0;
    for(y=w[N];y<C;y++)
        f[N][y]=p[N];

    for(i=N-1;i>1;i--){
        ymax=min(w[i]-1,C);
        for(y=0;y<ymax;y++)
            f[i][y]=f[i+1][y];
        for(y=w[N];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[2][C],f[2][C-w[1]]+p[1]);
}

void traceback(){
    int i,c;
    
    c=C;
    for(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[1][C])?1:0;
    }

int main(){
    w[1]=100;
    w[2]=14;
    w[3]=10;
    p[1]=20;
    p[2]=18;
    p[3]=15;
    bag();
    printf("the max :%d\n",f[1][C]);
    traceback();
    int i;
    for(i=1;i<=N;i++)
        printf("%d ",x[i]);
    printf("\n");
    return 0;
}
    

时间复杂度：bag是：O（nc)。如果c很大，则时间要比递归的长。