编程之五大算法

一、分治法

 在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……

    任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。

    分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

    分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

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

    分治法所能解决的问题一般具有以下几个特征：

    1) 该问题的规模缩小到一定的程度就可以容易地解决

    2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

    3) 利用该问题分解出的子问题的解可以合并为该问题的解；

    4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

    上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

    分治法的基本步骤

    分治法在每一层递归上都有三个步骤：

    分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

    解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题

    合并：将各个子问题的解合并为原问题的解。

    它的一般的算法设计模式如下：

    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的解。

    分治法的复杂性分析

    一个分治法将规模为n的问题分成k个规模为n／m的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：

          

    通过迭代法求得方程的解：

         

    递归方程及其解只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足够平滑，那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的，从而当mi≤n<mi+1时，T(mi)≤T(n)<T(mi+1)。

二、动态规划法

最优化原理

    1951年美国数学家R．Bellman等人，根据一类多阶段问题的特点，把多阶段决策问题变换为一系列互相联系的单阶段问题，然后逐个加以解决。一些静态模型，只要人为地引进“时间”因素，分成时段，就可以转化成多阶段的动态模型，用动态规划方法去处理。与此同时，他提出了解决这类问题的“最优化原理”(Principle of optimality)：

    “一个过程的最优决策具有这样的性质：即无论其初始状态和初始决策如何，其今后诸策略对以第一个决策所形成的状态作为初始状态的过程而言，必须构成最优策略”。简言之，一个最优策略的子策略，对于它的初态和终态而言也必是最优的。

    这个“最优化原理”如果用数学化一点的语言来描述的话，就是：假设为了解决某一优化问题，需要依次作出n个决策D1，D2，…，Dn，如若这个决策序列是最优的，对于任何一个整数k，1 < k < n，不论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策Dk+1，Dk+2，…，Dn也是最优的。

    最优化原理是动态规划的基础。任何一个问题，如果失去了这个最优化原理的支持，就不可能用动态规划方法计算。能采用动态规划求解的问题都需要满足一定的条件：

    (1) 问题中的状态必须满足最优化原理；

    (2) 问题中的状态必须满足无后效性。

    所谓的无后效性是指：“下一时刻的状态只与当前状态有关，而和当前状态之前的状态无关，当前的状态是对以往决策的总结”。

    问题求解模式

    动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。

    初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态

    图1 动态规划决策过程示意图

    (1)划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。

    (2)确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。

    (3)确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两段各状态之间的关系来确定决策。

    (4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。

    算法实现

    动态规划的主要难点在于理论上的设计，也就是上面4个步骤的确定，一旦设计完成，实现部分就会非常简单。使用动态规划求解问题，最重要的就是确定动态规划三要素：问题的阶段,每个阶段的状态以及从前一个阶段转化到后一个阶段之间的递推关系。递推关系必须是从次小的问题开始到较大的问题之间的转化，从这个角度来说，动态规划往往可以用递归程序来实现，不过因为递推可以充分利用前面保存的子问题的解来减少重复计算，所以对于大规模问题来说，有递归不可比拟的优势，这也是动态规划算法的核心之处。确定了动态规划的这三要素，整个求解过程就可以用一个最优决策表来描述，最优决策表是一个二维表，其中行表示决策的阶段，列表示问题状态，表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值（如最短路径，最长公共子序列，最大价值等），填表的过程就是根据递推关系，从1行1列开始，以行或者列优先的顺序，依次填写表格，最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。下面分别以求解最大化投资回报问题和最长公共子序列问题为例阐述用动态规划算法求解问题的一般思路。

 三、贪心算法

 所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

    贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

    贪心算法的基本思路如下：

    1.建立数学模型来描述问题。

    2.把求解的问题分成若干个子问题。

    3.对每一子问题求解，得到子问题的局部最优解。

    4.把子问题的解局部最优解合成原来解问题的一个解。

    实现该算法的过程：

    从问题的某一初始解出发；

    while 能朝给定总目标前进一步 do

    求出可行解的一个解元素；

    由所有解元素组合成问题的一个可行解；

    下面是一个可以试用贪心算法解的题目，贪心解的确不错，可惜不是最优解。

    例题分析

    [背包问题]有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。

    要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

    物品 A B C D E F G

    重量 35 30 60 50 40 10 25

    价值 10 40 30 50 35 40 30

    分析：

    目标函数： ∑pi最大

    约束条件是装入的物品总重量不超过背包容量：∑wi<=M( M=150)

    （1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？

    （2）每次挑选所占重量最小的物品装入是否能得到最优解？

    （3）每次选取单位重量价值最大的物品，成为解本题的策略。 ?

    值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。

    贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。

    可惜的是，它需要证明后才能真正运用到题目的算法中。

    一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。

    对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下：

    （1）贪心策略：选取价值最大者。反例：

    W=30

    物品：A B C

    重量：28 12 12

    价值：30 20 20

    根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。

    （2）贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。

    （3）贪心策略：选取单位重量价值最大的物品。反例：

    W=30

    物品：A B C

    重量：28 20 10

    价值：28 20 10

    根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。

四、回溯法

 回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

    1、回溯法的一般描述

    可用回溯法求解的问题P，通常要能表达为：对于已知的由n元组（x1，x2，…，xn）组成的一个状态空间E={（x1，x2，…，xn）∣xi∈Si ，i=1，2，…，n}，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中Si是分量xi的定义域，且 |Si| 有限，i=1，2，…，n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。

    解问题P的最朴素的方法就是枚举法，即对E中的所有n元组逐一地检测其是否满足D的全部约束，若满足，则为问题P的一个解。但显然，其计算量是相当大的。

    我们发现，对于许多问题，所给定的约束集D具有完备性，即i元组（x1，x2，…，xi）满足D中仅涉及到x1，x2，…，xi的所有约束意味着j（j<i）元组（x1，x2，…，xj）一定也满足D中仅涉及到x1，x2，…，xj的所有约束，i=1，2，…，n。换句话说，只要存在0≤j≤n-1，使得（x1，x2，…，xj）违反D中仅涉及到x1，x2，…，xj的约束之一，则以（x1，x2，…，xj）为前缀的任何n元组（x1，x2，…，xj，xj+1，…，xn）一定也违反D中仅涉及到x1，x2，…，xi的一个约束，n≥i>j。因此，对于约束集D具有完备性的问题P，一旦检测断定某个j元组（x1，x2，…，xj）违反D中仅涉及x1，x2，…，xj的一个约束，就可以肯定，以（x1，x2，…，xj）为前缀的任何n元组（x1，x2，…，xj，xj+1，…，xn）都不会是问题P的解，因而就不必去搜索它们、检测它们。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比枚举法效率更高的算法。

    回溯法首先将问题P的n元组的状态空间E表示成一棵高为n的带权有序树T，把在E中求问题P的所有解转化为在T中搜索问题P的所有解。树T类似于检索树，它可以这样构造：设Si中的元素可排成xi(1) ，xi(2) ，…，xi(mi-1) ，|Si| =mi，i=1，2，…，n。从根开始，让T的第I层的每一个结点都有mi个儿子。这mi个儿子到它们的双亲的边，按从左到右的次序，分别带权xi+1(1) ，xi+1(2) ，…，xi+1(mi) ，i=0，1，2，…，n-1。照这种构造方式，E中的一个n元组（x1，x2，…，xn）对应于T中的一个叶子结点，T的根到这个叶子结点的路径上依次的n条边的权分别为x1，x2，…，xn，反之亦然。另外，对于任意的0≤i≤n-1，E中n元组（x1，x2，…，xn）的一个前缀I元组（x1，x2，…，xi）对应于T中的一个非叶子结点，T的根到这个非叶子结点的路径上依次的I条边的权分别为x1，x2，…，xi，反之亦然。特别，E中的任意一个n元组的空前缀（），对应于T的根。

    因而，在E中寻找问题P的一个解等价于在T中搜索一个叶子结点，要求从T的根到该叶子结点的路径上依次的n条边相应带的n个权x1，x2，…，xn满足约束集D的全部约束。在T中搜索所要求的叶子结点，很自然的一种方式是从根出发，按深度优先的策略逐步深入，即依次搜索满足约束条件的前缀1元组（x1i）、前缀2元组（x1，x2）、…，前缀I元组（x1，x2，…，xi），…，直到i=n为止。

    在回溯法中，上述引入的树被称为问题P的状态空间树；树T上任意一个结点被称为问题P的状态结点；树T上的任意一个叶子结点被称为问题P的一个解状态结点；树T上满足约束集D的全部约束的任意一个叶子结点被称为问题P的一个回答状态结点，它对应于问题P的一个解

    用回溯法解题的一般步骤：

    （1）针对所给问题，定义问题的解空间；

    （2）确定易于搜索的解空间结构；

    （3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

五、分支限界法

 C++，这个词在中国大陆的程序员圈子中通常被读做"C加加"，而西方的程序员通常读做"C plus plus"，它是一种使用非常广泛的计算机编程语言。C++是一种静态数据类型检查的，支持多重编程范式的通用程序设计语言。它支持过程化程序设计、数据抽象、面向对象程序设计、制作图标等等泛型程序设计等多种程序设计风格。

    美国AT&T贝尔实验室的本贾尼·斯特劳斯特卢普（Bjarne Stroustrup）博士在20世纪80年代初期发明并实现了C++（最初这种语言被称作"C with Classes"）。一开始C++是作为C语言的增强版出现的，从给C语言增加类开始，不断的增加新特性。虚函数（virtual function）、运算符重载（operator overloading）、多重继承（multiple inheritance）、模板（template）、异常（exception）、RTTI、名字空间（name space）逐渐被加入标准。1998年国际标准组织（ISO）颁布了C++程序设计语言的国际标准ISO/IEC 14882-1998。C++是具有国际标准的编程语言，通常称作 ANSI/ISO C++。1998年是C++标准委员会成立的第一年，以后每5年视实际需要更新一次标准，下一次标准更新将是在2009年，目前我们一般称该标准C++0x。遗憾的是，由于C++语言过于复杂，以及他经历了长年的演变，直到现在（2004年）只有少数几个编译器完全符合这个标准(这么说也是不完全正确的，事实上，至今为止没有任何一款编译器完全支持ISO C++)。

    另外，就目前学习C++而言，可以认为他是一门独立的语言；他并不依赖C语言，我们可以完全不学C语言，而直接学习C++。根据《C++编程思想》（Thinking in C++）一书所评述的，C++与C的效率往往相差在正负5%之间。所以有人认为在大多数场合C++ 完全可以取代C语言(然而我们在单片机等需要谨慎利用空间、直接操作硬件的地方还是要使用C语言)。

    子语言
    根据Effective C++第三版第一条款的描述，现在C++由以下四个"子语言"组成：

    1、C子语言。C++支持C语言的几乎全部功能，在语法上与C语言仅有极微妙的差别(如括号表达式的左右值性，具体请参考C++标准文献)。
    2、面向对象的C++。C++首先作为一门面向对象的语言而闻名，这个特点在这里不再详述。
    3、泛型编程语言。C++强大（但容易失控的）模板功能使它能在编译期完成许多工作，从而大大提高运行期效率。
    4、STL（C++标准模板库）。随着STL的不断发展，它已经逐渐成为C++程序设计中不可或缺的部分，其效率可能比一般的naive代码低些，但是其安全性与规范性使它大受欢迎。

    语言发展

    C++语言发展大概可以分为三个阶段：第一阶段从80年代到1995年。这一阶段C++语言基本上是传统类型上的面向对象语言，并且凭借着接近C语言的效率，在工业界使用的开发语言中占据了相当大份额；第二阶段从1995年到2000年，这一阶段由于标准模板库(STL)和后来的Boost等程序库的出现，泛型程序设计在C++中占据了越来越多的比重性。当然，同时由于Java、C#等语言的出现和硬件价格的大规模下降，C++受到了一定的冲击；第三阶段从2000年至今，由于以Loki、MPL等程序库为代表的产生式编程和模板元编程的出现，C++出现了发展历史上又一个新的高峰，这些新技术的出现以及和原有技术的融合，使C++已经成为当今主流程序设计语言中最复杂的一员。

    C++的设计原则

    o C++设计成静态类型、和C同样高效且可移植的多用途程序设计语言。
    o C++设计成直接的和广泛的支援多种程序设计风格（程序化程序设计、资料抽象化、面向对象程序设计、泛型程序设计）。
    o C++设计成给程序设计者更多的选择，即使可能导致程序设计者选择错误。
    o C++设计成尽可能与C兼容，籍此提供一个从C到C++的平滑过渡。
    o C++避免平台限定或没有普遍用途的特性。
    o C++不使用会带来额外开销的特性。
    o C++设计成无需复杂的程序设计环境。

    出于保证语言的简洁和运行高效等方面的考虑，C++的很多特性都是以库（如STL）或其他的形式提供的，而没有直接添加到语言本身里。关于此类话题，C++之父的《C++语言的设计和演化》 里做了详尽的陈述。

    C++程序员的数量

    Forrester最新的调查显示，C++、微软VisualBasic和Java是众多公司产品体系的首选语言。对100家公司的调查显示，C/C++、VisualBasic和Java在产品体系中的使用比例分别是59%、61%和66%。

    传统上认为，C++相对于目前一些新潮的语言，如Java、C#，优势在于程序的运行性能。这种观念并不完全。如果一个人深信这一点，那么说明他并没有充分了解和理解C++和那个某某语言。同时，持有这种观念的人，通常也是受到了某种误导（罪魁祸首当然就是那些财大气粗的公司）。对于这些公司而言，他们隐藏了C++同某某语言间的核心差别，而把现在多数程序员不太关心的差别，也就是性能，加以强化。因为随着cpu性能的快速提升，性能问题已不为人们所关心。这叫"李代桃僵"。很多涉世不深的程序员，也就相信了他们。于是，大公司们的阴谋也就得逞了。

    一般认为，使用Java或C#的开发成本比C++低。但是，如果你能够充分分析C++和这些语言的差别，会发现这句话的成立是有条件的。这个条件就是：软件规模和复杂度都比较小。如果不超过3万行有效代码（不包括生成器产生的代码），这句话基本上还能成立。否则，随着代码量和复杂度的增加，C++的优势将会越来越明显。
    造成这种差别的就是C++的软件工程性。在Java和C#大谈软件工程的时候，C++实际上已经悄悄地将软件工程性提升到一个前所未有的高度。这一点被多数人忽视，并且被大公司竭力掩盖。

    语言在软件工程上的好坏，依赖于语言的抽象能力。从面向过程到面向对象，语言的抽象能力有了一个质的飞跃。但在实践中，人们发现面向对象无法解决所有软件工程中的问题。于是，精英们逐步引入、并拓展泛型编程，解决更高层次的软件工程问题。（实际上，面向对象和泛型编程的起源都可以追溯到1967年，但由于泛型编程更抽象，所以应用远远落后于面向对象）。

C++语言的应用

    哪些程序是用C++写的：
    主流的3种操作系统Windows,Linux,Unix,内核都是用C语言和汇编写的，上层高级特性是用C++写的。
    《魔兽世界》等几乎所有的网络游戏，百度搜索引擎（Baidu.com），我们所用的大多数软件都是用C++写的（硬件也有很多用到C++的）。

    C++之父Bjarne Stroustrup列举的C++应用：
    Amazon.com：Software for large-scale e-commerce
    Apple: OS X is written in a mix of language, but a few important parts are C++. The two most interesting are
    AT&T:The largest US telecommunications provider.
    o provisioning systems
    o systems for rapid network recovery after failure
    Autodesk: A large number of major number of application in the CAD domain
    Ericsson:o server platform.
    o TDMA-CDMA HLR
    o GSM-TDMA-CDMA mobility gateway
    Google: web search engine, etc。
    HP: Here is a tiny fraction of HP's C++ apps:
    o C, C++, Fortran90 compilers, and linker for the new HP IA64 platform (these add to more than 1 million lines of C++ code).
    IBM: o OS/400.
    o K42: a high performance, open source, general-purpose operating system kernel for cache-coherent multiprocessors.
    Intel:o Vtune performace analysis software
    o compilers and optimizers
    o lots of chip design and manufacturing software
    JPL (Jet Propulsion Lab, NASA): Mars rover autonomous driving system (incl. scene analysis and route planning). C++ on Mars! Also lots of supporting software "on the ground" (i.e. Earth).
    Microsoft:o Windows XP
    o Windows NT (NT4 and 2000)
    o Windows 9x (95, 98, Me)
    o Microsoft Office (Word, Excel, Access, PowerPoint, Outlook)
    o Internet Explorer (including Outlook Express)
    o Visual Studio
    o SQL
    Mozilla: Firefox browser and Thunderbird mail client (open source)
    MySQL: MySQL Server (about 250,000 lines of C++) and MySQL Cluster. Arguably the world's most popular open source database
    Nokia: o Mobile Communications radio-station/internet bridges: FlexiGGSN (Gateway GPRS Support Node) and FlexiSGSN (Server GPRS Support Node).
    o MSC/HLR
    Sun: o The HotSpot Java Virtual Machine is written in C++
    Symbian OS: rationale: "[...] using C++ for all system code, from the kernel upwards." This is one of the most widespread OS's for cellular phones
    KDE from linux is written in C++.
    telephone systems: I think it would be almost easier to list the systems which aren't written in C++

 C++编程技巧

    　一、使用new和delete进行动态内存分配和释放
    　　运算符new和delete是C++新增的运算符，提供了存储的动态分配和释放功能。它的作用相当于C语言的函数malloc（）和free（），但是性能更为优越。使用new较之使用malloc（）有以下的几个优点：
    　　（1）new自动计算要分配类型的大小，不使用sizeof运算符，比较省事，可以避免错误。
    　　（2）自动地返回正确的指针类型，不用进行强制指针类型转换。
    　　（3）可以用new对分配的对象进行初始化。
    　　使用例子：
    　　（1）int* p；
    　　　　p=new int[10]； //分配一个含有10个整数的整形数组
    　　　　delete[] p； //删除这个数组
    　　（2）int* p；
    　　　　p=new int (100)；//动态分配一个整数并初始化
    　　二、使用inline内连函数替代宏调用
    　　对于频繁使用的函数，C语言建议使用宏调用代替函数调用以加快代码执行，减少调用开销。但是宏调用有许多的弊端，可能引起不期望的副作用。例如宏：#define abs（a） （（a）<0?（-a）：（a））， 当使用abs（i++）时，这个宏就会出错。
    　　所以在C++中应该使用inline内连函数替代宏调用，这样既可达到宏调用的目的，又避免了宏调用的弊端。
    　　使用内连函数只须把inline关键字放在函数返回类型的前面。例如：
    inline int Add(int a，int b);//声明Add（）为内连函数
    　　这样编译器在遇到Add()函数时，就不再进行函数调用，而是直接嵌入函数代码以加快程序的执行。
    　　三、使用函数重载
    　　在C语言中，两个函数的名称不能相同，否则会导致编译错误。而在C++中，函数名相同而参数不同的两个函数被解释为重载。例如：
    void PutHz(char* str);//在当前位置输出汉字
    void PutHz(int x,int y,char * str);//在x，y处输出汉字
    　　使用函数重载可以帮助程序员处理更多的复杂问题，避免了使用诸如intabs()、fabs()、dabs()等繁杂的函数名称；同时在大型程序中，使函数名易于管理和使用，而不必绞尽脑汁地去处理函数名。
    　　四、使用引用（reference）代替指针进行参数传递
    　　在C语言中，如果一个函数需要修改用作参数的变量值的时候 ，参数应该声明为指针类型。例如：
    　　　void Add(int *a)
    {
    *a++;
    }
    调用时则使用 Add(&x)//其中x为int或可以转化为int的类型，如unsigned int, 但这时候编译器通过回给出warning
    　　对于复杂的程序，使用指针容易出错，程序也难以读懂。在C++中，对于上述情况 可以使用引用来代替指针，使程序更加清晰易懂。引用就是对变量取的一个别名，对引用进行操作，这就相当于对原有变量进行操作。例如使用引用的函数定义为：
    　　void Add(int& a){a++;}//a为一个整数的引用
    调用时使用 Add(x)//其中x为int。
    　　这个函数与使用指针的上一个函数的功能是一样的，然而代码却更为简洁和清晰易懂。
    五、使用缺省参数
    　　在C++中函数可以使用缺省参数，例如：
    void PutHzxy(char *str,int x=-1, int y=-1)
    {
    if(x==-1)
    x=wherex();
    if(y==-1)
    x=wherex();
    moveto(x,y);
    PutHx(str);
    }
    　　可以有三种方式调用函数PutHzxy()，例如：
    PutHzxy("C++语言");//使用缺省参数在当前位置输出
    PutHzxy("C++语言",10,10);//没有使用缺省参数
    PutHzxy("C++语言",10);//对y使用缺省参数，指定x的位置

    　　通常的情况下，一个函数应该具有尽可能大的灵活性。使用缺省参数为程序员处理更大的复杂性和灵活性问题提供了有效的方法，所以在C++的代码中都大量地使用了缺省参数。
    　　需要说明的是，所有的缺省参数必须出现在不缺省参数的右边。亦即，一旦开始定义缺省参数，就不可再说明非缺省的参数。
    　　例如：　
    void PutHzxy(char*str,int x=-1,int y=-1)//正确
    void PutHzxy(int x=-1,int y=-1,char*str)//错误

    六、使用STL
    STL（Standard Template Library，标准模板库), STL的代码从广义上讲分为三类：algorithm（算法）、container（容器）和iterator（迭代器），并包括一些工具类如auto_ptr。几乎所有的代码都采用了模板类和模版函数的方式，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。

    #include<vector>// 包含相关的头文件/
    typedef std::vector<int> intvector;//使用typedef 使代码看起来更简洁

    int main()
    {
    intvector vi;
    for(int i=0;i<10,i++)
    vi.push_back(i);//使用push_back添加元素
    for(int i=0;i<vi.size();i++)
    std::cout<<vi<<" ";//[]操作符被重载，使得我们可以像访问数组一样访问vector中的元素
    }