算法的设计方法

‘壹’ 算法的常用设计方法有哪些

算法设计是一件非常困难的工作，经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等等。
另外，为了更简洁的形式设计和藐视算法，在算法设计时又常常采用递归技术，用递归描述算法。

‘贰’ 如何设计算法

设计一个正确的算法是一件困难的工作，因为它需要创新，从以太真空中发掘出一个解方案来解决问题。算法设计比对现有的方案进行改良要难得多，因为算法设计的可选择空间太，过多的自由反而成了一种约束。 This book is designed to make you a better algorithm designer. The techniques presented in Part I of this book provide the basic ideas underlying all combinatorial algorithms. The problem catalog of Part II will help you with modeling your application and point you in the right direction of an algorithm or implementation. However, being a successful algorithm designer requires more than book knowledge; it requires a certain attitude, the right problem-solving approach. It is difficult to teach this mindset in a book; yet getting it is essential to become a successful designer. 本书的设计目标是让你成为一个更好的算法设计者。本书第一部分展示有关组合算法的基本原理和基本思想；第二部分的问题清单帮助你为你的问题建模，并且为你指明实现正确算法的方向。尽管如此，要成为一个成功的算法设计者光有书本知识是不够的，面对问题的态度（attitude）和选择正确的方法更重要。书本容易传授知识，很难传授人的心态（mindset)和思考方式；而这种心态和思考却是成为成功的算法设计者的根本条件。 The key to algorithm design (or any other problem-solving task) is to proceed by asking yourself a sequence of questions to guide your thought process. What if we do this? What if we do that? Should you get stuck on the problem, the best thing to do is move onto the next question. In any group brainstorming session, the most useful person in the room is the one who keeps asking, ``Why can't we do it this way?'' not the person who later tells them why. Because eventually she will stumble on an approach that can't be shot down. 算法设计（或其它问题解决任务）的关键是一系列持续的自我反问，这些反问引导我们思维的前进。“如果这样做会怎样？”，“如果那样做又会怎样？”……如果 你被一个问题掐住了，最好的办法就是先搁一下，换一个问题换一个前进的方向试试。在每组头脑风暴会议中，最有价值的人是不断提出为什么的人，不是尔后解说为什么的人。因为我们常常被一些习以为常的东西所拌倒，掉进自己设置的陷阱。 kemin：如果问题解决是一种思考过程，那么思考的形式（过程的严谨性、细致性和正确性）很重要，而思考的内容也不容忽视。因为引导我们思考前进的方式 除反问本身外，反问的内容也很重。就比如参加头脑风暴的材料一样。人大脑的思维功能是硬编码的，人与人之间没有思维规律——质的区别，只是思维的清晰度和 灵敏度——量的差别。人与人之间智力的差别更多体现在思维内容的量上，体现在对外部世界的事实掌握的广度和深度上。 Towards this end, we provide below a sequence of questions to guide your search for the right algorithm for your problem. To use it effectively, you must not only ask the questions, but answer them. The key is working through the answers carefully, by writing them down in a log. The correct answer to, ``Can I do it this way?'' is never ``no,'' but ``no, because ....'' By clearly articulating（明确有力地表达） your reasoning as to why something doesn't work, you can check if it really holds up or whether you have just glossed（掩盖） over a possibility that you didn't want to think hard enough about. You will be surprised how often the reason you can't find a convincing（使人信服的） explanation for something is because your conclusion is wrong. 在末尾我们提供一个反问问题的列表，你不但要反问自己这些问题，更重要是仔细回答这些问题，最好把答案写下来。回答诸如问题“我可以使用这种方式吗？”的 不是一个“不能”就完了，而是“不能，因为……”。通过仔细明确的回答“为什么不能”时，你会发现到底是“真的不能“，还是只是你自己不愿意去深入思考掩 盖了”能“。如果你不曾训练出严谨的思考方式，当你这样做时你会惊讶的发现，为了说明某些东西但却找不到一个令人信服的解释的原因常常是因为你的结论本身 是错的。 An important distinction to keep aware of ring any design process is the difference between strategy and tactics（战略）. Strategy represents the quest for the big picture, the framework around which we construct our path to the goal. Tactics are used to win the minor battles we must fight along the way. In problem solving, it is important to check repeatedly whether you are thinking on the right level. If you do not have a global strategy of how you are going to attack your problem, it is pointless to worry about the tactics. 在设计过程中特别重要区分策略和战略的概念。策略是对全局的一个探索，一个构筑通向目标路径的指导框架。战略则是用来解决通向大目标过程的较小的问题。如果你对关于如何对付所面临的问题没有一个全局的策略，那关心战略是不得要领的，予事无补的。在解题领域，不断修正思维的层次（thinking on the right level）是很重要战略。（--莱布尼兹曾经将人的解题思考过程比喻成晃筛子，把脑袋里面的东西都给抖落出来，然后正在搜索的注意力会抓住一切细微的、与问题有关的东西。事实上，要做到能够令注意力抓住这些有关的东西，就必须时刻将问题放在注意力层面，否则即使关键的东西抖落出来了也可能没注意到。） An example of a strategic question is, ``How best can I model my application as a graph algorithm problem?'' A tactical question might be, ``Should I use an adjacency邻接 list or adjacency matrix data structure to represent my graph?'' Of course, such tactical decisions are critical to the ultimate quality of the solution, but they can be properly evaluated only in light of a successful strategy. 一个策略问题的例子是：“我如何才能更好地把我的问题建模成图问题？”。而一个战略问题可能是这样：“我是用邻接列表还是邻接矩阵来实现我的图结构？”。当然，这种战略选择是对解决方案的最终质量起着重要作用；不过战略价值的体现还是基于正确的策略的选择。 When faced with a design problem, too many people freeze up in their thinking. After reading or hearing the problem, they sit down and realize that they don't know what to do next. They stare（凝视） into space, then panic（惊惶）, and finally end up settling（沉淀; 决定） for the first thing that comes to mind. Avoid this fate（天数; 运气; 命运 ）. Follow the sequence of questions provided below and in most of the catalog problem sections. We'll tell you what to do next! 初学者在面对问题时常常表现出思维凝滞、手足无措和盲目解题。参考以下的反问问题列表和本书的问题清单，我们告诉你应该怎么做。 Obviously, the more experience you have with algorithm design techniques such as dynamic programming, graph algorithms, intractability, and data structures, the more successful you will be at working through the list of questions. Part I of this book has been designed to strengthen this technical background. However, it pays to work through these questions regardless of how strong your technical skills are. The earliest and most important questions on the list focus on obtaining a detailed understanding of the problem and do not require specific expertise. 当然本反问问题列表对读者有背景要求，要求读者对算法设计技术（动态规划、图算法、难解性和数据结构）的熟悉程度。本书第一部分的目标就是对这些技术背景进行强化。不过，不管你的技术背景怎样，通读这些问题对你解题还是很有裨益的。

‘叁’ 算法的设计原则是什么

1.穷举算法思想

穷举算法思想就是从所有的可能结果中一个一个的试验，知道试出正确的结果。具体的操作步骤如下：

1)对每一种可能的结果，计算其结果；

2)判断结果是否符合题目要求，如果符合则该结果正确，如果不符合则继续进行第1)步骤。

穷举算法思想的经典例子为鸡兔同笼为题（又称龟鹤同笼问题），题目为“一个笼子里有鸡兔，共15个头、46条腿，问鸡兔各有多少只？”。代码如下：

public static void main(String[] args) {

int head = 0;
int leg = 0;
System.out.println( "输入鸡兔头数：");
Scanner input=new Scanner(System.in);
head = input.nextInt();
System.out.println( "输入鸡兔腿数：");
Scanner input1=new Scanner(System.in);
leg = input1.nextInt();

boolean existence = false;
for( int i = 0; i <= head; i++){
if( 2 * i + 4 * ( head - i) == leg){
System.out.println( "鸡的个数 :" + i);
System.out.println( "兔的个数 :" + ( head - i));
existence = true;
}
}

if( !existence){
System.out.println( "你输入的数据不正确");
}
}

2.递推算法思想

递推算法算法就是根据已知条件，利用特定关系推导出中间推论，直到得到结果的算法。

递推算法思想最经典的例子是斐波那契数列 : 1,1,2,3,5,8,13......

上面的数列符合F(n) = F(n-1) + F(n-2).代码如下：

public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n = input.nextInt();
System.out.println( fibonacci( n));
}

public static int fibonacci( int n){
if( n == 1){
return 1;
}else if( n == 2){
return 1;
}else{
return fibonacci( n - 1) + fibonacci( n - 2);
}
}

3.递归算法思想

递归算法思想是把大问题转换成同类问题的子问题，然后递归调用函数表示问题的解。

在使用递归的时候一定要注意调回递归函数的终止条件。

递归算法比较经典的例子是求阶乘。代码如下：

public static void main(String[] args) {
System.out.println( "输入一个大于零的数：");
Scanner input=new Scanner(System.in);
int n = input.nextInt();
System.out.println( factorial( n));
}

public static int factorial( int n){
if( n == 0){
return 1;
}else if( n == 1){
return 1;
}else{

‘肆’ 迭代法，二分法，牛顿迭代法，弦截法的算法设计思想

1)迭代法设计思想最简单：x=f(x) 但这种方法初值很主要，不然容易发散。
2)二分法设计思想是先给定区间[a,b]，要求f(a)与f(b)是异号，保证区间内与x轴有交点，求x=(a+b)/2，求f(x)，检查f(x)与f(a)是否同号，如果是同号，把x当成新的a，否则把x当成新的b，得到新的区间，重复求a和b的中点的值，判断与f(a)是否同号，不断循环下去，直到达到精度为止。
3)牛顿迭代法设计思想是对f(x0)某点求切线，与x轴交x1点后，把x1当成x0，再求出其相应新的f(x0)，再对其求切线，找到与x轴的新交点，不断循环下去，直到达到精度为止。这种方法要求先对函数求一阶导数，然后再迭代：x1=x0-f(x0)/f‘(x0)
4)弦截法设计思想利用插值原理，避免上面的求导，要求在f(x)上取二点x0,x1，做过f(x0),f(x1)的直线交x轴一点为x，把原来的x1当成x0，把x当成x1，再重复上面的做直线的过程，不断循环下去，直到达到精度为止。迭代公式：x=x1-(x1-x0)*f(x1)/(f(x1)-f(x0))

‘伍’ 设计算法的原则

设计算法的原则：

1、正确性：算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需要、能够得到问题的正确答案。

2、可读性：设计算法的目的，一方面是为了让计算机执行，但还有一个重要的目的就是为了便于他人的阅读，让人理解和交流，自己将来也可阅读。如果可读性不好，时间长了自己都不知道写了什么，可读性是评判算法（也包括实现它的程序代码）好坏很重要的标志。

3、健壮性：当输入的数据非法时，算法应当恰当地做出反应或进行相应处理，而不是莫名其妙的输出结果。并且处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便于在更高的抽象层次上进行处理。

4、高效率与低存储量：通常，算法的效率指的是算法的执行时间；算法的存储量指的是算法执行过程中所需要的最大存储空间，两者的复杂度都与问题的规模有关。算法分析的任务是对设计的每一个具体的算法，利用数学工具，讨论其复杂度，探讨具体算法对问题的适应性。

(5)算法的设计方法扩展阅读：

算法的“正确”通常在用法上有很大的差别，大体分为以下4个层次：

1、算法程序没有语法错误；

2、算法程序能够根据正确的输入的值得到满足要求的输出结果；

3、算法程序能够根据错误的输出的值满足规格说明的输出结果；

4、算法程序对于精心设计、极其刁难的测试数据都能满足要求的输出结果。

对于这4层含义，层次要求最低，因为仅仅没有语法错误实在谈不上是好的算法。而层次（4）是最困难的，人们几乎不可能逐一验证所有的输入都得到正确的结果。因此，算法的正确性在大部分情况下都不可能用程序来证明，而是用数学方法证明的。

‘陆’ 算法设计的过程一般是什么样子

和你做数学题目的过程一样，已知条件是什么？已知量是什么？要求什么？需要输出一个什么结果？

算法设计就是把问题解决步骤用计算机编程语言来表示出来

‘柒’ 什么叫算法算法有哪几种表示方法

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。计算机科学家往往将“算法”一词的含义限定为此类“符号算法”。“算法”概念的初步定义：一个算法是解决一个问题的进程。而并不需要每次都发明一个解决方案。

已知的算法有很多，例如“分治法”、“枚举测试法”、“贪心算法”、“随机算法”等。

(7)算法的设计方法扩展阅读

算法中的“分治法”

“分治法”是把一个复杂的问题拆分成两个较为简单的子问题，进而两个子问题又可以分别拆分成另外两个更简单的子问题，以此类推。问题不断被层层拆解。然后，子问题的解被逐层整合，构成了原问题的解。

高德纳曾用过一个邮局分发信件的例子对“分治法”进行了解释：信件根据不同城市区域被分进不同的袋子里；每个邮递员负责投递一个区域的信件，对应每栋楼，将自己负责的信件分装进更小的袋子；每个大楼管理员再将小袋子里的信件分发给对应的公寓。

‘捌’ 算法设计方法的内容简介

《算法设计方法》共分为8章。第1章介绍了算法的基本概念以及算法描述和算法分析的基本知识。第2章至第7章分别论述了分治与递归算法、散列与凝聚算法、贪心算法、动态规划算法、回溯算法和分支限界算法。在每一章的开头，都先对相应的典型算法的基本思路进行详细、清晰的阐述，然后通过多种实际问题的求解，对该典型算法的设计方法作进一步的剖析。第8章对NP完全问题的基本理论进行讨论，并介绍了求解NP困难问题的近似算法和概率算法。

‘玖’ 算法设计有哪些方法

算法设计常用的几种方法是
1.
穷举法
2.
贪心法
3.
分治法
4.
回溯法
5.
分枝限界法
6.
动态规划法