c语言算法 - 分而治之算法

2017年02月06日 95 阅读

c语言算法 - 分而治之算法2010-01-28君主和殖民者们所成功运用的分而治之策略也可以运用到高效率的计算机算法的设计过程中。本章将首先介绍怎样在算法设计领域应用这一古老的策略，然后将利用这一策略解决如下问题：最小最大问题、矩阵乘法、残缺棋盘、排序、选择和计算一个几何问题——找出二维空间中距离最近的两个点。本章给出了用来分析分而治之算法复杂性的数学方法，并通过推导最小最大问题和排序问题的复杂性下限来证明分而治之算法对于求解这两种...

c语言算法 - 分而治之算法 - 残缺棋盘

2017年02月06日 133 阅读

c语言算法 - 分而治之算法 - 残缺棋盘2010-01-28残缺棋盘（defective chessboard）是一个有2k×2k 个方格的棋盘，其中恰有一个方格残缺。图2 - 3给出k≤2时各种可能的残缺棋盘，其中残缺的方格用阴影表示。注意当k= 0时，仅存在一种可能的残缺棋盘（如图1 4 - 3 a所示）。事实上，对于任意k，恰好存在22k 种不同的残缺棋盘。残缺棋盘的问题要求用三格板（t r i o m i n o e s）覆盖残...

c语言算法 - 分而治之算法 - 归并排序

2017年02月06日 94 阅读

c语言算法 - 分而治之算法 - 归并排序2010-01-28可以运用分而治之方法来解决排序问题，该问题是将n个元素排成非递减顺序。分而治之方法通常用以下的步骤来进行排序算法：若n 为1，算法终止；否则，将这一元素集合分割成两个或更多个子集合，对每一个子集合分别排序，然后将排好序的子集合归并为一个集合。假设仅将n个元素的集合分成两个子集合。现在需要确定如何进行子集合的划分。一种可能性就是把前面n- 1个元素放到第一个子集中（称为A），最后一个元素放到第二个...

c语言算法 - 分而治之算法 - 距离最近的点对

2017年02月06日 106 阅读

c语言算法 - 分而治之算法 - 距离最近的点对2010-01-28给定n个点（xi，yi）（1≤i≤n），要求找出其中距离最近的两个点。例14-7 假设在一片金属上钻n个大小一样的洞，如果洞太近，金属可能会断。若知道任意两个洞的最小距离，可估计金属断裂的概率。这种最小距离问题实际上也就是距离最近的点对问题。通过检查所有的n（n- 1 ） / 2对点，并计算每一对点的距离，可以找出距离最近的一对点。这种方法所需要的时间为（n2 ）。我们称这种方...

c语言算法 - 分而治之算法 - 快速排序

2017年02月06日 96 阅读

c语言算法 - 分而治之算法 - 快速排序2010-01-28分而治之方法还可以用于实现另一种完全不同的排序方法，这种排序法称为快速排序（quick sort）。在这种方法中， n个元素被分成三段（组）：左段l e f t，右段r i g h t和中段m i d d l e。中段仅包含一个元素。左段中各元素都小于等于中段元素，右段中各元素都大于等于中段元素。因此l e f t和r i g h t中的元素可以独立排序，并且不必对l e f t和r i g h...

c语言算法 - 分而治之算法 - 选择排序

2017年02月06日 102 阅读

c语言算法 - 分而治之算法 - 选择排序2010-01-28对于给定的n个元素的数组a[0 : n - 1]，要求从中找出第k小的元素。当a[0 : n - 1]被排序时，该元素就是a[k - 1]。假设n=8，每个元素有两个域k e y和I D，其中k e y是一个整数，I D是一个字符。假设这8个元素为[（ 1 2 ,a），（ 4 ,b），（ 5 ,c），（ 4 ,d），（ 5 ,e），（ 1 0 ,f），（ 2 ,g），（ 2 0 ,h）], 排序...

c语言算法 - 贪婪算法

2017年02月06日 105 阅读

c语言算法 - 贪婪算法2010-01-28虽然设计一个好的求解算法更像是一门艺术，而不像是技术，但仍然存在一些行之有效的能够用于解决许多问题的算法设计方法，你可以使用这些方法来设计算法，并观察这些算法是如何工作的。一般情况下，为了获得较好的性能，必须对算法进行细致的调整。但是在某些情况下，算法经过调整之后性能仍无法达到要求，这时就必须寻求另外的方法来求解该问题。本章首先引入最优化的概念，然后介绍一种直观的问题求解方法：贪婪算法。最后，应用该算法给出货箱装...

c语言算法 - 贪婪算法 - 0/1背包问题

2017年02月06日 100 阅读

c语言算法 - 贪婪算法 - 0/1背包问题2010-01-28在0 / 1背包问题中，需对容量为c的背包进行装载。从n个物品中选取装入背包的物品，每件物品i的重量为wi，价值为pi。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高，即n ？i=1pi xi 取得最大值。约束条件为n ？i=1wi xi≤c 和xi？[0 , 1]（ 1≤i≤n）。在这个表达式中，需求出xt的值。xi=1表示物品i...

c语言算法 - 贪婪算法 - 拓扑排序

2017年02月06日 101 阅读

c语言算法 - 贪婪算法 - 拓扑排序2010-01-28一个复杂的工程通常可以分解成一组小任务的集合，完成这些小任务意味着整个工程的完成。例如，汽车装配工程可分解为以下任务：将底盘放上装配线，装轴，将座位装在底盘上，上漆，装刹车，装门等等。任务之间具有先后关系，例如在装轴之前必须先将底板放上装配线。任务的先后顺序可用有向图表示——称为顶点活动（ Activity On Vertex, AOV）网络。有向图的顶点代表任务，有向边（i...

c语言算法 - 贪婪算法 - 单源最短路径

2017年02月06日 116 阅读

c语言算法 - 贪婪算法 - 单源最短路径2010-01-28在这个问题中，给出有向图G，它的每条边都有一个非负的长度（耗费） a [i ][ j ]，路径的长度即为此路径所经过的边的长度之和。对于给定的源顶点s，需找出从它到图中其他任意顶点（称为目的）的最短路径。图13-10a 给出了一个具有五个顶点的有向图，各边上的数即为长度。假设源顶点s 为1，从顶点1出发的最短路径按路径长度顺序列在图13-10b 中，每条路径前面的数字为路径的长度。利用E. Di...

c语言算法 - 贪婪算法 - 二分覆盖

2017年02月06日 92 阅读

c语言算法 - 贪婪算法 - 二分覆盖2010-01-28二分图是一个无向图，它的n个顶点可二分为集合A和集合B，且同一集合中的任意两个顶点在图中无边相连（即任何一条边都是一个顶点在集合A中，另一个在集合B中）。当且仅当B中的每个顶点至少与A中一个顶点相连时，A的一个子集A" 覆盖集合B（或简单地说，A" 是一个覆盖）。覆盖A" 的大小即为A" 中的顶点数目。当且仅当A" 是覆盖B的子集中最小的时，A" 为最小覆盖。例1-10 考察如图1 - 6所示的具有...

c语言算法 - 贪婪算法 - 货箱装船

2017年02月06日 95 阅读

c语言算法 - 贪婪算法 - 货箱装船2010-01-28这个问题来自例1 - 2。船可以分步装载，每步装一个货箱，且需要考虑装载哪一个货箱。根据这种思想可利用如下贪婪准则：从剩下的货箱中，选择重量最小的货箱。这种选择次序可以保证所选的货箱总重量最小，从而可以装载更多的货箱。根据这种贪婪策略，首先选择最轻的货箱，然后选次轻的货箱，如此下去直到所有货箱均装上船或船上不能再容纳其他任何一个货箱。例1-7 假设n=8, [w1 , ... w8]=[100,20...

c语言算法 - 贪婪算法 - 最小耗费生成树

2017年02月06日 97 阅读

c语言算法 - 贪婪算法 - 最小耗费生成树2010-01-28在例1-2及1-3中已考察过这个问题。因为具有n 个顶点的无向网络G的每个生成树刚好具有n-1条边，所以问题是用某种方法选择n-1条边使它们形成G的最小生成树。至少可以采用三种不同的贪婪策略来选择这n-1条边。这三种求解最小生成树的贪婪算法策略是： K r u s k a l算法，P r i m算法和S o l l i n算法。1.Kruskal算法（1） 算法思想K r u s k a l算...

c语言贪婪算法算法-算法思想

2017年02月06日 94 阅读

c语言贪婪算法算法-算法思想2010-01-28在贪婪算法（greedy method）中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪婪决策的依据称为贪婪准则（greedy criterion）。例1-4 [找零钱] 一个小孩买了价值少于1美元的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目不限的面值为2 5美分、1 0美分、5美分、及1美分的硬币。...

C语言实现QQ密码大盗

2017年02月06日 93 阅读

C语言实现QQ密码大盗2010-01-28余和均一般的盗密码的软件的软件都是通过监视键盘来获得密码，这样操作比较方便，但是这样也存在一定问题，密码有的时候不是很准确，因为有的人输入密码并不是从前到后输入，当然这样的人也是少数，盗密码嘛，当然去得到那些比较粗心的人的密码！ 通过安装钩子来监视QQ登陆界面就是获得密码的方法，在安装前得先找到登陆窗口的句柄，当钩子安装后，记录键盘，当用户“回车”或是点了“登陆”就可...

C语言实现MATLAB 6.5中M文件的方法

2017年02月06日 107 阅读

C语言实现MATLAB 6.5中M文件的方法2010-01-28 计算机信息技术 宋威众所周知，MATLAB是一个功能强大的数学软件，擅长于用矩阵运算完成各种数学功能。但是其程序需要在MATLAB环境下解释执行，效率不高。如果能将它强大的函数库用于C语言，利用C来编译执行，MATLAB将能发挥更大的作用。所以，MATLAB从5.0开始已经提供了与外部C/C++程序的应用程序接口，为利用C语言调用MATLAB的函数提供了可能。但是MATLAB的接口发展很快，...

C语言的extern声明辨析

2017年02月06日 88 阅读

C语言的extern声明辨析2010-01-281 基本解释extern可以置于变量或者函数前，以标示变量或者函数的定义在别的文件中，提示编译器遇到此变量和函数时在其他模块中寻找其定义。另外，extern也可用来进行链接指定。2 问题：extern 变量在一个源文件里定义了一个数组：char a[6];在另外一个文件里用下列语句进行了声明：extern char *a；请问，这样可以吗？答案与分析：1）、不可以，程序运行时会告诉你非法访问。原因在于，指向类...

再谈C语言中数组和指针之间的互操作

2017年02月06日 102 阅读

再谈C语言中数组和指针之间的互操作2010-01-28张桂权我曾说过，在C语言中只有一维的数组（这是我对数组的看法），而且数组元素可以是任何类型的数据（或对象），自然也可以是另外的一个数组（因为数组也是一种数据类型）。所以如果你坚持要说有多维数组，那也不是不可能的事情。我们只要把一个数组赋值给另一个数组的元素就可以了。当然了，我们必须保证在程序编译期数组的大小是一个固定的常数。其实，数组的操作很简单的。只要我们确定一个数组的大小和指向该数组下标为0的元素的...

用C语言实现常见的三种中文内码转换

2017年02月06日 93 阅读

用C语言实现常见的三种中文内码转换2010-01-28常见的中文内码一般有GB2312（简体中文），GBK和台湾那边用的BIG5（繁体中文），有时候看一些台湾编程论坛里的资料，都是乱码，如果在IE中浏览，则要求安装繁体字库的支持。网上也有很多中文内码的转换工具，什么专家，大师，巨匠之类所有光辉灿烂的名字都被使用了，但是在自己的程序中集成这些功能岂不是更好。以前曾广泛流传过使用码表来转换中文内码的Code，但毕竟不完美，而且还要携带或内置一个巨大的表，浪费资...

C语言之static辨析

2017年02月06日 87 阅读

C语言之static辨析2010-01-281、概述static声明的变量在C语言中有两方面的特征：1）、变量会被放在程序的全局存储区中，这样可以在下一次调用的时候还可以保持原来的赋值。这一点是它与堆栈变量和堆变量的区别。2）、变量用static告知编译器，自己仅仅在变量的作用范围内可见。这一点是它与全局变量的区别。2、问题：Static的理解关于static变量，请选择下面所有说法正确的内容：A、若全局变量仅在单个C文件中访问，则可以将这个变量修改为静态...