C常用算法

liuxiaowen12345 贡献于2011-11-21

作者   创建于2009-01-13 09:41:00   修改者  修改于2009-01-13 10:10:00字数41215

文档摘要:第一章认真做事常常是浪费时间。- RobertByrne,撞球大师,台球选手和作家人们是这样描述它的:蛮力法是一种简单直接地解决问题的方法,常常直接基于问题的描述和所涉及的概念定义。这里的“力”是指计算机的能“力”,而不是人的智“力”。我们也可以用“直接做吧!”来描述蛮力法的策略。而且一般来说,蛮力策略也常常是最容易应用的方法。虽然巧妙和高效的算法很少来自于蛮力法,但我们不应该忽略它作为一种重要的算法设计策略的地位。第一,和其他某些策略不同,我们可以应用蛮力法来解决广阔领域的各种问题(实际上,它可能是惟一一种几乎什么问题都能解决的一般性方法)。
关键词:

Taken from "Introduction to The Design and Analysis of Algorithms" by Anany Levitin 节选自《算法设计与分析基础》潘彦 译 蛮力法 就像宝剑不是撬棍一样,科学也很少使用蛮力。 ——Edward Lytton (1830 - 1873),leila,第二卷,第一章 认真做事常常是浪费时间。 ——Robert Byrne,撞球大师,台球选手和作家 人们是这样描述它的:蛮力法是一种简单直接地解决问题的方法,常常直接基于问题的描述和所涉及的概念定义。这里的“力”是指计算机的能“力”,而不是人的智“力”。我们也可以用“直接做吧!”来描述蛮力法的策略。而且一般来说,蛮力策略也常常是最容易应用的方法。虽然巧妙和高效的算法很少来自于蛮力法,但我们不应该忽略它作为一种重要的算法设计策略的地位。第一,和其他某些策略不同,我们可以应用蛮力法来解决广阔领域的各种问题(实际上,它可能是惟一一种几乎什么问题都能解决的一般性方法)。具体来说,蛮力法常常用于一些非常基本、但又十分重要的算法,比如计算n个数字的和,求一个列表的最大元素,等等。第二,对于一些重要的问题来说(比如:排序、查找、矩阵乘法和字符串匹配),蛮力法可以产生一些合理的算法,它们多少具备一些实用价值,而且并不限制实例的规模。第三,如果要解决的问题实例不多,而且蛮力法可以用一直能够接受的速度对实例求解,那么,设计一个更高效算法所花费的代价很可能是不值得的。第四,即使效率通常很低,仍然可以用蛮力算法解决一些小规模的问题实例。最后,一个蛮力算法可以为研究或教学目的服务,例如,它可以作为准绳,来衡量同样问题的更高效算法。 下列这些著名的算法可以看作是蛮力法的例子:基于定义的矩阵乘法算法;选择排序;顺序查找;简单的字符串匹配算法。穷举查找是解组合问题的一种蛮力方法。它要求生成问题中的每一个组合对象,选出其中满足该问题约束的对象,然后找出一个期望的对象。旅行商问题、背包问题和分配问题是典型的能够用穷举查找算法求解的问题,至少在理论上是这样的。除了相关问题的一些规模非常小的实例,穷举查找法几乎是不实用的。 分治法 无论人们在祈祷什么,他们总是在祈祷一个奇迹。每一个祈祷都可以简化为:伟大的上帝呀,请让两个二相加不等于四吧。 ——伊万·屠格涅夫(1818 - 1883),俄国作家和短篇小说家 分治法可能是最著名的通用算法设计技术了。虽然它的名气可能和它那好记的名字有关,但它的确是当之无愧的:很多非常有效的算法实际上是这个通用算法的特殊实现。其实,分治法是按照以下方案工作的: 将问题的实例划分为同一个问题的几个较小的实例,最好拥有同样的规模。 对这些较小的实例求解(一般使用递归方法,但在问题规模足够小的时候,有时也会使用一些其他方法)。 如果必要的话,合并这些较小问题的解,以得到原始问题的解。 不是所有的分治算法都一定比简单蛮干更有效。但是,通常我们向算法女神所做的祈祷都被应允了,因而,使用分治法往往比使用其他方法效率更高。实际上,分治法孕育了计算机科学中许多最重要和最有效的算法。虽然我们通常只考虑顺序算法,但要知道,分治法对于并行算法是非常理想的,因为各个子问题都可以由不同的CPU同时计算。许多分治算法的时间效率T(n)满足方程T(n)=aT(n/b)+f(n)。 一些应用分治法的案例: 合并排序是一种分治排序算法。它把一个输入数组一分为二,并对它们递归排序,然后把这两个排好序的子数组合并为原数组的一个有序排列。在任何情况下,这个算法的时间效率都是Θ(nlogn),而且它的键值比较次数非常接近理论上的最小值。它的主要缺点是需要相当大的额外存储空间。 快速排序是一种分治排序算法,它根据元素值和某些事先确定的元素的比较结果,来对输入元素进行分区。快速排序十分有名,这不仅因为对于随机排列的数组,它是一种较为出众的nlogn效率算法,而且因为它的最差效率是平方级的。 折半查找是一种对有序数组进行查找O(logn)效率算法。它是应用分治技术的一个非典型案例,因为在每次迭代中,它只需要解决两个问题的一个。 二叉树的经典遍历算法——前序、中序、后序和其他类似的算法都需要递归处理左右两棵子树,它们都可以当作是分治技术的例子。用一些特定的外部顶点来替代给定树的空子树,有助于对这些算法进行分析。 有一种处理两个n位整数相乘的分治算法,大约需要做n(index:1.585)次一位数乘法。 Strassen算法只需要做7次乘法就能计算出两个2桔方阵的积,但比基于定义的算法要做更多次的加法。利用分治技术,该算法计算两个n阶方阵的积,但比基于定义的算法要做更多次的加法。利用分治技术,该算法计算两个n阶方阵的乘法时需要做n(index:2.807)次乘法。 分治技术可以成功地应用于两个重要的计算几何问题:最近对问题和凸包问题。 减治法 普卢塔克说,萨特斯为了告诉他的士兵坚忍和智慧比蛮力更重要的道理,把两匹马带到他们面前,然后让两个人拔光马的尾毛。一个人是魁梧的大力士,他用力地拔了又拔,但一点效果也没有;另一个人是一个精美的、长相矫捷的裁缝,他微笑着,每次拔掉一根毛,很快就把尾巴拔得光秃秃的。 ——E. Cobham Brewer,《惯用语和寓言词典》,1898 减治技术利用了一种关系:一个问题给定实例的解和同样问题较小实例的解之间的关系。一旦建立了这样一种关系,我们既可 以从顶至下(递归地),也可以从底至上(非递归地)地来运用。减治法有3种主要的变种: 减去一个常量; 减去一个常数因子; 减去的规模是可变的。 在减常量变种中,每次算法迭代总是从实例规模中减去一个规模相同的常量。一般来说,这个常量等于一,但减二的情况偶尔也会发生,例如,有的算法会根据实例规模为奇数和偶数的不同情况,分别做不同的处理。 减常因子技术意味着在算法的每次迭代中,总是才实例的规模中减去一个相同的常数因子。在大多数应用中,这样的常数因子等于二。 最后,在减治法的减可变规模变种中,算法在每次迭代时,规模减小的模式都是不同的。计算最大公约数的欧几里德算法是这种情况的一个很好的例子。回想一下,这个算法是基于这个公式的: gcd(m,n)=gcd(n,m mod n) 虽然等号右边的那些参数总是小于等号左边的参数(至少从该算法的第二次迭代开始),但它们既不是以常数也不是以常数因子的方式减小的。 一些应用减治法的案例: 插入排序是减(减一)治技术在排序问题上的直接应用。无论在平均情况还是最差情况下,它都是一个Θ(n2)的算法,但在平均情况下的效率大约要比最差情况快两倍。该算法一个较为出众的优势在于,对于几乎有序的数组,它的性能是很好的。 深度优先查找(DFS)和广度优先查找(BFS)是两种主要的图遍历算法。通过把图表示成深度优先森林或者广度优先森林的形式,有助于对图的许多重要特性进行研究。两种算法都有着相同的时间效率:对于邻接矩阵表示法来说是Θ(|V|2);对于邻接链表表示法来说是Θ(|V|+|E|)。 一个有向图是一个对边指定了方向的图。拓扑排序要求按照这种次序列出它的顶点,使得对于图中每一条边来说,边的起始顶点总是排在边的结束顶点之前。当且仅当有向图是一个无环有向图(不包含回路的有向图)的时候,该问题有解,也就是说,它不包含有向的回路。 解决拓扑排序问题有两种算法。第一种算法基于深度优先查找;第二种算法基于减一技术的直接应用。 在设计生成基本组合对象的算法时,减一技术是一种非常自然的选择。这类算法中最高效的类型是最小变化算法。然而,组合对象的数量增长地如此之快,使得实际应用中,即使最高效的算法也只能用来解决这类问题的一些非常小的实例。 有些问题是能够用减常因子算法来解的,这样的例子包括:用天平来辨别假币、俄式乘法以及约瑟夫斯问题。其他两个更重要的例子是折半查找和用平方求幂。 对于某些基于减治技术的算法,在算法的一次迭代和另一次迭代时消减的规模是变化的。这种减可变规模算法的例子包括欧几里德算法、选择问题的基于分区的算法、插值查找和二叉查找树中的查找和插入操作。 变治法 生活的秘密在于。。。用一个烦恼代替另一个烦恼。 ——Charles M. Schulz (1922 - 2000),美国漫画家,史努比之父 这种设计方法基于变换的思想,称为变治法。因为这些方法都是分成两个阶段工作的。首先,在“变”的阶段,出于这样或者那样的原因,把问题的实例变得更容易求解。然后,在第二阶段或者说“治”的阶段,对实例进行求解。根据我们对问题实例的变换方式,变治思想有3种主要的类型: 变换为同样问题的一个更简单或者更方便的实例——我们称之为实例化简; 变换为同样问题的不同表现——我们称之为改变表现。 变换为另一个问题的实例,这种问题的算法是已知的——我们称之为问题化简。 一些应用变治法的案例: 堆是一棵基本完备二叉树,它的键都满足父母优势要求。虽然定义为二叉树,但一般用数组来实现堆。堆对于优先队列的高效实现来说尤为重要;同时,堆还是堆排序的基础。 堆排序在理论上是一种重要的排序算法,它的基本思路是,在排好堆中的数组元素后,再从剩余的堆中连续删除最大的元素。 无论在最差情况下还是在平均情况下,该算法的运行时间都属于Θ(nlogn),而且,它还是在位的排序算法。 AVL树是一种在二叉树可能达到的广度上尽量平衡的二叉查找树。平衡是由四种称为旋转的变换来维持的。AVL树上的所有基本操作都属于Θ(logn);它消除了经典二叉查找树在最差效率上的弊端。 2-3树是一种达到了完美平衡的查找树,它允许一个节点最多包含两个键和三个子女。这个思想推而广之,会产生一种非常重要的B树。 高斯消去法是一种解线性方程组的算法,它是线性代数中的一种基本算法。它通过把方程组变换为反向替换法求解。高斯消去法大约需要1/3n3次乘法运算。 在无需对系数进行预处理的多项式求解算法中,霍纳法则是最优的。它只需要n次乘法和n次加法。它还有一些有用的副产品,比如综合除法算法。 两种计算a(index:n)的二进制幂算法。它们使用了指数n的二进制表示,但它们按照相反的方向对其进行处理:从左到右和从右到左。 线性规划关心的是最优化一个包含若干变量的线性函数,这个函数受到一些形式为线性等式和线性不等式的约束。有一些高效的算法可以对这个问题的庞大实例求解,它们包含了成千上万的变量和约束,但不能要求变量必须是整数。如果变量一定要是整数,我们称之为整数线性规划问题,这类问题的难度要高很多。 时空权衡 最重要的事情永远不能受次要事情的支配。 ——Johnn Wolfgang von Goethe (1749 - 1832) 无论对于计算机理论工作者还是计算机实践工作者来说,算法设计中的时空权衡都是一个总所周知的问题。作为一个例子,考虑一下在函数定义域的多个点上计算函数值的问题。如果运算时间更为重要的话,我们可以事先把函数值计算好并将它们存储在一张表中。这就是在电子计算机发明前,“人工计算机”所做的工作,那时的图书馆也被厚重的数学用表堆满了。虽然随着电子计算机的广泛应用,这些数学用表失去了大部分的吸引力,但事实正面,在开发一些用于其他问题的重要算法时,它们的基本思想还是非常有用的。按照一种更一般的表述,这个思想是对问题的部分或全部输入做预处理,然后对获得的额外信息进行存储,以加速后面问题的求解。我们把这个方法称为输入增强。其他采用空间换时间权衡思想的技术简单地使用额外空间来实现更快和(或)更方便的数据存取。我们把这种方法称为预构造。这个名字强调了这种空间换时间权衡技术的两个方面:所讨论问题在实际处理之前,已经做过某些处理了;但和输入增强技术不同,这个技术只涉及存取结构。还有一种和空间换时间权衡思想相关的算法设计技术:动态规划。这个策略的基础是把给定问题中重复子问题的解记录在表中,然后求得所讨论问题的解。 最后还要对算法设计中时间和空间的相互作用作两点说明:首先,并不是在所有的情况下,时间和空间这两种资源都必须相互竞争。实际上,它们可以联合起来,使得一个算法无论在运行时间上还是消耗的空间上都达到最小化。具体来说说,这种情况出现在一个算法使用了一种空间效率很高的数据结构来表示问题的输入,这种结构又反过来提高算法的时间效率。作为一个例子,考虑一下图的遍历问题。回忆一下两种主要的遍历算法(深度优先查找和广度优先查找),它们搜时间效率依赖于表示图的数据结构:对于邻接矩阵表示法是Θ(n2),对于邻接链表表示法是Θ(n+m),其中n和m分别是顶点和边的数量。如果输入图是稀疏的,也就是说,相对于顶点的数量来说,边的数量并不多(比方说,m∈O(n)),无论从空间角度还是从运行时间的角度来看,邻接链表表示法的效率都会更高一些。在处理稀疏矩阵和稀疏多项式的时候也会有相同的情况:如果在这些对象中,0所占的百分比足够高,在表示和处理对象时把0忽略,我们既可以节约空间也可以节约时间。 其次,在讨论空间换时间权衡的时候,我们无法不提到数据压缩这个重要领域。然而,我们必须强调,数据压缩的主要目的是节约空间而不是作为解决另一个问题的一项技术。 一些应用时空权衡的案例: 分布计数是一种特殊的方法,用来对元素取值来自于一个小集合的列表排序。 用于串匹配的Horspool算法可以看作是Boyer-Moore算法的一个简化版本。两个算法都以输入增强思想为基础,并且从右向左比较模式中的字符。两个算法都是用同样的坏符合移动表;Boyer-Moore算法还使用了第二个表,称为好后缀移动表。 散列是一种非常高效的实现字典的方法。它的基本思想是把键映射到一张一维表中。这种表在大小上的限制使得它必须采用一种碰撞解决机制。散列的两种主要类型是开散列又称为分离链(键存储在散列表以外的链表中)以及闭散列又称为开式寻址(键存储在散列表中)。平均情况下,这两种算法的查找、插入和删除操作的效率都是属于Θ(1)的。 B树是一颗平衡查找树,它把2-3树的思想推广到允许多个键位于同多节点一个节点上。它的主要应用是维护存储在磁盘上的数据的类索引信息。通过选择恰当的树的次数,即使对于非常大的文件,我们所实现的查找、插入和删除操作也只需要执行很少几次的磁盘存取。 动态规划 思想,就像幽灵一样……在它自己解释自己之前,必须先告诉它些什么。 ——查尔斯·狄更斯(1812-1870) 动态规划(dynamic programming)是一种算法设计技术,它有着相当有趣的历史。作为一种使多阶段决策过程最优的通用方法,它是在20世纪50年代由一位卓越的美国数学家Richard Bellman所发明的。因此,这个技术名字中的"programming"是计划和规范的意思,不是代表计算机中的编程。它作为一种重要的工具在应用数学中的价值被大家认同以后,起码在计算机科学的圈子里,人们不仅用它来解决特定类型的最优问题,而且最终把它作为一种通用的算法设计技术来使用。在这里,我们正是从这个角度来考虑这种技术的。 如果问题是由交叠的子问题所构成的,我们就可以用动态规划技术来解决它。一般来说,这样的子问题出现在对给定问题求解的递推关系中,这个递推关系中包含了相同类型的更小子问题的解。动态规划法建议,与其对交叠的子问题一次又一次地求解,还不如对每个较小的子问题只求解一次并把结果记录在表中,这样就可以从表中得出原始问题的解。一般来说,一个算法如果基于经典从底向上动态规划方法的话,需要解出给定问题的所有较小子问题。动态规划法的一个变种试图避免对不必要的子问题求解,它利用了一种所谓的记忆功能,可以把它看作是动态规划的一种从顶至下的变种。但无论我们使用动态规划的经典从底至上版本还是它基于记忆功能的从顶至下版本,设计这样一种算法的关键步骤还是相同的,即,导出一个问题实例的递推关系,该递推关系包含该问题的更小(并且是交叠的)子实例的解。对一个最优问题应用动态规划方法要求该问题满足最优性原则:一个最优问题的任何实例的最优解是由该实例的子实例的最优解组成的。 一些应用动态规划的案例: 通过构造帕斯卡三角形来计算二项式系数可以看作是动态规划技术在一个非最优问题上的应用。 求传递闭包的Warshall算法和求完全最短路径问题的Floyd算法都基于同一种思想,可以把这种思想解释为动态规划技术的一种应用。 如果已知键的一个集合以及它们的查找概率,可以使用动态规划方法来构造一颗最优二叉查找树。 用动态规划算法求解背包问题可以作为应用该技术对组合难题求解的例证。 贪婪技术 贪婪,我找不到一个更好的词来描述它,它就是好!它就是对!它就是有效! ——美国演员迈克·道格拉斯,在影片《华尔街》中扮演Gordon Gecko时的台词 贪婪法建议通过一系列步骤来构造问题的解,每一步对目前构造的部分解做一个扩展,直到获得问题的完整解为止。这个技术的核心是,所做的每一步选择都必须满足: 可行的:即它必须满足问题的约束。 局部最优:它是当前步骤中所有可行选择中最佳的局部选择。 不可取消:即选择一旦做出,在算法的后面步骤中就无法改变了。 这些要求对这种技术的名称作出了解释:在每一步中,它要求“贪婪”地选择最佳操作,并希望通过一系列局部的最优选择,能够产生一个整个问题的(全局的)最优解。我们尽量避免从哲学的角度来讨论贪婪是好不好。(如果大家还没有看过本章的引语中提到的那部电影,我可以告诉大家,影片中男主人公的结局并不大好。)才我们算法的角度来看,这个问题应该是,贪婪算法是否是有效的。就像我们将会看到的,的确存在某些类型问题,一系列局部的最优选择对于它们的每一个实例都能够产生一个最优解。然而,还有一些问题并不是这种情况。对于这样的问题,如果我们关心的是,或者说我们能够满足于一个近似解,贪婪算法仍然是有价值的。作为一种规则,贪婪算法看上去既诱人又简单。尽管看上去它们并不复杂,但在这种技术背后有着相当复杂的理论,它是基于一种被称为“拟阵”的抽象组合结构。 一些应用贪婪技术的案例: Prim算法是一种为加权连通图构造最小生成树的贪婪算法。它的工作原理是向前面构造的一颗子树中添加离树中顶点最近的顶点。 Kruskal算法是另一种最小生成树问题的算法它按照权重的增序把边包含进来,以构造一颗最小生成树,并使得这种包含不会产生一条回路。为了保证这种检查的效率,需要应用一种所谓的union-find算法。 Dijkstra算法解决了单起点最短路径问题,该问题要求出从给定的顶点(起点)出发通过加权图或者有向图的其他所有顶点的最短路径。它的工作过程和Prim算法是一样的,不同点在于它比较的是路径的长度而不是边的长度。对于不含负权重的图, Dijkstra算法总是能够产生一个正确的解。 哈夫曼树是一颗二叉树,它使得从根出发到包含一组预定义权重的叶子之间的加权路径长度达到最小。哈夫曼树的最重要的应用是哈夫曼编码。 哈夫曼编码是一种最优的自由前缀变长编码方案,它基于字符在给定文本中的出现频率,把比特串赋给字符。这是通过贪婪地构造一颗二叉树来完成的,二叉树的叶子代表字母表中的字符,而树中的边则标记为0或者1。 回溯法和分支限界法 关注那些不断已被他人成功应用的新思路。你的原创思想只应该应用在那些你正在研究的问题上。 ——托马斯·爱迪生(1847-1931) 回溯和分支限界都是以构造一颗状态空间树为基础的,树的节点反映了对一个部分解所作的特定选择。如果可以保证,节点子孙所对应的选择不可能得出问题的一个解,两种技术都会立即停止处理这个节点。两种技术的区别在于它们能够处理的问题类型不同。分支限界法只能应用于最优问题,因为它基于针对一个问题的目标函数,计算其可能值的边界。回溯法并不受这种要求的制约,但在大多数情况下,它处理的是非优化问题。回溯法和分支限界法的另一个区别在于它们生成状态空间树的节点顺序不同。对于回溯法来说,它的树的生长顺序常常是深度优先的(也就是和DFS类似)。分支限界法可以根据多种规则生成节点,如最佳优先原则。 回溯的主要思想是每次只构造解的一个分量,然后按照下面的方法来评估这个部分构造解。如果一个部分构造解可以进一步构造而不会违反问题的约束,我们就接受对解的下一个分量所做的第一个合法选择。如果无法对下一分量进行合法的选择,就不必在剩下的任何分量再做任何选择了。在这种情况下,该算法进行回溯,把部分构造解的最后一个分量替换为它的下一个选择。通过对所做的选择构造一颗所谓的状态空间树,我们很容易实现这种处理。树的根代表了在查找解之前的初始状态。树的第一层节点代表了对解的第一个分量所做的选择,第二层节点代表了对解的第二个分量所做的选择,以此类推。如果一个部分构造解仍然有可能导致一个完整解,我们说这个部分解在树中的相应节点是有希望的;否则,我们说它是没希望的。叶子则要么代表了没希望的死胡同,要么代表了算法找到的完整解。在大多数情况下,一个回溯算法的状态空间树是按照深度优先的方式来构造的。如果当前节点是有希望的,通过向部分解添加下一个分量的第一个合法选择,就生成了节点的一个子女,而处理也会转向这个子女节点。如果当前节点变得没希望了,该算法回溯到该节点的父母,考虑部分解的最后一个分量的下一个可能选择;如果这种选择不存在,它再回溯到树的上一层,以此类推。最后,如果该算法找到了问题的一个完整解,它要么就停止了(如果只需要一个解),要么回溯之后继续查找其他可能的解。 和回溯法相比,分支限界法需要两个额外的条件: 对于一颗状态空间树的每一个节点所代表的部分解,我们要提供一种方法,计算出通过这个部分解繁衍出的任何解在目标函数上的最佳值边界。 目前求得的最佳解的值。 如果可以得到这些信息,我们可以拿某个节点的边界值和目前求得的最佳解进行比较:如果边界值不能超越(也就是说,在最小化问题中不小于,在最大化问题中不大于)目前的最佳解,这个节点就是一个没有希望的节点,需要立即中止(也有人说把树枝剪掉),因为从这个节点生成的解,没有一个能比目前已经得到的解更好。这就是分支限界技术的主要思想。 一般来说,对于一个分支限界算法的状态空间树来说,只要符合下面三种中的一种原因,我们就会中止掉它的在当前节点上的查找路径: 该节点的边界值不能超越目前最佳解的值。 该节点无法代表任何可行解,因为它已经违反了问题的约束。 该节点代表的可行解的子集只包含一个单独的点(因此无法给出更多的选择)。在这种情况下,我们拿这个可行解在目标函数上的值和目前求得的最佳解进行比较,如果新的解更好一些的话,就用前者替换后者。 一些应用案例: 最近邻居是一种简单的贪婪算法,用来对旅行商问题近似求解。该算法的性能比是没有上界的,哪怕对一种重要的子集——欧几里德图来说,也是如此。 饶树两周也是旅行商问题的一种近似算法,对于欧几里德图来说,它的性能比是2。该算法的基本思想是在围绕最小生成树散步的时候走捷径。 背包问题有一种巧妙贪婪算法,它的基本思想是,按照价值重量比的降序处理输入物品。对于该问题的连续版本来说,该算法总能生成一个精确的最优解。 背包问题的多项式近似方案是一种参数可调的多项式时间算法,可以按照预定义的任意精度生成近似解。 解非线性方程是数值分析中最重要的领域之一。虽然我们没有非线性方程的求根公式(只有少数例外),但有若干算法可以对它们近似求解。 平方法和试位法分别是连续版本的折半查找和插值查找。它们的主要优势在于,算法在每次迭代时,都会把根括在某个区间里。 牛顿法会生成近似根的一个序列,它们都是函数图像的切线在x轴上的截距。如果选择了一个较好的初始近似值,该算法 “八皇后”动态图形的实现 八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。 对于八皇后问题的实现,如果结合动态的图形演示,则可以使算法的描述更形象、更生动,使教学能产生良好的效果。下面是笔者用Turbo C实现的八皇后问题的图形程序,能够演示全部的92组解。八皇后问题动态图形的实现,主要应解决以下两个问题。 1.回溯算法的实现 (1)为解决这个问题,我们把棋盘的横坐标定为i,纵坐标定为j,i和j的取值范围是从1到8。当某个皇后占了位置(i,j)时,在这个位置的垂直方向、水平方向和斜线方向都不能再放其它皇后了。用语句实现,可定义如下三个整型数组:a[8],b[15],c[24]。其中: a[j-1]=1 第j列上无皇后 a[j-1]=0 第j列上有皇后 b[i+j-2]=1 (i,j)的对角线(左上至右下)无皇后 b[i+j-2]=0 (i,j)的对角线(左上至右下)有皇后 c[i-j+7]=1 (i,j)的对角线(右上至左下)无皇后 c[i-j+7]=0 (i,j)的对角线(右上至左下)有皇后 (2)为第i个皇后选择位置的算法如下: for(j=1;j<=8;j++) /*第i个皇后在第j行*/ if ((i,j)位置为空)) /*即相应的三个数组的对应元素值为1*/ {占用位置(i,j) /*置相应的三个数组对应的元素值为0*/ if i<8 为i+1个皇后选择合适的位置; else 输出一个解 } 2.图形存取 在Turbo C语言中,图形的存取可用如下标准函数实现: size=imagesize(x1,y1,x2,y2) ;返回存储区域所需字节数。 arrow=malloc(size);建立指定大小的动态区域位图,并设定一指针arrow。 getimage(x1,y1,x2,y2,arrow);将指定区域位图存于一缓冲区。 putimage(x,y,arrow,copy)将位图置于屏幕上以(x,y)左上角的区域。 3. 程序清单如下 #i nclude #i nclude #i nclude #i nclude char n[3]={0,0};/*用于记录第几组解*/ int a[8],b[15],c[24],i; int h[8]={127,177,227,277,327,377,427,477};/*每个皇后的行坐标*/ int l[8]={252,217,182,147,112,77,42,7};/*每个皇后的列坐标*/ void *arrow; void try(int i) {int j; for (j=1;j<=8;j++) if (a[j-1]+b[i+j-2]+c[i-j+7]==3) /*如果第i列第j行为空*/ {a[j-1]=0;b[i+j-2]=0;c[i-j+7]=0;/*占用第i列第j行*/ putimage(h[i-1],l[j-1],arrow,COPY_PUT);/*显示皇后图形*/ delay(500);/*延时*/ if(i<8) try(i+1); else /*输出一组解*/ {n[1]++;if (n[1]>9) {n[0]++;n[1]=0;} bar(260,300,390,340);/*显示第n组解*/ outtextxy(275,300,n); delay(3000); } a[j-1]=1;b[i+j-2]=1;c[i-j+7]=1; putimage(h[i-1],l[j-1],arrow,XOR_PUT);/*消去皇后,继续寻找下一组解*/ delay(500); } } int main(void) {int gdrive=DETECT,gmode,errorcode; unsigned int size; initgraph(&gdrive,&gmode,""); errorcode=graphresult(); if (errorcode!=grOk) {printf("Graphics error\n");exit(1);} rectangle(50,5,100,40); rectangle(60,25,90,33); /*画皇冠*/ line(60,28,90,28);line(60,25,55,15); line(55,15,68,25);line(68,25,68,10); line(68,10,75,25);line(75,25,82,10); line(82,10,82,25);line(82,25,95,15); line(95,15,90,25); size=imagesize(52,7,98,38); arrow=malloc(size); getimage(52,7,98,38,arrow);/*把皇冠保存到缓冲区*/ clearviewport(); settextstyle(TRIPLEX_FONT, HORIZ_DIR, 4); setusercharsize(3, 1, 1, 1); setfillstyle(1,4); for (i=0;i<=7;i++) a[i]=1; for (i=0;i<=14;i++) b[i]=1; for (i=0;i<=23;i++) c[i]=1; for (i=0;i<=8;i++) line(125,i*35+5,525,i*35+5);/*画棋盘*/ for (i=0;i<=8;i++) line(125+i*50,5,125+i*50,285); try(1);/*调用递归函数*/ delay(3000); closegraph(); free(arrow); } 八皇后问题的串行算法 1 八皇后问题 所谓八皇后问题,是在8*8格的棋盘上,放置8个皇后。要求每行每列放一个皇后,而且每一条对角线和每一条反对角线上不能有多于1个皇后,也即对同时放置在棋盘的两个皇后(row1,column1)和(row2,column2),不允许(column1-column2)=(row1-row2)或者(column1+row1)=(column2+row2)的情况出现。 2 八皇后问题的串行递归算法 八皇后问题最简单的串行解法为如下的递归算法: (2.1)深度递归函数: go(int step,int column) {int i,j,place; row[step]=column; if (step==8) outputresult( ); /*结束递归打印结果*/ else /*继续递归*/ {for(place=1;place<=8;place++) {for(j=1;j<=step;j++) if(collision(j ,row[j],step+1,place)) /*判断是否有列冲突、对角线或反对角线*/ goto skip_this_place; go(step+1,place); skip_this_place:; } } }/* go */ (2.2)主函数: void main( ) {int place,j; for(place=1;place<=8;place++) go(1,place); }/* main */ 八皇后问题的并行算法 该算法是将八皇后所有可能的解放在相应的棋盘上,主进程负责生成初始化的棋盘,并将该棋盘发送到某个空闲的子进程,由该子进程求出该棋盘上满足初始化条件的所有的解。这里,我们假定主进程只初始化棋盘的前两列,即在棋盘的前两列分别放上2个皇后,这样就可以产生8*8=64个棋盘。 1 主进程算法 主进程等待所有的子进程,每当一个子进程空闲的时侯,就向主进程发送一个Ready(就绪)信号。主进程收到子进程的Ready信号后,就向该子进程发送一个棋盘。当主进程生成了所有的棋盘后,等待所有的子进程完成它们的工作。然后向每个子进程发送一个Finished信号,打印出各个子进程找到的解的总和,并退出。子进程接收到Finished信号也退出。 2 子进程算法 每个子进程在收到主进程发送过来的棋盘后,对该棋盘进行检查。若不合法,则放弃该棋盘。子进程回到空闲状态,然后向主进程发送Ready信号,申请新的棋盘;若合法,则调用move_to_right(board,rowi,colj)寻找在该棋盘上剩下的6个皇后可以摆放的所有位置,move_to_right(board,rowi,colj)是个递归过程, 验证是否能在colj列rowi行以后的位置是否能放一个皇后。 1)首先将more_queen设置成FALSE; 以LEAF,TRUE和FLASE区分以下三种情况: A)LEAF:成功放置但是已到边缘,colj现在已经比列的最大值大1,回退两列,检查是否能将待检查皇后放在哪一行:如果能,把more_queen设成TRUE; B)TRUE:成功放置皇后,检查这一列是否能有放置皇后的其他方式,如有,把more_queen设成TRUE; C)FALSE:不能放置,回退一列再试,如果能把more_queen设成TRUE ,如果皇后已在最后一行,必须再检查上一列。 2)如果more_queens=TRUE,仍需再次调用move_to_right(),为新棋盘分配空间,用xfer()将现有棋盘拷贝到nextboard,并进行下列情况的处理: TRUE:得到一个皇后的位置,增大列数再试; FALSE:失败,如果more_queen为真, 取回棋盘,保存上次调用的棋盘。将列数减小,取走皇后,增加行数,再调用move_to_right(); LEAF:得到一种解法,solution增一,将解法写入log_file,由于已到边缘,列数回退1,检查是否放置一个皇后,如果能,新加一个皇后后,调用move_to_right;如果不能,检查more_queen如果more_queen为真,将棋盘恢复到上次调用时保存的棋盘,将待检查的皇后下移,调用move_to_right。 八皇后问题的高效解法-递归版 // Yifi 2003 have fun! : ) //8 Queen 递归算法 //如果有一个Q 为 chess[i]=j; //则不安全的地方是 k行 j位置,j+k-i位置,j-k+i位置 class Queen8{ static final int QueenMax = 8; static int oktimes = 0; static int chess[] = new int[QueenMax];//每一个Queen的放置位置 public static void main(String args[]){ for (int i=0;i= 0) && (chess[i]+k < QueenMax) ) qsave[chess[i]+k]=false; if ( (chess[i]-k >= 0) && (chess[i]-k < QueenMax) ) qsave[chess[i]-k]=false; i++; } //下面榘踩? for(i=0;i   #include   #include   typedef char DataType;/*定义DataType类型*/   typedef enum {Link,Thread}PointerTag;   typedef struct node{   DataType data;   struct node *lchild, *rchild;/*左右孩子子树*/   PointerTag LTag,RTag;   }BiThrNode; /*结点类型*/   typedef BiThrNode *BiThrTree ;/*二叉树类型*/   void CreatBinTree(BiThrTree *T)   { /*构造二叉链表,注意:输入序列是先序序列*/   char ch;   if ((ch=getchar())==' ')   *T=NULL;   else{ /*读入非空格*/   *T=(BiThrNode *)malloc(sizeof(BiThrNode));/*生成结点*/   (*T)->data=ch;(*T)->LTag=Link;(*T)->RTag=Link;   CreatBinTree(&(*T)->lchild); /*构造左子树 */   CreatBinTree(&(*T)->rchild); /*构造右子树*/   }   }   BiThrTree pre;/*全局变量*/   void InThreading(BiThrTree p)   {   if(p)   {InThreading(p->lchild);/*左子树线索化*/   if(!p->lchild){p->LTag=Thread;p->lchild=pre;}/*前驱线索*/   if(!pre->rchild){pre->RTag=Thread;pre->rchild=p;}/*后继线索*/   pre=p;/*保持pre指向p*/   InThreading(p->rchild);/*右子树线索化*/   }   }   int InOrderThreading(BiThrTree *Thrt,BiThrTree T)   /*中序遍厉二叉树T,并将其中序线索化,Thrt指向头结点*/   { if(!(*Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(0);   (*Thrt)->LTag=Link;(*Thrt)->RTag=Thread;/*建头结点*/   (*Thrt)->rchild=*Thrt;/*右指针回指*/   if(!T) (*Thrt)->lchild=*Thrt;   else   { (*Thrt)->lchild=T;pre=*Thrt;   InThreading(T);/*中序遍历进行中序线索化*/   pre->rchild=*Thrt;pre->RTag=Thread;/*最后一个结点线索化*/   (*Thrt)->rchild=pre;   }   return 1;   }   int print(BiThrTree e)   {printf("%d %c %d\n",e->LTag,e->data,e->RTag);return 1;}   int InOrderTraverse(BiThrTree T,int (* visit)(BiThrTree e))   /*T指向头结点,头结点的左链lchild指向根结点,中序遍厉二叉树*/   {BiThrTree p;   p=T->lchild;/*p指向根结点*/   while(p!=T)/*空树或遍厉结束时,p==T*/   {while(p->LTag==Link) p=p->lchild;   if(!visit(p)) return 0;/*打印*/   while(p->RTag==Thread&&p->rchild!=T)   {p=p->rchild;visit(p);}/*访问后继结点*/   p=p->rchild;   }   return 1;   }   void main()   { /*测试程序*/   BiThrTree T,Thrt;   CreatBinTree(&T);   InOrderThreading(&Thrt,T);   InOrderTraverse(Thrt,print);   }   /*可输入"-+a *b -c d /e f "来测试(注意空格)*/ c排序算法大全 2008-03-23 12:53 排序算法是一种基本并且常用的算法。由于实际工作中处理的数量巨大,所以排序算法 对算法本身的速度要求很高。 而一般我们所谓的算法的性能主要是指算法的复杂度,一般用O方法来表示。在后面我将 给出详细的说明。         对于排序的算法我想先做一点简单的介绍,也是给这篇文章理一个提纲。 我将按照算法的复杂度,从简单到难来分析算法。 第一部分是简单排序算法,后面你将看到他们的共同点是算法复杂度为O(N*N)(因为没有使用word,所以无法打出上标和下标)。 第二部分是高级排序算法,复杂度为O(Log2(N))。这里我们只介绍一种算法。另外还有几种 算法因为涉及树与堆的概念,所以这里不于讨论。 第三部分类似动脑筋。这里的两种算法并不是最好的(甚至有最慢的),但是算法本身比较 奇特,值得参考(编程的角度)。同时也可以让我们从另外的角度来认识这个问题。现在,让我们开始吧: 一、简单排序算法 由于程序比较简单,所以没有加什么注释。所有的程序都给出了完整的运行代码,并在我的VC环境 下运行通过。因为没有涉及MFC和WINDOWS的内容,所以在BORLAND C++的平台上应该也不会有什么 问题的。在代码的后面给出了运行过程示意,希望对理解有帮助。 1.冒泡法: 这是最原始,也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡: #include void BubbleSort(int* pData,int Count) { int iTemp; for(int i=1;i=i;j--)                  {                    if(pData[j]10,9,7,8->10,7,9,8->7,10,9,8(交换3次) 第二轮:7,10,9,8->7,10,8,9->7,8,10,9(交换2次) 第一轮:7,8,10,9->7,8,9,10(交换1次) 循环次数:6次 交换次数:6次 其他: 第一轮:8,10,7,9->8,10,7,9->8,7,10,9->7,8,10,9(交换2次) 第二轮:7,8,10,9->7,8,10,9->7,8,10,9(交换0次) 第一轮:7,8,10,9->7,8,9,10(交换1次) 循环次数:6次 交换次数:3次 上面我们给出了程序段,现在我们分析它:这里,影响我们算法性能的主要部分是循环和交换, 显然,次数越多,性能就越差。从上面的程序我们可以看出循环的次数是固定的,为1+2+...+n-1。 写成公式就是1/2*(n-1)*n。 现在注意,我们给出O方法的定义: 若存在一常量K和起点n0,使当n>=n0时,有f(n)<=K*g(n),则f(n) = O(g(n))。(呵呵,不要说没 学好数学呀,对于编程数学是非常重要的!!!) 现在我们来看1/2*(n-1)*n,当K=1/2,n0=1,g(n)=n*n时,1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以f(n) =O(g(n))=O(n*n)。所以我们程序循环的复杂度为O(n*n)。 再看交换。从程序后面所跟的表可以看到,两种情况的循环相同,交换不同。其实交换本身同数据源的 有序程度有极大的关系,当数据处于倒序的情况时,交换次数同循环一样(每次循环判断都会交换), 复杂度为O(n*n)。当数据为正序,将不会有交换。复杂度为O(0)。乱序时处于中间状态。正是由于这样的 原因,我们通常都是通过循环次数来对比算法。 2.交换法: 交换法的程序最清晰简单,每次用当前的元素一一的同其后的元素比较并交换。 #include void ExchangeSort(int* pData,int Count) { int iTemp; for(int i=0;i9,10,8,7->8,10,9,7->7,10,9,8(交换3次) 第二轮:7,10,9,8->7,9,10,8->7,8,10,9(交换2次) 第一轮:7,8,10,9->7,8,9,10(交换1次) 循环次数:6次 交换次数:6次 其他: 第一轮:8,10,7,9->8,10,7,9->7,10,8,9->7,10,8,9(交换1次) 第二轮:7,10,8,9->7,8,10,9->7,8,10,9(交换1次) 第一轮:7,8,10,9->7,8,9,10(交换1次) 循环次数:6次 交换次数:3次 从运行的表格来看,交换几乎和冒泡一样糟。事实确实如此。循环次数和冒泡一样 也是1/2*(n-1)*n,所以算法的复杂度仍然是O(n*n)。由于我们无法给出所有的情况,所以 只能直接告诉大家他们在交换上面也是一样的糟糕(在某些情况下稍好,在某些情况下稍差)。 3.选择法: 现在我们终于可以看到一点希望:选择法,这种方法提高了一点性能(某些情况下) 这种方法类似我们人为的排序习惯:从数据中选择最小的同第一个值交换,在从省下的部分中 选择最小的与第二个交换,这样往复下去。 #include void SelectSort(int* pData,int Count) { int iTemp; int iPos; for(int i=0;i(iTemp=9)10,9,8,7->(iTemp=8)10,9,8,7->(iTemp=7)7,9,8,10(交换1次) 第二轮:7,9,8,10->7,9,8,10(iTemp=8)->(iTemp=8)7,8,9,10(交换1次) 第一轮:7,8,9,10->(iTemp=9)7,8,9,10(交换0次) 循环次数:6次 交换次数:2次 其他: 第一轮:8,10,7,9->(iTemp=8)8,10,7,9->(iTemp=7)8,10,7,9->(iTemp=7)7,10,8,9(交换1次) 第二轮:7,10,8,9->(iTemp=8)7,10,8,9->(iTemp=8)7,8,10,9(交换1次) 第一轮:7,8,10,9->(iTemp=9)7,8,9,10(交换1次) 循环次数:6次 交换次数:3次 遗憾的是算法需要的循环次数依然是1/2*(n-1)*n。所以算法复杂度为O(n*n)。 我们来看他的交换。由于每次外层循环只产生一次交换(只有一个最小值)。所以f(n)<=n 所以我们有f(n)=O(n)。所以,在数据较乱的时候,可以减少一定的交换次数。 4.插入法: 插入法较为复杂,它的基本工作原理是抽出牌,在前面的牌中寻找相应的位置插入,然后继续下一张 #include void InsertSort(int* pData,int Count) { int iTemp; int iPos; for(int i=1;i=0) && (iTemp9,10,8,7(交换1次)(循环1次) 第二轮:9,10,8,7->8,9,10,7(交换1次)(循环2次) 第一轮:8,9,10,7->7,8,9,10(交换1次)(循环3次) 循环次数:6次 交换次数:3次 其他: 第一轮:8,10,7,9->8,10,7,9(交换0次)(循环1次) 第二轮:8,10,7,9->7,8,10,9(交换1次)(循环2次) 第一轮:7,8,10,9->7,8,9,10(交换1次)(循环1次) 循环次数:4次 交换次数:2次 上面结尾的行为分析事实上造成了一种假象,让我们认为这种算法是简单算法中最好的,其实不是, 因为其循环次数虽然并不固定,我们仍可以使用O方法。从上面的结果可以看出,循环的次数f(n)<= 1/2*n*(n-1)<=1/2*n*n。所以其复杂度仍为O(n*n)(这里说明一下,其实如果不是为了展示这些简单 排序的不同,交换次数仍然可以这样推导)。现在看交换,从外观上看,交换次数是O(n)(推导类似 选择法),但我们每次要进行与内层循环相同次数的‘=’操作。正常的一次交换我们需要三次‘=’ 而这里显然多了一些,所以我们浪费了时间。 最终,我个人认为,在简单排序算法中,选择法是最好的。 二、高级排序算法: 高级排序算法中我们将只介绍这一种,同时也是目前我所知道(我看过的资料中)的最快的。 它的工作看起来仍然象一个二叉树。首先我们选择一个中间值middle程序中我们使用数组中间值,然后 把比它小的放在左边,大的放在右边(具体的实现是从两边找,找到一对后交换)。然后对两边分别使 用这个过程(最容易的方法——递归)。 1.快速排序: #include void run(int* pData,int left,int right) { int i,j; int middle,iTemp; i = left; j = right; middle = pData[(left+right)/2]; //求中间值    do{          while((pData[i]middle) && (j>left))//从右扫描大于中值的数                         j--;          if(i<=j)//找到了一对值                        {                         //交换                          iTemp = pData[i];                          pData[i] = pData[j];                          pData[j] = iTemp;                          i++;                          j--;                        } }while(i<=j);//如果两边扫描的下标交错,就停止(完成一次) //当左边部分有值(lefti),递归右半边 if(right>i)            run(pData,i,right); } void QuickSort(int* pData,int Count) { run(pData,0,Count-1); } void main() { int data[] = {10,9,8,7,6,5,4}; QuickSort(data,7); for (int i=0;i<7;i++)             cout< void Bubble2Sort(int* pData,int Count) { int iTemp; int left = 1; int right =Count -1; int t; do {          //正向的部分         for(int i=right;i>=left;i--)                     {                       if(pData[i] void ShellSort(int* pData,int Count) { int step[4]; step[0] = 9; step[1] = 5; step[2] = 3; step[3] = 1; int i,Temp; int k,s,w; for(int i=0;i<4;i++)             {               k = step[i];               s = -k;              for(int j=k;j=0) && (w<=Count))                                       {                                         pData[w+k] = pData[w];                                         w = w-k;                                       }                          pData[w+k] = iTemp;                       }            } } void main() { int data[] = {10,9,8,7,6,5,4,3,2,1,-10,-1}; ShellSort(data,12); for (int i=0;i<12;i++)              cout<=N,符合此条件的最小那个X)。   其时间复杂度为:O(nlogn).所需辅助存储空间为:O(n)   归并算法如下:   long merge(long *A,long p,long q,long r)   {   long n1,n2,i,j,k;   long *L,*R;   n1=q-p+1;   n2=r-q;   L=(long *)malloc((n1+2)*sizeof(long));   R=(long *)malloc((n2+2)*sizeof(long));   for(i=1;i<=n1;i++)   L=A[p+i-1];   for(j=1;j<=n2;j++)   R[j]=A[q+j];   L[n1+1]=R[n2+1]=RAND_MAX;   i=j=1;   for(k=p;k<=r;k++)   {   if(L<=R[j])   {   A[k]=L;   i++;   }   else   {   A[k]=R[j];   j++;   }   }   free(L);   free(R);   return 0;   }   long mergesort(long *A,long p,long r)   {   long q;   if(pk,但n能被k整除,则应打印出k的值,并用n除以k的商,作为新的正 整数你n,重复执行第一步。 (3)如果n不能被k整除,则用k+1作为k的值,重复执行第一步。 ___________________________________________________________________ 程序源代码: /* zheng int is divided yinshu*/ main() { int n,i; printf("\nplease input a number:\n"); scanf("%d",&n); printf("%d=",n); for(i=2;i<=n;i++) { while(n!=i) { if(n%i==0) { printf("%d*",i); n=n/i; } else break; } } printf("%d",n); } 题目:利用条件运算符的嵌套来完成此题:学习成绩>=90分的同学用A表示,60 -89分之间的用B表示,60分以下的用C表示。 __________________________________________________________________ 程序分析:(a>b)?a:b这是条件运算符的基本例子。 ___________________________________________________________________ 程序源代码: main() { int score; char grade; printf("please input a score\n"); scanf("%d",&score); grade=score>=90?'A'score>=60?'B':'C'); printf("%d belongs to %c",score,grade); } 题目:输入两个正整数m和n,求其最大公约数和最小公倍数。 __________________________________________________________________ 程序分析:利用辗除法。 ___________________________________________________________________ 程序源代码: main() { int a,b,num1,num2,temp; printf("please input two numbers:\n"); scanf("%d,%d",&num1,&num2); if(num1  { temp=num1; num1=num2;  num2=temp; } a=num1;b=num2; while(b!=0)/*利用辗除法,直到b为0为止*/ { temp=a%b; a=b; b=temp; } printf("gongyueshu:%d\n",a); printf("gongbeishu:%d\n",num1*num2/a); } 题目:输入一行字符,分别统计出其中英文字母、空格、数字和其它字符的个数 。 __________________________________________________________________ 程序分析:利用while语句,条件为输入的字符不为'\n'. ___________________________________________________________________ 程序源代码: #include "stdio.h" main() {char c; int letters=0,space=0,digit=0,others=0; printf("please input some characters\n"); while((c=getchar())!='\n') { if(c>='a'&&c<='z'||c>='A'&&c<='Z') letters++; else if(c==' ') space++; else if(c>='0'&&c<='9') digit++; else others++; } printf("all in all:char=%d space=%d digit=%d others=% d\n",letters,space,digit,others); } 题目:求s=a+aa+aaa+aaaa+aa...a的值,其中a是一个数字。例如 2+22+222+2222+22222(此时共有5个数相加),几个数相加有键盘控制。 __________________________________________________________________ 程序分析:关键是计算出每一项的值。 ___________________________________________________________________ 程序源代码: main() { int a,n,count=1; long int sn=0,tn=0; printf("please input a and n\n"); scanf("%d,%d",&a,&n); printf("a=%d,n=%d\n",a,n); while(count<=n) { tn=tn+a; sn=sn+tn; a=a*10; ++count; } printf("a+aa+...=%ld\n",sn); } 题目:一个数如果恰好等于它的因子之和,这个数就称为“完数”。例如6=1+2 +3.编程找出1000以内的所有完数。 ___________________________________________________________________ 程序源代码: main() { static int k[10]; int i,j,n,s; for(j=2;j<1000;j++) { n=-1; s=j; for(i=1;i   { if((j%i)==0) { n++; s=s-i; k[n]=i; } } if(s==0) { printf("%d is a wanshu",j); for(i=0;i  printf("%d,",k); printf("%d\n",k[n]); } } } 题目:一球从100米高度自由落下,每次落地后反跳回原高度的一半;再落下, 求它在第10次落地时,共经过多少米?第10次反弹多高? ___________________________________________________________________ 程序源代码: main() { float sn=100.0,hn=sn/2; int n; for(n=2;n<=10;n++) { sn=sn+2*hn;/*第n次落地时共经过的米数*/ hn=hn/2; /*第n次反跳高度*/ } printf("the total of road is %f\n",sn); printf("the tenth is %f meter\n",hn); } 题目:一只猴子摘了N个桃子第一天吃了一半又多吃了一个,第二天又吃了余下的 一半又多吃了一个,到第十天的时候发现还有一个. ___________________________________________________________________ 程序源代码: /* 猴子吃桃问题 */ main() { int i,s,n=1; for(i=1;i<10;i++) { s=(n+1)*2 n=s; } printf("第一天共摘了%d个桃\n",s); } 迭代法求方程根 ___________________________________________________________________ /* 迭代法求一个数的平方根 */ #define Epsilon 1.0E-6 /*控制解的精度*/ #include main() { float a,x0,x1; printf("请输入要求的数:"); scanf("%f",&a); x0=a/2; x1=(x0+a/x0)/2; while(fabs(x1-x0)>=Epsilon) { x0=x1; x1=(x0+a/x0)/2; } printf("%f的平方根:%f.5\n",x1); } /* 上题的另一种算法 */ #define Epsilon 1.0E-6 /*控制解的精度*/ #include #include main() { float num,pre,this; do { scanf("%f",&num);/*输入要求平方根的数*/ }while(num<0); if (num==0) printf("the root is 0"); else { this=1; do { pre=this; this=(pre+num/pre)/2; }while(fabs(pre-this)>Epsilon);/*用解的精度,控制循环次数*/ } printf("the root is %f",this); } 用牛顿迭代法 求方程 2*x*x*x-4*x*x+3*x-6 的根 /* 牛顿迭代法 */ #define Epsilon 1.0E-6 /*控制解的精度*/ #include main() { float x1,x0=1.5; x1=x0-(2*x0*x0*x0-4*x0*x0+3*x0-6)/(6*x0*x0-8*x0+3); while(fabs(x1-x0>=Epsilon) {   x0=x1; x1=x0-(2*x0*x0*x0-4*x0*x0+3*x0-6)/(6*x0*x0-8*x0+3); } printf("方程的根为%f\n",x1); } 用二分法求上题 /* 二分法 */ #define Epsilon 1.0E-5 /*控制解的精度*/ #include main() { folat x1,x2,x0,f1,f2,f0; x0=(x1+x2)/2; f0=2*x0*x0*x0-4*x0*x0+3*x0-6;   /* 求中点的函数值 */ while(fabs(f0)>=Epsilon) { if(f0*f1<0) { x2=x0; f2=2*x2*x2*x2-4*x2*x2+3*x2-6; } if(f0*f2<0) { x1=x0; f1=2*x1*x1*x1-4*x1*x1+3*x1-6; } x0=(x1+x2)/2; f0=2*x0*x0*x0-4*x0*x0+3*x0-6; } printf("用二分法求得方程的根:%f\n",x0); } 题目:打印出如下图案(菱形) * *** ****** ******** ****** *** * ___________________________________________________________________ 程序分析:先把图形分成两部分来看待,前四行一个规律,后三行一个规律,利 用双重for循环,第一层控制行,第二层控制列。 ___________________________________________________________________ 程序源代码: main() { int i,j,k; for(i=0;i<=3;i++) { for(j=0;j<=2-i;j++) printf(" "); for(k=0;k<=2*i;k++) printf("*"); printf("\n"); } for(i=0;i<=2;i++) { for(j=0;j<=i;j++) printf(" "); for(k=0;k<=4-2*i;k++) printf("*"); printf("\n"); } } 题目:一个5位数,判断它是不是回文数。即12321是回文数,个位与万位相同, 十位与千位相同。 ___________________________________________________________________ 程序分析:同29例 ___________________________________________________________________ 程序源代码: main( ) { long ge,shi,qian,wan,x; scanf("%ld",&x); wan=x/10000; qian=x%10000/1000; shi=x%100/10; ge=x%10; if (ge==wan&&shi==qian)/*个位等于万位并且十位等于千位*/ printf("this number is a huiwen\n"); else printf("this number is not a huiwen\n"); } 题目:请输入星期几的第一个字母来判断一下是星期几,如果第一个字母一样, 则继续判断第二个字母。 ___________________________________________________________________ 程序分析:用情况语句比较好,如果第一个字母一样,则判断用情况语句或if语 句判断第二个字母。 ___________________________________________________________________ 程序源代码: #include void main() { char letter; printf("please input the first letter of someday\n"); while ((letter=getch())!='Y') /*当所按字母为Y时才结束*/ { switch (letter) {case 'S':printf("please input second letter\n"); if((letter=getch())=='a') printf("saturday\n"); else if ((letter=getch())=='u') printf("sunday\n"); else printf("data error\n"); break; case 'F':printf("friday\n");break; case 'M':printf("monday\n");break; case 'T':printf("please input second letter\n"); if((letter=getch())=='u') printf("tuesday\n"); else if ((letter=getch())=='h') printf("thursday\n"); else printf("data error\n"); break; case 'W':printf("wednesday\n");break; default: printf("data error\n"); } } } 题目:Press any key to change color, do you want to try it. Please hurry up! ___________________________________________________________________ 程序源代码: #include void main(void) { int color; for (color = 0; color < 8; color++) { textbackground(color); /*设置文本的背景颜色*/ cprintf("This is color %d\r\n", color); cprintf("ress any key to continue\r\n"); getch(); /*输入字符看不见*/ } } 题目:学习gotoxy()与clrscr()函数 ___________________________________________________________________ 程序源代码: #include void main(void) { clrscr(); /*清屏函数*/ textbackground(2); gotoxy(1, 5); /*定位函数*/ cprintf("Output at row 5 column 1\n"); textbackground(3); gotoxy(20, 10); cprintf("Output at row 10 column 20\n"); } 题目:练习函数调用 ___________________________________________________________________ 程序源代码: #include void hello_world(void) { printf("Hello, world!\n"); } void three_hellos(void) { int counter; for (counter = 1; counter <= 3; counter++) hello_world();/*调用此函数*/ } void main(void) { three_hellos();/*调用此函数*/ } 题目:文本颜色设置 ___________________________________________________________________ 程序源代码: #include void main(void) { int color; for (color = 1; color < 16; color++) { textcolor(color);/*设置文本颜色*/ cprintf("This is color %d\r\n", color); } textcolor(128 + 15); cprintf("This is blinking\r\n"); } 题目:求100之内的素数 ___________________________________________________________________ 程序源代码: #include #include "math.h" #define N 101 main() { int i,j,line,a[N]; for(i=2;ia[j]) min=j; tem=a; a=a[min]; a[min]=tem; } /*output data*/ printf("After sorted \n"); for(i=0;iend) a[10]=number; else {for(i=0;i<10;i++) { if(a>number) {temp1=a; a=number; for(j=i+1;j<11;j++) {temp2=a[j]; a[j]=temp1; temp1=temp2; } break; } } } for(i=0;i<11;i++) printf("%6d",a); } 题目:将一个数组逆序输出。 ___________________________________________________________________ 程序分析:用第一个与最后一个交换。 ___________________________________________________________________ 程序源代码: #define N 5 main() { int a[N]={9,6,5,4,1},i,temp; printf("\n original array:\n"); for(i=0;i"); scanf("%d",&num); printf("\40:The square for this number is %d \n",SQ(num)); if(num>=50) again=TRUE; else again=FALSE; } } 题目:宏#define命令练习(2) ___________________________________________________________________ 程序源代码: #include "stdio.h" #define exchange(a,b) { \ /*宏定义中允许包含两道衣裳命令的情形,此时必须在最右边加上"\"*/ int t;\ t=a;\ a=b;\ b=t;\ } void main(void) { int x=10; int y=20; printf("x=%d; y=%d\n",x,y); exchange(x,y); printf("x=%d; y=%d\n",x,y); } 题目:宏#define命令练习(3) ___________________________________________________________________ 程序源代码: #define LAG > #define SMA < #define EQ == #include "stdio.h" void main() { int i=10; int j=20; if(i LAG j) printf("\40: %d larger than %d \n",i,j); else if(i EQ j) printf("\40: %d equal to %d \n",i,j); else if(i SMA j) printf("\40:%d smaller than %d \n",i,j); else printf("\40: No such value.\n"); } 题目:#if #ifdef和#ifndef的综合应用。 ___________________________________________________________________ 程序源代码: #include "stdio.h" #define MAX #define MAXIMUM(x,y) (x>y)?x:y #define MINIMUM(x,y) (x>y)?y:x void main() { int a=10,b=20; #ifdef MAX printf("\40: The larger one is %d\n",MAXIMUM(a,b)); #else printf("\40: The lower one is %d\n",MINIMUM(a,b)); #endif #ifndef MIN printf("\40: The lower one is %d\n",MINIMUM(a,b)); #else printf("\40: The larger one is %d\n",MAXIMUM(a,b)); #endif #undef MAX #ifdef MAX printf("\40: The larger one is %d\n",MAXIMUM(a,b)); #else printf("\40: The lower one is %d\n",MINIMUM(a,b)); #endif #define MIN #ifndef MIN printf("\40: The lower one is %d\n",MINIMUM(a,b)); #else printf("\40: The larger one is %d\n",MAXIMUM(a,b)); #endif } 题目:#include 的应用练习 ___________________________________________________________________ 程序源代码: test.h 文件如下: #define LAG > #define SMA < #define EQ == #include "test.h" /*一个新文件50.c,包含test.h*/ #include "stdio.h" void main() { int i=10; int j=20; if(i LAG j) printf("\40: %d larger than %d \n",i,j); else if(i EQ j) printf("\40: %d equal to %d \n",i,j); else if(i SMA j) printf("\40:%d smaller than %d \n",i,j); else printf("\40: No such value.\n"); } 题目:学习使用按位与 & 。    ___________________________________________________________________ 程序分析:0&0=0; 0&1=0; 1&0=0; 1&1=1 ___________________________________________________________________ 程序源代码: #include "stdio.h" main() { int a,b; a=077; b=a&3; printf("\40: The a & b(decimal) is %d \n",b); b&=7; printf("\40: The a & b(decimal) is %d \n",b); } 题目:学习使用按位或 | 。 ___________________________________________________________________ 程序分析:0|0=0; 0|1=1; 1|0=1; 1|1=1             ___________________________________________________________________ 程序源代码: #include "stdio.h" main() { int a,b; a=077; b=a|3; printf("\40: The a & b(decimal) is %d \n",b); b|=7; printf("\40: The a & b(decimal) is %d \n",b); } 题目:学习使用按位异或 ^ 。    ___________________________________________________________________ 程序分析:0^0=0; 0^1=1; 1^0=1; 1^1=0 ___________________________________________________________________ 程序源代码: #include "stdio.h" main() { int a,b; a=077; b=a^3; printf("\40: The a & b(decimal) is %d \n",b); b^=7; printf("\40: The a & b(decimal) is %d \n",b); } 题目:取一个整数a从右端开始的4~7位。 ___________________________________________________________________   程序分析:可以这样考虑: (1)先使a右移4位。 (2)设置一个低4位全为1,其余全为0的数。可用~(~0<<4) (3)将上面二者进行&运算。 ___________________________________________________________________ 程序源代码: main() { unsigned a,b,c,d; scanf("%o",&a); b=a>>4; c=~(~0<<4); d=b&c; printf("%o\n%o\n",a,d); } 题目:学习使用按位取反~。    ___________________________________________________________________ 程序分析:~0=1; ~1=0; ___________________________________________________________________ 程序源代码: #include "stdio.h" main() { int a,b; a=234; b=~a; printf("\40: The a's 1 complement(decimal) is %d \n",b); a=~a; printf("\40: The a's 1 complement(hexidecimal) is %x \n",a); } 题目:画图,学用circle画圆形。 ___________________________________________________________________ 程序源代码: /*circle*/ #include "graphics.h" main() { int driver,mode,i; float j=1,k=1; driver=VGA;mode=VGAHI; initgraph(&driver,&mode,""); setbkcolor(YELLOW); for(i=0;i<=25;i++) { setcolor(8); circle(310,250,k); k=k+j; j=j+0.3; } } 题目:画图,学用line画直线。 ___________________________________________________________________       程序源代码: #include "graphics.h" main() { int driver,mode,i; float x0,y0,y1,x1; float j=12,k; driver=VGA;mode=VGAHI; initgraph(&driver,&mode,""); setbkcolor(GREEN); x0=263;y0=263;y1=275;x1=275; for(i=0;i<=18;i++) { setcolor(5); line(x0,y0,x0,y1); x0=x0-5; y0=y0-5; x1=x1+5; y1=y1+5; j=j+10; } x0=263;y1=275;y0=263; for(i=0;i<=20;i++) { setcolor(5); line(x0,y0,x0,y1); x0=x0+5; y0=y0+5; y1=y1-5; } } 题目:画图,学用rectangle画方形。    ___________________________________________________________________   程序分析:利用for循环控制100-999个数,每个数分解出个位,十位,百位。 ___________________________________________________________________   程序源代码: #include "graphics.h" main() { int x0,y0,y1,x1,driver,mode,i; driver=VGA;mode=VGAHI; initgraph(&driver,&mode,""); setbkcolor(YELLOW); x0=263;y0=263;y1=275;x1=275; for(i=0;i<=18;i++) { setcolor(1); rectangle(x0,y0,x1,y1); x0=x0-5; y0=y0-5; x1=x1+5; y1=y1+5; } settextstyle(DEFAULT_FONT,HORIZ_DIR,2); outtextxy(150,40,"How beautiful it is!"); line(130,60,480,60); setcolor(2); circle(269,269,137); }   

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 5 金币 [ 分享文档获得金币 ] 5 人已下载

下载文档