提高指针精确度算法

㈠ Windows鼠标属性里“提高指针精确度”的功能是怎么工作的

首先，这个功能的描述有错误，开启这个功能之后，你的鼠标移动速度和鼠标指针移动速度不再是同时运动，而是加速度运动。

对于一般电脑用户来说，这个功能可能适合长距离的鼠标移动。但对于需要精准操作（游戏，制图）的电脑用户来说，就会非常影响。

以下是开启windows鼠标属性“提高指针精准度”的步骤。

1、进入 控制面板所有控制面板项轻松访问中心。

㈡ 作为程序员提高编程能力的几个基础算法

一：快速排序算法

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序n个项目要Ο(nlogn)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(nlogn)算法更快，因为它的内部循环（innerloop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divideandconquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

算法步骤：

1从数列中挑出一个元素，称为“基准”（pivot），

2重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

3递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

二：堆排序算法

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

堆排序的平均时间复杂度为Ο(nlogn) 。

创建一个堆H[0..n-1]

把堆首（最大值）和堆尾互换

3.把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置

4.重复步骤2，直到堆的尺寸为1

三：归并排序

归并排序（Mergesort，台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（DivideandConquer）的一个非常典型的应用。

1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

2.设定两个指针，最初位置分别为两个已经排序序列的起始位置

3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

4.重复步骤3直到某一指针达到序列尾

5.将另一序列剩下的所有元素直接复制到合并序列尾

四：二分查找算法

二分查找算法是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。折半搜索每次把搜索区域减少一半，时间复杂度为Ο(logn) 。

五：BFPRT(线性查找算法)

BFPRT算法解决的问题十分经典，即从某n个元素的序列中选出第k大（第k小）的元素，通过巧妙的分析，BFPRT可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相似，当然，为使得算法在最坏情况下，依然能达到o(n)的时间复杂度，五位算法作者做了精妙的处理。

1.将n个元素每5个一组，分成n/5(上界)组。

2.取出每一组的中位数，任意排序方法，比如插入排序。

3.递归的调用selection算法查找上一步中所有中位数的中位数，设为x，偶数个中位数的情况下设定为选取中间小的一个。

4.用x来分割数组，设小于等于x的个数为k，大于x的个数即为n-k。

5.若i==k，返回x；若i<k，在小于x的元素中递归查找第i小的元素；若i>k，在大于x的元素中递归查找第i-k小的元素。

终止条件：n=1时，返回的即是i小元素。

六：DFS（深度优先搜索）

深度优先搜索算法（Depth-First-Search），是搜索算法的一种。它沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。DFS属于盲目搜索。

深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。

深度优先遍历图算法步骤：

1.访问顶点v；

2.依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；

3.若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。

上述描述可能比较抽象，举个实例：

DFS在访问图中某一起始顶点v后，由v出发，访问它的任一邻接顶点w1；再从w1出发，访问与w1邻接但还没有访问过的顶点w2；然后再从w2出发，进行类似的访问，…如此进行下去，直至到达所有的邻接顶点都被访问过的顶点u为止。

接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。

七：BFS(广度优先搜索)

广度优先搜索算法（Breadth-First-Search），是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。

BFS同样属于盲目搜索。一般用队列数据结构来辅助实现BFS算法。

1.首先将根节点放入队列中。

2.从队列中取出第一个节点，并检验它是否为目标。

如果找到目标，则结束搜寻并回传结果。

否则将它所有尚未检验过的直接子节点加入队列中。

3.若队列为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。

4.重复步骤2。

八：Dijkstra算法

戴克斯特拉算法（Dijkstra’salgorithm）是由荷兰计算机科学家艾兹赫尔·戴克斯特拉提出。迪科斯彻算法使用了广度优先搜索解决非负权有向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

该算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。我们以V表示G中所有顶点的集合。每一个图中的边，都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径相连。我们以E表示G中所有边的集合，而边的权重则由权重函数w:E→[0,∞]定义。因此，w(u,v)就是从顶点u到顶点v的非负权重（weight）。边的权重可以想象成两个顶点之间的距离。任两点间路径的权重，就是该路径上所有边的权重总和。已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最低权重路径(例如，最短路径)。这个算法也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径。对于不含负权的有向图，Dijkstra算法是目前已知的最快的单源最短路径算法。

1.初始时令S=,T=，T中顶点对应的距离值

若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值

若不存在<V0,Vi>，d(V0,Vi)为∞

2.从T中选取一个其距离值为最小的顶点W且不在S中，加入S

3.对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值

重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止

九：动态规划算法

动态规划（Dynamicprogramming）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

关于动态规划最经典的问题当属背包问题。

1.最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。

2.子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

十：朴素贝叶斯分类算法

朴素贝叶斯分类算法是一种基于贝叶斯定理的简单概率分类算法。贝叶斯分类的基础是概率推理，就是在各种条件的存在不确定，仅知其出现概率的情况下，如何完成推理和决策任务。概率推理是与确定性推理相对应的。而朴素贝叶斯分类器是基于独立假设的，即假设样本每个特征与其他特征都不相关。

朴素贝叶斯分类器依靠精确的自然概率模型，在有监督学习的样本集中能获取得非常好的分类效果。在许多实际应用中，朴素贝叶斯模型参数估计使用最大似然估计方法，换言朴素贝叶斯模型能工作并没有用到贝叶斯概率或者任何贝叶斯模型。

尽管是带着这些朴素思想和过于简单化的假设，但朴素贝叶斯分类器在很多复杂的现实情形中仍能够取得相当好的效果。

通过掌握以上算法，能够帮你迅速提高编程能力，成为一名优秀的程序员。

㈢ 衡量算法效率的方法与准则

算法效率与分析
数据结构作为程序设计的基础，其对算法效率的影响必然是不可忽视的。本文就如何合理选择数据结构来优化算法这一问题，对选择数据结构的原则和方法进行了一些探讨。首先对数据逻辑结构的重要性进行了分析，提出了选择逻辑结构的两个基本原则；接着又比较了顺序和链式两种存储结构的优点和缺点，并讨论了选择数据存储结构的方法；最后本文从选择数据结构的的另一角度出发，进一步探讨了如何将多种数据结构进行结合的方法。在讨论方法的同时，本文还结合实际，选用了一些较具有代表性的信息学竞赛试题举例进行了分析
【正文】一、引论
“数据结构＋算法＝程序”，这就说明程序设计的实质就是对确定的问题选择一种合适的数据结构，加上设计一种好的算法。由此可见，数据结构在程序设计中有着十分重要的地位。
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。因为这其中的“关系”，指的是数据元素之间的逻辑关系，因此数据结构又称为数据的逻辑结构。而相对于逻辑结构这个比较抽象的概念，我们将数据结构在计算机中的表示又称为数据的存储结构。
建立问题的数学模型，进而设计问题的算法，直至编出程序并进行调试通过，这就是我们解决信息学问题的一般步骤。我们要建立问题的数学模型，必须首先找出问题中各对象之间的关系，也就是确定所使用的逻辑结构；同时，设计算法和程序实现的过程，必须确定如何实现对各个对象的操作，而操作的方法是决定于数据所采用的存储结构的。因此，数据逻辑结构和存储结构的好坏，将直接影响到程序的效率。

二、选择合理的逻辑结构

在程序设计中，逻辑结构的选用就是要分析题目中的数据元素之间的关系，并根据这些特定关系来选用合适的逻辑结构以实现对问题的数学描述，进一步解决问题。逻辑结构实际上是用数学的方法来描述问题中所涉及的操作对象及对象之间的关系，将操作对象抽象为数学元素，将对象之间的复杂关系用数学语言描述出来。
根据数据元素之间关系的不同特性，通常有以下四种基本逻辑结构：集合、线性结构、树形结构、图状（网状）结构。这四种结构中，除了集合中的数据元素之间只有“同属于一个集合”的关系外，其它三种结构数据元素之间分别为“一对一”、“一对多”、“多对多”的关系。
因此，在选择逻辑结构之前，我们应首先把题目中的操作对象和对象之间的关系分析清楚，然后再根据这些关系的特点来合理的选用逻辑结构。尤其是在某些复杂的问题中，数据之间的关系相当复杂，且选用不同逻辑结构都可以解决这一问题，但选用不同逻辑结构实现的算法效率大不一样。
对于这一类问题，我们应采用怎样的标准对逻辑结构进行选择呢？
下文将探讨选择合理逻辑结构应充分考虑的两个因素。

一、 充分利用“可直接使用”的信息。
首先，我们这里所讲的“信息”，指的是元素与元素之间的关系。
对于待处理的信息，大致可分为“可直接使用”和“不可直接使用”两类。对于“可直接使用”的信息，我们使用时十分方便，只需直接拿来就可以了。而对于“不可直接使用”的这一类，我们也可以通过某些间接的方式，使之成为可以使用的信息，但其中转化的过程显然是比较浪费时间的。
由此可见，我们所需要的是尽量多的“可直接使用”的信息。这样的信息越多，算法的效率就会越高。
对于不同的逻辑结构，其包含的信息是不同的，算法对信息的利用也会出现不同的复杂程度。因此，要使算法能够充分利用“可直接使用”的信息，而避免算法在信息由“不可直接使用”向“可直接使用”的转化过程中浪费过多的时间，我们必然需要采用一种合理的逻辑结构，使其包含更多“可直接使用”的信息。
〖问题一〗 IOI99的《隐藏的码字》。
〖问题描述〗
问题中给出了一些码字和一个文本，要求编程找出文本中包含这些码字的所有项目，并将找出的项目组成一个最优的“答案”，使得答案中各项目所包含的码字长度总和最大。每一个项目包括一个码字，以及该码字在文本中的一个覆盖序列（如’abcadc’就是码字’abac’的一个覆盖序列），并且覆盖序列的长度不超过1000。同时，“答案”要求其中每个项目的覆盖序列互相没有重叠。
〖问题分析〗
对于此题，一种较容易得出的基本算法是：对覆盖序列在文本中的终止位置进行循环，再判断包含了哪些码字，找出所有项目，并最后使用动态规划的方法将项目组成最优的“答案”。
算法的其它方面我们暂且不做考虑，而先对问题所采用的逻辑结构进行选择。
如果我们采用线性的逻辑结构（如循环队列），那么我们在判断是否包含某个码字t时，所用的方法为：初始时用指针p指向终止位置，接着通过p的不断前移，依次找出码字t从尾到头的各个字母。例如码字为“ABDCAB”，而文本图1-1，终止位置为最右边的箭头符号，每个箭头代表依次找到的码字的各个字母。
指针p的移动方向
A B D C A B

C D A C B D C A D C D B A D C C B A D

图1-1

由于题目规定码字的覆盖序列长度不超过1000，所以进行这样的一次是否包含的判断，其复杂度为O(1000)。
由于码字t中相邻两字母在文本中的位置，并非只有相邻(如图1-1中的’D’和’C’)这一种关系，中间还可能间隔了许多的字母(如图1-1中’C’和’A’就间隔了2个字母)，而线性结构中拥有的信息，仅仅只存在于相邻的两元素之间。通过这样简单的信息来寻找码字的某一个字母，其效率显然不高。
如果我们建立一个有向图，其中顶点i(即文本的第i位)用52条弧分别连接’a’..’z’,’A’..’Z’这52个字母在i位以前最后出现的位置（如图1-2的连接方式），我们要寻找码字中某个字母的前一个字母，就可以直接利用已连接的边，而不需用枚举的方法。我们也可以把问题看为：从有向图的一个顶点出发，寻找一条长度为length(t)-1的路径，并且路径中经过的顶点，按照码字t中的字母有序。

C D A C B D C A D C D B A D C C B A D

图1-2
通过计算，用图进行记录在空间上完全可以承受(记录1000个点×52条弧×4字节的长整型=200k左右)。在时间上，由于可以充分利用第i位和第i+1位弧的连接方式变化不大这一点(如图1-2所示，第i位和第i+1位只有一条弧的指向发生了变化，即第i+1位将其中一条弧指向了第i位)，所以要对图中的弧进行记录，只需对弧的指向进行整体赋值，并改变其中的某一条弧即可。
因此，我们通过采用图的逻辑结构，使得寻找字母的效率大大提高，其判断的复杂度为O(length(t))，最坏为O(100)，比原来方法的判断效率提高了10倍。
（附程序codes.pas）

对于这个例子，虽然用线性的数据结构也可以解决，但由于判断的特殊性，每次需要的信息并不能从相邻的元素中找到，而线性结构中只有相邻元素之间存在关系的这一点，就成为了一个很明显的缺点。因此，问题一线性结构中的信息，就属于“不可直接使用”的信息。相对而言，图的结构就正好满足了我们的需要，将所有可能产生关系的点都用弧连接起来，使我们可以利用弧的关系，高效地进行判断寻找的过程。虽然图的结构更加复杂，但却将“不可直接使用”的信息，转化成为了“可直接使用”的信息，算法效率的提高，自然在情理之中。。
二、 不记录“无用”信息。
从问题一中我们看到，由于图结构的信息量大，所以其中的信息基本上都是“可用”的。但是，这并不表示我们就一定要使用图的结构。在某些情况下，图结构中的“可用”信息，是有些多余的。
信息都“可用”自然是好事，但倘若其中“无用”（不需要）的信息太多，就只会增加我们思考分析和处理问题时的复杂程度，反而不利于我们解决问题了。
〖问题二〗 湖南省1997年组队赛的《乘船问题》
〖问题描述〗
有N个人需要乘船，而每船最多只能载两人，且必须同名或同姓。求最少需要多少条船。
〖问题分析〗
看到这道题，很多人都会想到图的数据结构：将N个人看作无向图的N个点，凡同名或同姓的人之间都连上边。
要满足用船最少的条件，就是需要尽量多的两人共乘一条船，表现在图中就是要用最少的边完成对所有顶点的覆盖。这就正好对应了图论的典型问题：求最小边的覆盖。所用的算法为“求任意图最大匹配”的算法。
使用“求任意图最大匹配”的算法比较复杂(要用到扩展交错树，对花的收缩等等)，效率也不是很高。因此，我们必须寻找一个更简单高效的方法。
首先，由于图中任两个连通分量都是相对独立的，也就是说任一条匹配边的两顶点，都只属于同一个连通分量。因此，我们可以对每个连通分量分别进行处理，而不会影响最终的结果。
同时，我们还可以对需要船只s的下限进行估计：
对于一个包含Pi个顶点的连通分量，其最小覆盖边数显然为[Pi/2]。若图中共有L个连通分量，则s=∑[Pi/2](1<=i<=L)。
然后，我们通过多次尝试，可得出一个猜想：
实际需要的覆盖边数完全等于我们求出的下限∑[Pi/2](1<=i<=L)。
要用图的结构对上述猜想进行证明，可参照以下两步进行：
1． 连通分量中若不存在度为1的点，就必然存在回路。
2． 从图中删去度为1的点及其相邻的点，或删去回路中的任何一边，连通分量依然连通，即连通分量必然存在非桥边。
由于图的方法不是这里的重点，所以具体证明不做详述。而由采用图的数据结构得出的算法为：每次输出一条非桥的边，并从图中将边的两顶点删去。此算法的时间复杂度为O(n3)。（寻找一条非桥边的复杂度为O(n2)，寻找覆盖边操作的复杂度为O(n)）
由于受到图结构的限制，时间复杂度已经无法降低，所以如果我们要继续对算法进行优化，只有考虑使用另一种逻辑结构。这里，我想到了使用二叉树的结构，具体说就是将图中的连通分量都转化为二叉树，用二叉树来解决问题。
首先，我们以连通分量中任一个顶点作为树根，然后我们来确定建树的方法。
1． 找出与根结点i同姓的点j（j不在二叉树中）作为i的左儿子，再以j为树根建立子树。
2． 找出与根结点i同名的点k（k不在二叉树中）作为i的右儿子，再以k为树根建立子树。
如图2-1-1中的连通分量，我们通过上面的建树方法，可以使其成为图2-1-2中的二叉树的结构(以结点1为根)。（两点间用实线表示同姓，虚线表示同名）

图2-1-2

图2-1-1
接着，我就来证明这棵树一定包含了连通分量中的所有顶点。
【引理2.1】
若二叉树T中包含了某个结点p，那么连通分量中所有与p同姓的点一定都在T中。
证明：
为了论证的方便，我们约定：s表示与p同姓的顶点集合；lc[p,0]表示结点p，lc[p,i](i>0)表示lc[p,i-1]的左儿子，显然lc[p,i]与p是同姓的。
假设存在某个点q，满足qs且qT。由于s是有限集合，因而必然存在某个lc[p,k]无左儿子。则我们可以令lc[p,k+1]=q，所以qT，与假设qT相矛盾。
所以假设不成立，原命题得证。

由引理2.1的证明方法，我们同理可证引理2.2。
【引理2.2】
若二叉树T中包含了某个结点p，那么连通分量中所有与p同名的点一定都在T中。

有了上面的两个引理，我们就不难得出下面的定理了。
【定理一】
以连通分量中的任一点p作为根结点的二叉树，必然能够包含连通分量中的所有顶点。
证明：
由引理2.1和引理2.2，所有与p同姓或同名的点都一定在二叉树中，即连通分量中所有与p有边相连的点都在二叉树中。由连通分量中任两点间都存在路径的特性，该连通分量中的所有点都在二叉树中。

在证明二叉树中包含了连通分量的所有顶点后，我们接着就需要证明我们的猜想，也就是下面的定理：
【定理二】包含m个结点的二叉树Tm，只需要船的数量为boat[m]=[m/2](mN)。
证明：
(i) 当m=1,m=2,m=3时命题显然成立。

图2-2-1

图2-2-2

图2-2-3
(ii) 假设当m<k(k>3)时命题成立，那么当m=k时，我们首先从树中找到一个层次最深的结点，并假设这个结点的父亲为p。那么，此时有且只有以下三种情况（结点中带有阴影的是p结点）：
(1) 如图2-2-1，p只有一个儿子。此时删去p和p唯一的儿子，Tk就成为了Tk-2，则boat[k]=boat[k-2]+1=[(k-2)/2]+1=[k/2]。
(2) 如图2-2-2，p有两个儿子，并且p是其父亲的左儿子。此时可删去p和p的右儿子，并可将p的左儿子放到p的位置上。同样地，Tk成为了Tk-2，boat[k]=boat[k-2]+1=[k/2]。
(3) 如图2-2-3，p有两个儿子，并且p是其父亲的右儿子。此时可删去p和p的左儿子，并可将p的右儿子放到p的位置上。情况与(2)十分相似，易得此时得boat[k]=boat[k-2]+1=[k/2]。
综合(1)、(2)、(3)，当m=k时，boat[k]=[k/2]。
最后，综合(i)、(ii)，对于一切mN，boat[m]=[m/2]。

由上述证明，我们将问题中数据的图结构转化为树结构后，可以得出求一棵二叉树的乘船方案的算法：
proc try(father:integer;var root:integer;var rest:byte);
{输出root为树根的子树的乘船方案，father=0表示root是其父亲的左儿子，
father=1表示root是其父亲的右儿子，rest表示输出子树的乘船方案后，
是否还剩下一个根结点未乘船}
begin
visit[root]:=true; {标记root已访问}
找到一个与root同姓且未访问的结点j;
if j<>n+1 then try(0,j,lrest);
找到一个与root同姓且未访问的结点k;
if k<>n+1 then try(1,k,rrest);
if (lrest=1) xor (rrest=1) then begin {判断root是否只有一个儿子，情况一}
if lrest=1 then print(lrest,root) else print(rrest,root);
rest:=0;
end
else if (lrest=1) and (rrest=1) then begin {判断root是否有两个儿子}
if father=0 then begin
print(rrest,root);root:=j; {情况二}
end
else begin
print(lrest,root);root:=k; {情况三}
end;
rest:=1;
end
else rest:=1;
end;

这只是输出一棵二叉树的乘船方案的算法，要输出所有人的乘船方案，我们还需再加一层循环，用于寻找各棵二叉树的根结点，但由于每个点都只会访问一次，寻找其左右儿子各需进行一次循环，所以算法的时间复杂度为O(n2)。（附程序boat.pas）

最后，我们对两种结构得出不同时间复杂度算法的原因进行分析。其中最关键的一点就是因为二叉树虽然结构相对较简单，但已经包含了几乎全部都“有用”的信息。由我们寻找乘船方案的算法可知，二叉树中的所有边不仅都发挥了作用，而且没有重复的使用，可见信息的利用率也是相当之高的。
既然采用树结构已经足够，图结构中的一些信息就显然就成为了“无用”的信息。这些多余的“无用”信息，使我们在分析问题时难于发现规律，也很难找到高效的算法进行解决。这正如迷宫中的墙一样，越多越难走。“无用”的信息，只会干扰问题的规律性，使我们更难找出解决问题的方法。

小结
我们对数据的逻辑结构进行选择，是构造数学模型一大关键，而算法又是用来解决数学模型的。要使算法效率高，首先必须选好数据的逻辑结构。上面已经提出了选择逻辑结构的两个条件（思考方向），总之目的是提高信息的利用效果。利用“可直接使用”的信息，由于中间不需其它操作，利用的效率自然很高；不不记录“无用”的信息，就会使我们更加专心地研究分析“有用”的信息，对信息的使用也必然会更加优化。
总之，在解决问题的过程中，选择合理的逻辑结构是相当重要的环
三、 选择合理的存储结构
数据的存储结构，分为顺序存储结构和链式存储结构。顺序存储结构的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系；链式存储结构则是借助指示元素存储地址的指针表示数据元素之间的逻辑关系。
因为两种存储结构的不同，导致这两种存储结构在具体使用时也分别存在着优点和缺点。
这里有一个较简单的例子：我们需要记录一个n×n的矩阵，矩阵中包含的非0元素为m个。
此时，我们若采用顺序存储结构，就会使用一个n×n的二维数组，将所有数据元素全部记录下来；若采用链式存储结构，则需要使用一个包含m个结点的链表，记录所有非0的m个数据元素。由这样两种不同的记录方式，我们可以通过对数据的不同操作来分析它们的优点和缺点。
1． 随机访问矩阵中任意元素。由于顺序结构在物理位置上是相邻的，所以可以很容易地获得任意元素的存储地址，其复杂度为O(1)；对于链式结构，由于不具备物理位置相邻的特点，所以首先必须对整个链表进行一次遍历，寻找需进行访问的元素的存储地址，其复杂度为O(m)。此时使用顺序结构显然效率更高。
2． 对所有数据进行遍历。两种存储结构对于这种操作的复杂度是显而易见的，顺序结构的复杂度为O(n2)，链式结构为O(m)。由于在一般情况下m要远小于n2，所以此时链式结构的效率要高上许多。
除上述两种操作外，对于其它的操作，这两种结构都不存在很明显的优点和缺点，如对链表进行删除或插入操作，在顺序结构中可表示为改变相应位置的数据元素。
既然两种存储结构对于不同的操作，其效率存在较大的差异，那么我们在确定存储结构时，必须仔细分析算法中操作的需要，合理地选择一种能够“扬长避短”的存储结构。

一、合理采用顺序存储结构。
我们在平常做题时，大多都是使用顺序存储结构对数据进行存储。究其原因，一方面是出于顺序结构操作方便的考虑，另一方面是在程序实现的过程中，使用顺序结构相对于链式结构更便于对程序进行调试和查找错误。因此，大多数人习惯上认为，能够使用顺序结构进行存储的问题，最“好”采用顺序存储结构。
其实，这个所谓的“好”只是一个相对的标准，是建立在以下两个前提条件之下的：
1． 链式结构存储的结点与顺序结构存储的结点数目相差不大。这种情况下，由于存储的结点数目比较接近，使用链式结构完全不能体现出记录结点少的优点，并且可能会由于指针操作较慢而降低算法的效率。更有甚者，由于指针自身占用的空间较大，且结点数目较多，因而算法对空间的要求可能根本无法得到满足。
2． 并非算法效率的瓶颈所在。由于不是算法最费时间的地方，这里是否进行改进，显然是不会对整个算法构成太大影响的，若使用链式结构反而会显得操作过于繁琐。

二、必要时采用链式存储结构。
上面我对使用顺序存储结构的条件进行了分析，最后就只剩下何时应该采用链式存储结构的问题了。
由于链式结构中指针操作确实较繁琐，并且速度也较慢，调试也不方便，因而大家一般都不太愿意用链式的存储结构。但是，这只是一般的观点，当链式结构确实对算法有很大改进时，我们还是不得不进行考虑的。
〖问题三〗 IOI99的《地下城市》。
〖问题描述〗
已知一个城市的地图，但未给出你的初始位置。你需要通过一系列的移动和探索，以确定初始时所在的位置。题目的限制是：
1． 不能移动到有墙的方格。
2． 只能探索当前所在位置四个方向上的相邻方格。
在这两个限制条件下，要求我们的探索次数（不包括移动）尽可能的少。
〖问题分析〗
由于存储结构要由算法的需要确定，因此我们首先来确定问题的算法。
经过对问题的分析，我们得出解题的基本思想：先假设所有无墙的方格都可能是初始位置，再通过探索一步步地缩小初始位置的范围，最终得到真正的初始位置。同时，为提高算法效率，我们还用到了分治的思想，使我们每一次探索都尽量多的缩小初始位置的范围(使程序尽量减少对运气的依赖)。
接着，我们来确定此题的存储结构。
由于这道题的地图是一个二维的矩阵，所以一般来讲，采用顺序存储结构理所当然。但是，顺序存储结构在这道题中暴露了很大的缺点。我们所进行的最多的操作，一是对初始位置的范围进行筛选，二是判断要选择哪个位置进行探索。而这两种操作，所需要用到的数据，只是庞大地图中很少的一部分。如果采用顺序存储结构(如图3-1中阴影部分表示已标记)，无论你需要用到多少数据，始终都要完全的遍历整个地图。

4
3
2
1
1 2 3 4
图3-1

head

图3-2
然而，如果我们采用的是链式存储结构(如图3-2的链表)，那么我们需要多少数据，就只会遍历多少数据，这样不仅充分发挥了链式存储结构的优点，而且由于不需单独对某一个数据进行提取，每次都是对所有数据进行判断，从而避免了链式结构的最大缺点。
我们使用链式存储结构，虽然没有降低问题的时间复杂度(链式存储结构在最坏情况下的存储量与顺序存储结构的存储量几乎相同)，但由于体现了前文所述选择存储结构时扬长避短的原则，因而算法的效率也大为提高。（程序对不同数据的运行时间见表3-3）
测试数据编号 使用顺序存储结构的程序 使用链式存储结构的程序
1 0.06s 0.02s
2 1.73s 0.07s
3 1.14s 0.06s
4 3.86s 0.14s
5 32.84s 0.21s
6 141.16s 0.23s
7 0.91s 0.12s
8 6.92s 0.29s
9 6.10s 0.23s
10 17.41s 0.20s

表3-3
（附使用链式存储结构的程序under.pas）
我们选择链式的存储结构，虽然操作上可能稍复杂一些，但由于改进了算法的瓶颈，算法的效率自然也今非昔比。由此可见，必要时选择链式结构这一方法，其效果是不容忽视的。
小结
合理选择逻辑结构，由于牵涉建立数学模型的问题，可能大家都会比较注意。但是对存储结构的选择，由于不会对算法复杂度构成影响，所以比较容易忽视。那么，这种不能降低算法复杂度的方法是否需要重视呢？
大家都知道，剪枝作为一种常用的优化算法的方法，被广泛地使用，但剪枝同样是无法改变算法的复杂度的。因此，作用与剪枝相似的存储结构的合理选择，也是同样很值得重视的。
总之，我们在设计算法的过程中，必须充分考虑存储结构所带来的不同影响，选择最合理的存储结构。

四、 多种数据结构相结合

上文所探讨的，都是如何对数据结构进行选择，其中包含了逻辑结构的选择和存储结构的选择，是一种具有较大普遍性的算法优化方法。对于多数的问题，我们都可以通过选择一种合理的逻辑结构和存储结构以达到优化算法的目的。
但是，有些问题却往往不如人愿，要对这类问题的数据结构进行选择，常常会顾此失彼，有时甚至根本就不存在某一种合适的数据结构。此时，我们是无法选择出某一种合适的数据结构的，以上的方法就有些不太适用了。
为解决数据结构难以选择的问题，我们可以采用将多种数据结构进行结合的方法。通过多种数据结构相结合，达到取长补短的作用，使不同的数据结构在算法中发挥出各自的优势。
这只是我们将多种数据结构进行结合的总思想，具体如何进行结合，我们可以先看下面的例子。
我们可以采用映射的方法，将线性结构中的元素与堆中间的结点一一对应起来，若线性的数组中的元素发生变化，堆中相应的结点也接着变化，堆中的结点发生变化，数组中相应的元素也跟着变化。
将两种结构进行结合后，无论是第一步还是第二步，我们都不需对所有元素进行遍历，只需进行常数次复杂度为O(log2n)的堆化操作。这样，整个时间复杂度就成为了O(nlog2n)，算法效率无疑得到了很大提高。

五、 总结
我们平常使用数据结构，往往只将其作为建立模型和算法实现的工具，而没有考虑这种工具对程序效率所产生的影响。信息学问题随着难度的不断增大，对算法时空效率的要求也越来越高，而算法的时空效率，在很大程度上都受到了数据结构的制约。

㈣ 调高控制面板里的鼠标速度，还是调高鼠标DPi好

当然是调DPI好。鼠标的DPI是每英寸点数，也就是鼠标每移动一英寸指针在屏幕上移动的点数。比如400DPI的鼠标，他在移动一英寸的时候，屏幕上的指针可以移动400个点。这个是鼠标精准定位的点。
系统控制面板的鼠标速度是以插值算法计算的，比如当控制面板把速度调快（标准的是最中间的档位，就是6/11），那么鼠标移动实际只有1个点的距离，系统插值计算为两个点距离，就是跳过一个点移动，这样就移动更快，但是损失了精准的定位，调得越快定位越差（一倍是1个点当2个点，二倍就2个当4个，以此内推）。当速度调慢，把鼠标真实移动两个点移动的距离，只当成一个点距离，这样移动就变慢了。

你可以理解成这样，鼠标DPI移动是真实的定位，比如你要移动800个点的距离，DPI是真实定位了这800点的每个点。控制面板鼠标速度调快一倍，那么它只定位了400个点，它是跳着两个点当1个点移动的。反过来，控制面板调慢了，虽然你屏幕上的每一个点都能精准定位，但是却牺牲了你鼠标的定位。
即使你通过共同调节鼠标和控制面板速度，搭配出来同样的速度，在真实定位反应上都会有损失的。但是我们一般很多时候，并不需要鼠标精确的定位每个点，但是像有些游戏或作图之类的应用，对定位要求很高，这就需要对定位能力要求很高的鼠标了（很多鼠标本身芯片定位能力就差，或是芯片自身就是插值算法的）。

㈤ 机械表的一些顶级工艺

陀飞轮是瑞士钟表大师路易·宝玑先生在1795年发明的一种钟表调速装置。法文Tourbillon（故又称特比龙），有“漩涡”之意，是指装有“旋转擒纵调速机构”的机械表，陀飞轮机构，是为了校正地心引力对钟表机件造成的误差。陀飞轮表代表了机械表制造工艺中的最高水平，整个擒纵调速机构组合在一起并且能够转动，以一定的速度不断的旋转，使其把地心引力对机械表中“擒纵系统”的影响减至最低程度，提高走时精度。由于其独特的运行方式，已经把钟表的动感艺术美发挥到登峰造极的地步，历来被誉为“表中之王”。
陀飞轮的结构
陀飞轮的创意在于，将擒纵机构放在一个框架（Carriage）之内，使框架围 陀飞轮
绕轴心也就是摆轮的轴心做360度不停的旋转。这样，原本的擒纵机构是固定的，因而当表搁置位置变化的时候，擒纵机构不变，造成了擒纵零件受力不同而产生了误差；当擒纵机构360度不停的旋转起来的时候，会将零件的方位误差综合起来，互相抵消，从而消灭误差。目前陀飞轮一般是1分钟转360度，也是最理想的旋转速度。
陀飞轮的原理就是当钟表在垂直位置时补偿地心引力的作用。 换句话说，当一只钟表处于垂直位置时，由于来自地心引力的作用，它的调节控制器，即是其摆轮、游丝和擒纵器，会在每一下摆动时发生难以觉察的快慢变化。 如果把调节控制器装设在一个每分钟转动一周的“笼框”上，即可获得一系列的垂直位置。这样便可以使钟表走动时十分准确，并能够互补误差。 这个原理看来十分简单，但实施起来却是另外一回事。原因之一便是“笼框”和陀飞轮的重量不能超过0.3克或0.013盎司——相当于一片天鹅羽毛的重量或两片鹦鹉羽毛的重量。另一原因是，它由72个精细组件组成，而其中大部分为手工制作！
陀飞轮的技术演进
陀飞轮手表经过时间和技术的改进和革新主要可以分为以下三代： 1、第一代陀飞轮表（即第一种结构—Tourbillon）是在1795年由瑞士制表大师Abraham-Louis Breguet发明并制成的。其飞轮结构必须由“飞轮旋转框架”（Tourbillon’s Carriage）和“飞轮固定支架”（Tourbillon’s Bridge）不可或缺的两部分基本构件组成。在此组合中，“摆轮夹板”（Balance’s Bridge）必须随飞轮一起旋转。按照不同的组合方式，第一代飞轮表可以分为两类：同轴式（即摆轮的中心和飞轮的中心在同一轴心上）；偏心式（亦称非同轴式，即摆轮的中心和飞轮的中心不在同一轴心上）。 2、第二代飞行陀飞轮表（即第二种结构—Flying Tourbillon）是在1927年，德国制表大师Alferd Helwig制造成功没有“飞轮固定支架”的陀飞轮怀表，提高了此种表运转时的神秘感和动态艺术美。在此组合中“摆轮夹板”仍须随飞轮一起旋转，此第二代飞轮表同样有同轴式和偏心式两种类别。 3、第三代神奇陀飞轮表（即第三种结构—Mystery Tourbillon）则由东方的钟表大师—中国人矫大羽（Kiu Tai Yu）在1993年于香港的“天仪轩”首创发明并且亲手制造成功。它不但和第二代飞行陀飞轮表一样都取消了“飞轮固定支架”，而且奇迹般地把“飞轮旋转框架”也一同取消了（在第一代和第二代飞轮表中，此构件都是必不可少的）。另外，在这个全新的结构中还把第一代和第二代飞轮表中必须随飞轮一起旋转的“摆轮夹板”改变为不随飞轮一起转动，首次大大减轻了飞轮重量达一半以上，并且可以加大摆轮的直径以增强计时的稳定性，同时又提高了动感艺术表现的水平。在飞轮表制造历史中，矫大羽首次选用蓝宝石玻璃替代了原本用金属制造的“摆轮夹板”，之前此部件是附属于“飞轮旋转框架”中的。由于此表运转时显得更加神秘莫测，故在国际上也被称为“矫氏神奇陀飞轮”（Kiu’s Mystery Tourbillon）和“中国陀飞轮”（Chinese Tourbillon）。

万年历
卷曲在链盘之内的发条是用手工装上的。它缓缓地松开，通过齿轮拖动系统（由齿轮和小齿轮组成）把它的动力传送到擒纵装置上，（擒纵装置调节它的力度）并传送到游丝摆轮。游丝摆轮的功能是调节时间，它每秒钟振动6到8次。振动越有规律，表的精确度就越高。齿轮拖动系统连接在游丝摆轮上，它的功能是驱动表盘上的指针。根据这个基本的原则（大约需要90个零部件），可以改制成一整套不同样式、越来越复杂的机械表，可多达13种功能，包括万年历、月相等。一块"顶级复杂"的机械表由1400个零部件组成。
普通的手表是通过机械方式（机械表）或者简单的换算方式（电子表）来实现日历功能的。而“万年历”需要实现一个略为复杂的算法，要实现这个算法，普通的电子表控制芯片已经不能胜任，需要一块8位以上的芯片来完成这个工作。所以，真正有万年历功能的手表，基本是电子石英表，机械表不能做到真正的自动有万年历功能，还要人工操作。

日月星辰就不太清楚了

㈥ 求一个C#中使用高性能数组（使用指针）的实际应用

stackalloc 创建一个高性能的数组

stackalloc命令指示.NET运行库分配堆栈上一定量的内存。在调用它时，需要为它提供两条信息：
● 要存储的数据类型
● 需要存储的数据个数。
例如，分配足够的内存，以存储10个decimal数据，可以编写下面的代码：
decimal* pDecimals = stackalloc decimal [10];
注意，这个命令只是分配堆栈内存而已。它不会试图把内存初始化为任何默认值，这正好符合我们的目的。因为这是一个高性能的数组，给它不必要地初始化值会降低性能。
同样，要存储20个double数据，可以编写下面的代码：
double* pDoubles = stackalloc double [20];
虽然这行代码指定把变量的个数存储为一个常数，但它是在运行时计算的一个数字。所以可以把上面的示例写为：
int size;
size = 20; // or some other value calculated at run-time
double* pDoubles = stackalloc double [size];
从这些代码段中可以看出，stackalloc的语法有点不寻常。它的后面紧跟的是要存储的数据类型名(该数据类型必须是一个值类型)，其后是把需要的变量个数放在方括号中。分配的字节数是变量个数乘以sizeof(数据类型)。在这里，使用方括号表示这是一个数组。如果给20个double数据分配存储单元，就得到了一个有20个元素的double数组，最简单的数组类型可以是：逐个存储元素的内存块，如图7-6所示。

图 7-6
在图7-6中，显示了一个由stackalloc返回的指针，stackalloc总是返回分配数据类型的指针，它指向新分配内存块的顶部。要使用这个内存块，可以取消对返回指针的引用。例如，给20个double数据分配内存后，把第一个元素(数组中的元素0)设置为3.0，可以编写下面的代码：
double* pDoubles = stackalloc double [20];
*pDoubles = 3.0;
要访问数组的下一个元素，可以使用指针算法。如前所述，如果给一个指针加1，它的值就会增加其数据类型的字节数。在本例中，就会把指针指向下一个空闲存储单元。因此可以把数组的第二个元素(数组中元素号为1)设置为8.4：
double* pDoubles = stackalloc double [20];
*pDoubles = 3.0;
*(pDoubles+1) = 8.4;
同样，可以用表达式*(pDoubles+X)获得数组中下标为X的元素。
这样，就得到一种访问数组中元素的方式，但对于一般目的，使用这种语法过于复杂。C#为此定义了另一种语法。对指针应用方括号时，C#为方括号提供了一种非常明确的含义。如果变量p是任意指针类型，X是一个整数，表达式p[X]就被编译器解释为*(p+X)，这适用于所有的指针，不仅仅是用stackalloc初始化的指针。利用这个简捷的记号，就可以用一种非常方便的方式访问数组。实际上，访问基于堆栈的一维数组所使用的语法与访问基于堆的、由System.Array类表示的数组是一样的：
double *pDoubles = stackalloc double [20];
pDoubles[0] = 3.0; // pDoubles[0] is the same as *pDoubles
pDoubles[1] = 8.4; // pDoubles[1] is the same as *(pDoubles+1)

注意：
把数组的语法应用于指针并不是新东西。自从开发出C和C++语言以来，它们就是这两种语言的基础部分。实际上，C++开发人员会把这里用stackalloc获得的、基于堆栈的数组完全等同于传统的基于堆栈的C和C++数组。这个语法和指针与数组的链接方式是C语言在70年代后期流行起来的原因之一，也是指针的使用成为C和C++中一种大众化编程技巧的主要原因。
高性能的数组可以用与一般C#数组相同的方式访问，但需要强调其中的一个警告。在C#中，下面的代码会抛出一个异常：
double [] myDoubleArray = new double [20];
myDoubleArray[50] = 3.0;
抛出异常的原因很明显。使用越界的下标来访问数组：下标是50，但允许的最大值是19。但是，如果使用stackalloc声明了一个相同数组，对数组进行边界检查时，这个数组中没有包装任何对象，因此下面的代码不会抛出异常：
double* pDoubles = stackalloc double [20];
pDoubles[50] = 3.0;
在这段代码中，我们分配了足够的内存来存储20个double类型数据。接着把sizeof(double)存储单元的起始位置设置为该存储单元的起始位置加上50*sizeof(double)存储单元，来保存双精度值3.0。但这个存储单元超出了刚才为double分配的内存区域。谁也不知道这个地址上存储了什么数据。最好是只使用某个当前未使用的内存，但所重写的空间也有可能是堆栈上用于存储其他变量或某个正在执行的方法的返回地址。因此，使用指针获得高性能的同时，也会付出一些代价：需要确保自己知道在做什么，否则就会抛出非常古怪的运行时错误。
2. 示例QuickArray
下面用一个stackalloc示例QuickArray来结束关于指针的讨论。在这个示例中，程序仅要求用户提供为数组分配的元素数。然后代码使用stackalloc给long型数组分配一定的存储单元。这个数组的元素是从0开始的整数的平方，结果显示在控制台上：
using System;

namespace Wrox.ProCSharp.Chapter07
{
class MainEntryPoint
{
static unsafe void Main()
{
Console.Write("How big an array do you want? \n> ");
string userInput = Console.ReadLine();
uint size = uint.Parse(userInput);

long* pArray = stackalloc long [(int)size];
for (int i=0 ; i pArray = i*i;

for (int i=0 ; i Console.WriteLine("Element {0} = {1}", i, *(pArray+i));
}
}
}
运行这个示例，得到如下所示的结果：
QuickArray
How big an array do you want?
> 15
Element 0 = 0
Element 1 = 1
Element 2 = 4
Element 3 = 9
Element 4 = 16
Element 5 = 25
Element 6 = 36
Element 7 = 49
Element 8 = 64
Element 9 = 81
Element 10 = 100
Element 11 = 121
Element 12 = 144
Element 13 = 169
Element 14 = 196
7.4 小结
要想成为真正优秀的C#程序员，必须牢固掌握存储单元和垃圾收集的工作原理。本文描述了CLR管理以及在堆和堆栈上分配内存的方式，讨论了如何编写正确释放未托管资源的类，并介绍如何在C#中使用指针，这些都是很难理解的高级主题，初学者常常不能正确实现。

本文摘至清华大学出版社出版的Wrox红皮书《C＃高级编程（第3版）》，

㈦ 什么是提高指针精确度.

提高指针精确度就是鼠标加速度

指针是对图案视觉的设置,指针选项则是对操作方面的设置,拖动“选择指针移动速度”上的滑块,就能调节鼠标指针在屏幕上移动的速度。建议在“提高指针精确度”旁边的方框打上×号,这样有利于鼠标更精确地定位。

㈧ 什么是高精度

高精度算法在一般的科学计算中,会经常算到小数点后几百位或者更多,当然也可能是几千亿几百亿的大数字.
一般这类数字我们统称为高精度数,高精度算法是用计算机对于超大数据的一种模拟加,减,乘,除,乘方,阶乘,开方等运算.
譬如一个很大的数字N >= 10^ 100, 很显然这样的数字无法在计算机中正常存储.
于是, 我们想到了办法,将这个数字拆开,拆成一位一位的 或者是四位四位的存储到一个数组中, 用一个数组去表示一个数字.这样这个数字就被称谓是高精度数.
对于高精度数,也要像平常数一样做加减乘除以及乘方的运算,于是就有了高精度算法:
下面提供了Pascal的高精度加法, 高精度乘以单精度, 高精度乘以高精度的代码, 其他版本请各位大牛添加进来吧!
Pascal代码如下(非完整); k为预定进制，加大进制以提高速度。
Procere HPule(a, b: Arr; Var c:Arr); //高精度加法
Var
i: Integer;
Begin
FillChar(c, SizeOf(c), 0);
For i:= 1 To Maxn-1 Do Begin
c［i］:= c［i］ + a［i］ + b［i］;
c［i + 1］ := c［i］ Div k;
c［i］ := c［i］ Mod k；
End;
End;
Procere HPule(a: Arr; b:Integer; Var c:Arr); //高精度乘以单精度
Var
i: Integer;
Begin
FillChar(c, SizeOf(c), 0);
For i:= 1 To Maxn-1 Do Begin
c［i］ := c［i］ + a［i］ * b;
c［i+1］:= c［i］ Div k;
c［i］:= c［i］ Mod k
End;
End;
Procere HPule(a, b: Arr; ; Var c:Arr); //高精度乘以高精度
Var
i, j: Integer;
Begin
FillChar(c, SizeOf(c), 0);
For i:= 1 To Maxn Do
For j := 1 To Maxn Begin
c［i+j-1］ := c［i+j-1］ + a［i］ * b［ｊ］;
c［i+ｊ］:= c［i+j-1］ Div k;
c［i+j-1］:= c［i+j-1］ Mod k
End;
End;
Ps:为了防止网络错误识别, 过程中有不少符号是全角状态输入.
高精度加法
var
a,b,c:array[1..201] of 0..9;
n:string;
lena,lenb,lenc,i,x:integer;
begin
write('Input augend:'); readln(n);lena:=length(n);
for i:=1 to lena do a[lena-i+1]:=ord(n)-ord('0');{加数放入a数组}
write('Input addend:'); readln(n); lenb:=length(n);
for i:=1 to lenb do b[lenb-i+1]:=ord(n)-ord('0');{被加数放入b数组}
i:=1;
while (i<=lena) or(i<=lenb) do
begin
x := a + b + x div 10; {两数相加，然后加前次进位}
c := x mod 10; {保存第i位的值}
i := i + 1
end;
if x>=10 {处理最高进位}
then begin lenc:=i; c:=1 end
else lenc:=i-1;
for i:=lenc downto 1 do write(c); writeln {输出结果}
end.
高精度乘法（低对高）
const max=100; n=20;
var a:array[1..max]of 0..9;
i,j,k;x:integer;
begin
k:=1; a[k]:=1;{a=1}
for i:=2 to n do{a*2*3….*n}
begin
x:=0;{进位初始化}
for j:=1 do k do{a=a*i}
begin
x:=x+a[j]*i; a[j]:=x mod 10;x:=x div 10
end;
while x>0 do {处理最高位的进位}
begin
k:=k+1;a[k]:=x mod 10;x:=x div 10
end
end;
writeln;
for i:=k dowento 1 write(a){输出a}
end.
高精度乘法（高对高）
var a,b,c:array[1..200] of 0..9;
n1,n2:string; lena,lenb,lenc,i,j,x:integer;
begin
write('Input multiplier:'); readln(n1);
write('Input multiplicand:'); readln(n2);
lena:=length(n1); lenb:=length(n2);
for i:=1 to lena do a[lena-i+1]:=ord(n1)-ord('0');
for i:=1 to lenb do b[lenb-i+1]:=ord(n2)-ord('0');
for i:=1 to lena do
begin
x:=0;
for j:=1 to lenb do{对乘数的每一位进行处理}
begin
x := a*b[j]+x div 10+c;{当前乘积+上次乘积进位+原数}
c:=x mod 10;
end;
c:= x div 10;{进位}
end;
lenc:=i+j;
while (c[lenc]=0) and (lenc>1) do dec(lenc); {最高位的0不输出}
for i:=lenc downto 1 do write(c); writeln
end.
高精度除法
fillchar(s,sizeof(s),0);{小数部分初始化}
fillchar(posi,sizeof(posi),0); {小数值的位序列初始化}
len←0;st←0; {小数部分的指针和循环节的首指针初始化}
read(x,y);{读被除数和除数}
write(x div y);{输出整数部分}
x←x mod y;{计算x除以y的余数}
if x=0 then exit;{若x除尽y，则成功退出}
while len<limit do{若小数位未达到上限，则循环}
begin
inc(len);posi[x]←len;{记下当前位小数，计算下一位小数和余数}
x←x*10; s[len]←x div y;x←x mod y;
if posi[x]<>0 {若下一位余数先前出现过，则先前出现的位置为循环节的开始}
then begin st←posi[x]; break;end;{then}
if x=0 then break; {若除尽，则成功退出}
end;{while}
if len=0
then begin writeln;exit;end;{若小数部分的位数为0，则成功退出；否则输出小数点}
write('.');
if st=0 {若无循环节，则输出小数部分，否则输出循环节前的小数和循环节}
then for i←1 to len do write(s)
else begin
for i←1 to st-1 do write(s);
write('(');
for i←st to len do write(s);
write(')');
end;{else}

㈨ C++指针问题

所不同的是一般的变量包含的是实际的真实的数据，而指针是一个指示器，它告诉程序在内存的哪块区域可以找到数据。这是一个非常重要的概念，有很多程序和算法都是围绕指针而设计的，如链表。
开始学习
如何定义一个指针呢？就像你定义一个其它变量一样，只不过你要在指针名字前加上一个星号。我们来看一个例子：
下面这个程序定义了两个指针，它们都是指向整型数据。

int* pNumberOne;

int* pNumberTwo;
你注意到在两个变量名前的“p”前缀了吗？这是程序员通常在定义指针时的一个习惯，以提高便程序的阅读性，表示这是个指针。现在让我们来初始化这两个指针：

pNumberOne = &some_number;

pNumberTwo = &some_other_number;

&号读作“什么的地址”，它表示返回的是变量在内存中的地址而不是变量本身的值。在这个例子中，pNumberOne 等于
some_number的地址，所以现在pNumberOne指向some_number。 如果现在我们在程序中要用到some_number，我们就
可以使用pNumberOne。
我们来学习一个例子：
在这个例子中你将学到很多，如果你对指针的概念一点都不了解，我建议你多看几遍这个例子，指针是个很复杂的东西，但你会很快掌握它的。
这个例子用以增强你对上面所介绍内容的了解。它是用C编写的(注：原英文版是用C写的代码，译者重新用C++改写写了所有代码，并在DEV C++ 和VC++中编译通过！）

#include

void main()

{

// 声明变量：

int nNumber;

int *pPointer;

// 现在给它们赋值：

nNumber = 15;

pPointer = &nNumber;

//打印出变量nNumber的值：

cout"nNumber is equal to :";

// 现在通过指针改变nNumber的值：

*pPointer = 25;

//证明nNumber已经被上面的程序改变

//重新打印出nNumber的值:

cout"nNumber is equal to :";

}
通读一下这个程序，编译并运行它，务必明白它是怎样工作的。如果你完成了，准备好，开始下一小节。
陷井！
试一下，你能找出下面这段程序的错误吗？

#include

int *pPointer;

void SomeFunction();

{

int nNumber;

nNumber = 25;

//让指针指向nNumber:

pPointer = &nNumber;

}

void main()

{

SomeFunction(); //为pPointer赋值

//为什么这里失败了?为什么没有得到25

cout"Value of *pPointer: ";

}

这段程序先调用了SomeFunction函数，创建了个叫nNumber的变量，接着让指针pPointer指向了它。可是问题出在哪儿呢？当函数结
束后，nNumber被删掉了，因为这一个局部变量。局部变量在定义它的函数执行完后都会被系统自动删掉。也就是说当SomeFunction 函数返回
主函数main()时，这个变量已经被删掉，但pPointer还指着变量曾经用过的但现在已不属于这个程序的区域。如果你还不明白，你可以再读读这个程
序，注意它的局部变量和全局变量，这些概念都非常重要。
但这个问题怎么解决呢？答案是动态分配技术。注意这在C和C++中是不同的。由于大多数程序员都是用C++，所以我用到的是C++中常用的称谓。
动态分配
动态分配是指针的关键技术。它是用来在不必定义变量的情况下分配内存和让指针去指向它们。尽管这么说可能会让你迷惑，其实它真的很简单。下面的代码就是一个为一个整型数据分配内存的例子：
int *pNumber;
pNumber = new int;
第一行声明一个指针pNumber。第二行为一个整型数据分配一个内存空间，并让pNumber指向这个新内存空间。下面是一个新例，这一次是用double双精型：
double *pDouble;
pDouble = new double;
这种格式是一个规则，这样写你是不会错的。
但动态分配又和前面的例子有什么不同呢？就是在函数返回或执行完毕时，你分配的这块内存区域是不会被删除的所以我们现在可以用动态分配重写上面的程序：

#include

int *pPointer;

void SomeFunction()

{

// 让指针指向一个新的整型

pPointer = new int;

*pPointer = 25;

}

void main()

{

SomeFunction(); // 为pPointer赋值

cout"Value of *pPointer: ";

}

通读这个程序，编译并运行它，务必理解它是怎样工作的。当SomeFunction 调用时，它分配了一个内存，并让pPointer指向它。这一次，
当函数返回时，新的内存区域被保留下来，所以pPointer始终指着有用的信息，这是因为了动态分配。但是你再仔细读读上面这个程序，虽然它得到了正确
结果，可仍有一个严重的错误。
分配了内存，别忘了回收
太复杂了，怎么会还有严重的错误！其实要改正并不难。问题是：你动态地分配了一
个内存空间，可它绝不会被自动删除。也就是说，这块内存空间会一直存在，直到你告诉电脑你已经使用完了。可结果是，你并没有告诉电脑你已不再需要这块内存
空间了，所以它会继续占据着内存空间造成浪费，甚至你的程序运行完毕，其它程序运行时它还存在。当这样的问题积累到一定程度，最终将导致系统崩溃。所以这
是很重要的，在你用完它以后，请释放它的空间，如：
delete pPointer;
这样就差不多了，你不得不小心。在这你终止了一个有效的指针（一个确实指向某个内存的指针）。
下面的程序，它不会浪费任何的内存：

#include

int *pPointer;

void SomeFunction()

{

// 让指针指向一个新的整型

pPointer = new int;

*pPointer = 25;

}

void main()

{

SomeFunction(); //为pPointer赋值

cout"Value of *pPointer: ";

delete pPointer;

}

只有一行与前一个程序不同，但就是这最后一行十分地重要。如果你不删除它，你就会制造一起“内存漏洞”，而让内存逐渐地泄漏。
(译者:假如在程序中调用了两次SomeFunction，你又该如何修改这个程序呢？请读者自己思考)
传递指针到函数
传递指针到函数是非常有用的，也很容易掌握。如果我们写一个程序，让一个数加上5,看一看这个程序完整吗？：

#include

void AddFive(int Number)

{

Number = Number + 5;

}

void main()

{

int nMyNumber = 18;

cout"My original number is ";

AddFive(nMyNumber);

cout"My new number is ";

//得到了结果23吗？问题出在哪儿？

}

问题出在函数AddFive里用到的Number是变量nMyNumber的一个副本而传递给函数，而不是变量本身。因此， " Number =
Number + 5" 这一行是把变量的副本加了5，而原始的变量在主函数main()里依然没变。试着运行这个程序，自己去体会一下。

要解决这个问题，我们就要传递一个指针到函数，所以我们要修改一下函数让它能接受指针：把'void AddFive(int Number)' 改成
'void AddFive(int* Number)' 。下面就是改过的程序，注意函数调用时要用＆号，以表示传递的是指针：

#include

void AddFive(int* Number)

{

*Number = *Number + 5;

}

void main()

{

int nMyNumber = 18;

cout"My original number is ";

AddFive(&nMyNumber);

cout"My new number is ";

}
试着自己去运行它，注意在函数AddFive的参数Number前加*号的重要性：它告诉编译器，我们是把指针所指的变量加5。而不并指针自己加5。
最后，如果想让函数返回指针的话，你可以这么写：
int * MyFunction();
在这句里，MyFunction返回一个指向整型的指针。
指向类的指针
指针在类中的操作要格外小心，你可以用如下的办法定义一个类：

class MyClass

{

public:

int m_Number;

char m_Character;

};
接着你就可以定义一个MyClass 类的变量了：
MyClass thing;
你应该已经知道怎样去定义一个指针了吧：
MyClass *thing;
接着你可以分配个内存空间给它：
thing = new MyClass;

注意，问题出现了。你打算怎样使用这个指针呢，通常你可能会写'thing.m_Number'，但是thing是类吗，不，它是一个指向类的指针，它
本身并不包含一个叫m_Number的变量。所以我们必须用另一种方法：就是把'.'(点号）换成 -> ,来看下面的例子：

class MyClass

{

public:

int m_Number;

char m_Character;

};

void main()

{

MyClass *pPointer;

pPointer = new MyClass;

pPointer->m_Number = 10;

pPointer->m_Character = 's';

delete pPointer;

}
指向数组的指针
你也可以让指针指向一个数组，按下面的方法操作：
int *pArray;
pArray = new int[6];
程序会创建一个指针pArray，让它指向一个有六个元素的数组。另外一种方法，不用动态分配：
int *pArray;
int MyArray[6];
pArray = &MyArray[0];

注意，&MyArray[0] 也可以简写成 MyArray ，都表示是数组的第一个元素地址。但如果写成pArray = &
MyArray可能就会出问题，结果是 pArray 指向的是指向数组的指针（在一维数组中尽管与&MyArray[0]相等），而不是你想要
的，在多维数组中很容易出错。
在数组中使用指针
一旦你定义了一个指向数组的指针，你该怎样使用它呢？让我们来看一个例子，一个指向整型数组的指针：

#include

void main()

{

int Array[3];

Array[0] = 10;

Array[1] = 20;

Array[2] = 30;

int *pArray;

pArray = &Array[0];

cout"pArray points to the value %d\n";

}

如果让指针指向数组元素中的下一个，可以用pArray++.也可以用你应该能想到的pArray + 1，都会让指针指向数组的下一个元素。要注意的
是你在移动指针时，程序并不检查你是否已经移动地超出了你定义的数组，也就是说你很可能通过上面的简单指针加操作而访问到数组以外的数据，而结果就是，可
能会使系统崩溃，所以请格外小心。
当然有了pArray + 1，也可以有pArray － 1，这种操作在循环中很常用，特别是while循环中。
另一个需要注意的是，如果你定义了一个指向整型数的指针：int* pNumberSet ，你可以把它当作是数组，如：pNumberSet[0] 和 *pNumberSet是相等的，pNumberSet[1]与*(pNumberSet + 1)也是相等的。
在这一节的最后提一个警告：如果你用 new 动态地分配了一个数组，
int *pArray;
pArray = new int[6];
别忘了回收，
delete[] pArray;
这一句是告诉编译器是删除整个数组而不一个单独的元素。千万记住了。
后话
还有一点要小心，别删除一个根本就没分配内存的指针，典型的是如果没用new分配，就别用delete:

void main()

{

int number;

int *pNumber = number;

delete pNumber; // 错误 - *pNumber 没有用new动态分配内存.

}
常见问题解答
Q：为什么我在编译程序时老是在 new 和 delete语句中出现'symbol undefined' 错误？
A：new 和 delete都是C++在C上的扩展，这个错误是说编译器认为你现在的程序是C而不C++，当然会出错了。看看你的文件名是不是.cpp结尾。
Q：new 和 malloc有什么不同？
A：new 是C++中的关健字，用来分配内存的一个标准函数。如果没有必要，请不要在C++中使用malloc。因为malloc是C中的语法，它不是为面向对象的C++而设计的。
Q：我可以同时使用free 和 delete吗？
A：你应该注意的是，它们各自所匹配的操作不同。free只用在用malloc分配的内存操作中，而delete只用在用new分配的内存操作中。
引用（写给某些有能力的读者）
这一节的内容不是我的这篇文章的中心，只是供某些有能力的读者参考。
有些读者经常问我关于引用和指针的问题，这里我简要地讨论一下。
在前面指针的学习中，我们知道（＆）是读作“什么的地址”，但在下面的程序中，它是读作“什么的引用”
int& Number = myOtherNumber;
Number = 25;
引用有点像是一个指向myOtherNumber的指针，不同的是它是自动删除的。所以他比指针在某些场合更有用。与上面等价的代码是：
int* pNumber = &myOtherNumber;
*pNumber = 25;
指针与引用另一个不同是你不能修改你已经定义好的引用，也就是说你不能改变它在声明时所指的内容。举个例子：
int myFirstNumber = 25;
int mySecondNumber = 20;
int &myReference = myFirstNumber;
myReference = mySecondNumber;//这一步能使myReference 改变吗？
cout<<myFristNumber<<endl;//结果是20还是25？
当在类中操作时，引用的值必须在构造函数中设定，例：
CMyClass::CMyClass(int &variable) : m_MyReferenceInCMyClass(variable)
{
// constructor code here
}
总结
这篇文章开始可能会较难掌握，所以最好是多读几遍。有些读者暂时还不能理解，在这儿我再做一个简要的总结：
指针是一个指向内存区域的变量，定义时在变量名前加上星号（*）（如：int *number）。
你可以得到任何一个变量的地址，只在变量名前加上＆（如：pNumber = &my_number）。
你可以用'new' 关键字动态分配内存。指针的类型必须与它所指的变量类型一样（如：int *number 就不能指向 MyClass）。
你可以传递一个指针到函数。必须用'delete'删除你动态分配的内存。
你可以用&array[0]而让指针指向一个数组。
你必须用delete[]而不是delete来删除动态分配的数组。

文章到这儿就差不多结束了，但这些并不就是指针所有的东西，像指向指针的指针等我还没有介绍，因为这些东西对于一个初学指针的人来说还太复杂了，我不能
让读者一开始就被太复杂的东西而吓走了。好了，到这儿吧，试着运行我上面写的小程序，也多自己写写程序，你肯定会进步不小的！