分治算法流程图

❶ 什么是算法

算法（Algorithm）是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。一个算法应该具有以下五个重要的特征：算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。1、有穷性（Finiteness）算法的有穷性是指算法必须能在执行有限个步骤之后终止2、确切性(Difiniteness)算法的每一步骤必须有确切的定义；3、输入项(Input)一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；4、输出项(Output)一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；5、可行性(Effectiveness)算法中执行的任何计算步都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成。（也称之为有效性）计算机科学家尼克劳斯-沃思曾着过一本着名的书《数据结构十算法= 程序》，可见算法在计算机科学界与计算机应用界的地位。编辑本段算法的复杂度同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。时间复杂度算法的时间复杂度是指执行算法所需要的时间。一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做T(n)=Ο(f(n))因此，问题的规模n 越大，算法执行的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。空间复杂度算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。详见网络词条"算法复杂度"编辑本段算法设计与分析的基本方法1.递推法递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。它把问题分成若干步，找出相邻几步的关系，从而达到目的，此方法称为递推法。2.递归递归指的是一个过程：函数不断引用自身，直到引用的对象已知3.穷举搜索法穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从众找出那些符合要求的候选解作为问题的解。4.贪婪法贪婪法是一种不追求最优解，只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。5.分治法分治法是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。6.动态规划法动态规划是一种在数学和计算机科学中使用的，用于求解包含重叠子问题的最优化问题的方法。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础，被广泛应用于计算机科学和工程领域。7.迭代法迭代法是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或者方程组）的过程，为实现这一过程所使用的方法统称为迭代法。编辑本段算法分类算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法、并行算法。算法可以宏泛的分为三类：有限的，确定性算法 这类算法在有限的一段时间内终止。他们可能要花很长时间来执行指定的任务，但仍将在一定的时间内终止。这类算法得出的结果常取决于输入值。有限的，非确定算法 这类算法在有限的时间内终止。然而，对于一个（或一些）给定的数值，算法的结果并不是唯一的或确定的。无限的算法 是那些由于没有定义终止定义条件，或定义的条件无法由输入的数据满足而不终止运行的算法。通常，无限算法的产生是由于未能确定的定义终止条件。编辑本段举例经典的算法有很多，如："欧几里德算法，割圆术，秦九韶算法"。编辑本段算法经典专着目前市面上有许多论述算法的书籍，其中最着名的便是《计算机程序设计艺术》（The Art Of Computer Programming) 以及《算法导论》（Introction To Algorithms）。编辑本段算法的历史“算法”即算法的大陆中文名称出自《周髀算经》；而英文名称Algorithm 来自于9世纪波斯数学家al-Khwarizmi，因为al-Khwarizmi在数学上提出了算法这个概念。“算法”原为"algorism"，意思是阿拉伯数字的运算法则，在18世纪演变为"algorithm"。欧几里得算法被人们认为是史上第一个算法。 第一次编写程序是Ada Byron于1842年为巴贝奇分析机编写求解解伯努利方程的程序，因此Ada Byron被大多数人认为是世界上第一位程序员。因为查尔斯·巴贝奇(Charles Babbage)未能完成他的巴贝奇分析机，这个算法未能在巴贝奇分析机上执行。 因为"well-defined procere"缺少数学上精确的定义，19世纪和20世纪早期的数学家、逻辑学家在定义算法上出现了困难。20世纪的英国数学家图灵提出了着名的图灵论题，并提出一种假想的计算机的抽象模型，这个模型被称为图灵机。图灵机的出现解决了算法定义的难题，图灵的思想对算法的发展起到了重要作用的。求素数的埃拉托塞尼筛法和求方根的开方的方法公式（算法不等于公式，公式却是提供一种算法）

❷ 算法设计的过程一般是什么样子

您好，楼主
算法设计就是把问题的解决步骤通过计算机编程语言来实现。
大概步骤如下：
1.分析问题：输入什么/输出什么/条件什么/能用什么方法
2.用流程图画出解决方案：决定程序的结构（有三大结构：顺序结构、判断结构、循环结构）
3.算法设计：常见的算法设计方法有：穷举法/迭代法/递推法/递归法/回溯法/贪婪法/分治法。
4.程序设计：这个就需要变成语言来实现的。

❸ 高二数学 算法的概念 在线等！！！！！！！！！！！！！

算法 参考出处：http://blog.csdn.net/ctu_85/archive/2008/05/11/2432736.aspx
一、什么是算法
算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。算法常常含有重复的步骤和一些比较或逻辑判断。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
算法的时间复杂度是指算法需要消耗的时间资源。一般来说，计算机算法是问题规模n 的函数f(n)，算法执行的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。时间复杂度用“O（数量级）”来表示，称为“阶”。常见的时间复杂度有： O（1）常数阶；O（log2n）对数阶；O（n）线性阶；O（n2）平方阶。
算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。
[font class="Apple-style-span" style="font-weight: bold;" id="bks_etfhxykd"]算法 Algorithm [/font]
算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。
一个算法应该具有以下五个重要的特征：
1、有穷性： 一个算法必须保证执行有限步之后结束；
2、确切性： 算法的每一步骤必须有确切的定义；
3、输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；
4、输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
5、可行性： 算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。
算法的设计要求
1）正确性（Correctness）
有4个层次：
A．程序不含语法错误；
B．程序对几组输入数据能够得出满足规格要求的结果；
C．程序对精心选择的、典型的、苛刻的、带有刁难性的几组输入数据能够得出满足规格要求的结果；
D．程序对一切合法的输入数据都能产生满足规格要求的结果。
2）可读性（Readability）
算法的第一目的是为了阅读和交流；
可读性有助于对算法的理解；
可读性有助于对算法的调试和修改。
3）高效率与低存储量
处理速度快；存储容量小
时间和空间是矛盾的、实际问题的求解往往是求得时间和空间的统一、折中。
算法的描述 算法的描述方式（常用的）
算法描述 自然语言
流程图 特定的表示算法的图形符号
伪语言 包括程序设计语言的三大基本结构及自然语言的一种语言
类语言 类似高级语言的语言，例如，类PASCAL、类C语言。
算法的评价 算法评价的标准：时间复杂度和空间复杂度。
1）时间复杂度 指在计算机上运行该算法所花费的时间。用“O（数量级）”来表示，称为“阶”。
常见的时间复杂度有： O（1）常数阶；O（logn）对数阶；O（n）线性阶；O（n＾2）平方阶
2）空间复杂度 指算法在计算机上运行所占用的存储空间。度量同时间复杂度。
时间复杂度举例
（a） X：=X+1 ； O（1）
（b） FOR I：=1 TO n DO
X：= X+1； O（n）
（c） FOR I：= 1 TO n DO
FOR J：= 1 TO n DO
X：= X+1； O（n＾2）
“算法”一词最早来自公元 9世纪 波斯数学家比阿勒·霍瓦里松的一本影响深远的着作《代数对话录》。20世纪的 英国 数学家 图灵 提出了着名的图灵论点，并抽象出了一台机器，这台机器被我们称之为 图灵机 。图灵的思想对算法的发展起到了重要的作用。
算法是 计算机 处理信息的本质，因为 计算机程序 本质上是一个算法，告诉计算机确切的步骤来执行一个指定的任务，如计算职工的薪水或打印学生的成绩单。 一般地，当算法在处理信息时，数据会从输入设备读取，写入输出设备，可能保存起来以供以后使用。
这是算法的一个简单的例子。
我们有一串随机数列。我们的目的是找到这个数列中最大的数。如果将数列中的每一个数字看成是一颗豆子的大小 可以将下面的算法形象地称为“捡豆子”：
首先将第一颗豆子（数列中的第一个数字）放入口袋中。
从第二颗豆子开始检查，直到最后一颗豆子。如果正在检查的豆子比口袋中的还大，则将它捡起放入口袋中，同时丢掉原先的豆子。 最后口袋中的豆子就是所有的豆子中最大的一颗。
下面是一个形式算法，用近似于 编程语言 的 伪代码 表示
给定：一个数列“list"，以及数列的长度"length(list)" largest = list[1] for counter = 2 to length(list): if list[counter] > largest: largest = list[counter] print largest
符号说明:
= 用于表示赋值。即：右边的值被赋予给左边的变量。
List[counter] 用于表示数列中的第 counter 项。例如：如果 counter 的值是5，那么 List[counter] 表示数列中的第5项。
<= 用于表示“小于或等于”。
二、算法设计的方法
1.递推法
递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。设要求问题规模为N的解，当N=1时，解或为已知，或能非常方便地得到解。能采用递推法构造算法的问题有重要的递推性质，即当得到问题规模为i-1的解后，由问题的递推性质，能从已求得的规模为1，2，…，i-1的一系列解，构造出问题规模为I的解。这样，程序可从i=0或i=1出发，重复地，由已知至i-1规模的解，通过递推，获得规模为i的解，直至得到规模为N的解。
【问题】 阶乘计算
问题描述：编写程序，对给定的n（n≤100），计算并输出k的阶乘k！（k=1，2，…，n）的全部有效数字。
由于要求的整数可能大大超出一般整数的位数，程序用一维数组存储长整数，存储长整数数组的每个元素只存储长整数的一位数字。如有m位成整数N用数组a[ ]存储：
N=a[m]×10m-1+a[m-1]×10m-2+ … +a[2]×101+a[1]×100
并用a[0]存储长整数N的位数m，即a[0]=m。按上述约定，数组的每个元素存储k的阶乘k！的一位数字，并从低位到高位依次存于数组的第二个元素、第三个元素……。例如，5！=120，在数组中的存储形式为：
3 0 2 1 ……
首元素3表示长整数是一个3位数，接着是低位到高位依次是0、2、1，表示成整数120。
计算阶乘k！可采用对已求得的阶乘(k-1)！连续累加k-1次后求得。例如，已知4！=24，计算5！，可对原来的24累加4次24后得到120。细节见以下程序。
# include <stdio.h>
# include <malloc.h>
......
2.递归
递归是设计和描述算法的一种有力的工具，由于它在复杂算法的描述中被经常采用，为此在进一步介绍其他算法设计方法之前先讨论它。
能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。
【问题】 编写计算斐波那契（Fibonacci）数列的第n项函数fib（n）。
斐波那契数列为：0、1、1、2、3、……，即：
fib(0)=0;
fib(1)=1;
fib(n)=fib(n-1)+fib(n-2) （当n>1时）。
写成递归函数有：
int fib(int n)
{ if (n==0) return 0;
if (n==1) return 1;
if (n>1) return fib(n-1)+fib(n-2);
}
递归算法的执行过程分递推和回归两个阶段。在递推阶段，把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。例如上例中，求解fib(n)，把它推到求解fib(n-1)和fib(n-2)。也就是说，为计算fib(n)，必须先计算fib(n-1)和fib(n-2)，而计算fib(n-1)和fib(n-2)，又必须先计算fib(n-3)和fib(n-4)。依次类推，直至计算fib(1)和fib(0)，分别能立即得到结果1和0。在递推阶段，必须要有终止递归的情况。例如在函数fib中，当n为1和0的情况。
在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解，例如得到fib(1)和fib(0)后，返回得到fib(2)的结果，……，在得到了fib(n-1)和fib(n-2)的结果后，返回得到fib(n)的结果。
在编写递归函数时要注意，函数中的局部变量和参数知识局限于当前调用层，当递推进入“简单问题”层时，原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层，它们各有自己的参数和局部变量。
由于递归引起一系列的函数调用，并且可能会有一系列的重复计算，递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时，通常按递推算法编写程序。例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法，即从斐波那契数列的前两项出发，逐次由前两项计算出下一项，直至计算出要求的第n项。
【问题】 组合问题
问题描述：找出从自然数1、2、……、n中任取r个数的所有组合。例如n=5，r=3的所有组合为： （1）5、4、3 （2）5、4、2 （3）5、4、1
（4）5、3、2 （5）5、3、1 （6）5、2、1
（7）4、3、2 （8）4、3、1 （9）4、2、1
（10）3、2、1
分析所列的10个组合，可以采用这样的递归思想来考虑求组合函数的算法。设函数为void comb(int m,int k)为找出从自然数1、2、……、m中任取k个数的所有组合。当组合的第一个数字选定时，其后的数字是从余下的m-1个数中取k-1数的组合。这就将求m个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。设函数引入工作数组a[ ]存放求出的组合的数字，约定函数将确定的k个数字组合的第一个数字放在a[k]中，当一个组合求出后，才将a[ ]中的一个组合输出。第一个数可以是m、m-1、……、k，函数将确定组合的第一个数字放入数组后，有两种可能的选择，因还未去顶组合的其余元素，继续递归去确定；或因已确定了组合的全部元素，输出这个组合。细节见以下程序中的函数comb。
【程序】
# include <stdio.h>
# define MAXN 100
int a[MAXN];
void comb(int m,int k)
{ int i,j;
for (i=m;i>=k;i--)
{ a[k]=i;
if (k>1)
comb(i-1,k-1);
else
{ for (j=a[0];j>0;j--)
printf(“%4d”,a[j]);
printf(“\n”);
}
}
}
void main()
{ a[0]=3;
comb(5,3);
}
3.回溯法
回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。
【问题】 组合问题
问题描述：找出从自然数1，2，…，n中任取r个数的所有组合。
采用回溯法找问题的解，将找到的组合以从小到大顺序存于a[0]，a[1]，…，a[r-1]中，组合的元素满足以下性质：
（1） a[i+1]>a，后一个数字比前一个大；
（2） a-i<=n-r+1。
按回溯法的思想，找解过程可以叙述如下：
首先放弃组合数个数为r的条件，候选组合从只有一个数字1开始。因该候选解满足除问题规模之外的全部条件，扩大其规模，并使其满足上述条件（1），候选组合改为1，2。继续这一过程，得到候选组合1，2，3。该候选解满足包括问题规模在内的全部条件，因而是一个解。在该解的基础上，选下一个候选解，因a[2]上的3调整为4，以及以后调整为5都满足问题的全部要求，得到解1，2，4和1，2，5。由于对5不能再作调整，就要从a[2]回溯到a[1]，这时，a[1]=2，可以调整为3，并向前试探，得到解1，3，4。重复上述向前试探和向后回溯，直至要从a[0]再回溯时，说明已经找完问题的全部解。按上述思想写成程序如下：
【程序】
# define MAXN 100
int a[MAXN];
void comb(int m,int r)
{ int i,j;
i=0;
a=1;
do {
if (a-i<=m-r+1
{ if (i==r-1)
{ for (j=0;j<r;j++)
printf(“%4d”,a[j]);
printf(“\n”);
}
a++;
continue;
}
else
{ if (i==0)
return;
a[--i]++;
}
} while (1)
}
main()
{ comb(5,3);
}
4.贪婪法
贪婪法是一种不追求最优解，只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。
例如平时购物找钱时，为使找回的零钱的硬币数最少，不考虑找零钱的所有各种发表方案，而是从最大面值的币种开始，按递减的顺序考虑各币种，先尽量用大面值的币种，当不足大面值币种的金额时才去考虑下一种较小面值的币种。这就是在使用贪婪法。这种方法在这里总是最优，是因为银行对其发行的硬币种类和硬币面值的巧妙安排。如只有面值分别为1、5和11单位的硬币，而希望找回总额为15单位的硬币。按贪婪算法，应找1个11单位面值的硬币和4个1单位面值的硬币，共找回5个硬币。但最优的解应是3个5单位面值的硬币。
【问题】 装箱问题
问题描述：装箱问题可简述如下：设有编号为0、1、…、n-1的n种物品，体积分别为v0、v1、…、vn-1。将这n种物品装到容量都为V的若干箱子里。约定这n种物品的体积均不超过V，即对于0≤i＜n，有0＜vi≤V。不同的装箱方案所需要的箱子数目可能不同。装箱问题要求使装尽这n种物品的箱子数要少。
若考察将n种物品的集合分划成n个或小于n个物品的所有子集，最优解就可以找到。但所有可能划分的总数太大。对适当大的n，找出所有可能的划分要花费的时间是无法承受的。为此，对装箱问题采用非常简单的近似算法，即贪婪法。该算法依次将物品放到它第一个能放进去的箱子中，该算法虽不能保证找到最优解，但还是能找到非常好的解。不失一般性，设n件物品的体积是按从大到小排好序的，即有v0≥v1≥…≥vn-1。如不满足上述要求，只要先对这n件物品按它们的体积从大到小排序，然后按排序结果对物品重新编号即可。装箱算法简单描述如下：
{ 输入箱子的容积；
输入物品种数n；
按体积从大到小顺序，输入各物品的体积；
预置已用箱子链为空；
预置已用箱子计数器box_count为0；
for (i=0;i<n;i++)
{ 从已用的第一只箱子开始顺序寻找能放入物品i 的箱子j；
if （已用箱子都不能再放物品i）
{ 另用一个箱子，并将物品i放入该箱子；
box_count++；
}
else
将物品i放入箱子j；
}
}
上述算法能求出需要的箱子数box_count，并能求出各箱子所装物品。下面的例子说明该算法不一定能找到最优解，设有6种物品，它们的体积分别为：60、45、35、20、20和20单位体积，箱子的容积为100个单位体积。按上述算法计算，需三只箱子，各箱子所装物品分别为：第一只箱子装物品1、3；第二只箱子装物品2、4、5；第三只箱子装物品6。而最优解为两只箱子，分别装物品1、4、5和2、3、6。
若每只箱子所装物品用链表来表示，链表首结点指针存于一个结构中，结构记录尚剩余的空间量和该箱子所装物品链表的首指针。另将全部箱子的信息也构成链表。以下是按以上算法编写的程序。
}
5.分治法
任何一个可以用计算机求解的问题所需的计算时间都与其规模N有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算；n=2时，只要作一次比较即可排好序；n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。
分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
如果原问题可分割成k个子问题（1<k≤n），且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
分治法所能解决的问题一般具有以下几个特征：
（1）该问题的规模缩小到一定的程度就可以容易地解决；
（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
（3）利用该问题分解出的子问题的解可以合并为该问题的解；
（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑贪心法或动态规划法。第四条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。
分治法在每一层递归上都有三个步骤：
（1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
（2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
（3）合并：将各个子问题的解合并为原问题的解。
6.动态规划法
经常会遇到复杂问题不能简单地分解成几个子问题，而会分解出一系列的子问题。简单地采用把大问题分解成子问题，并综合子问题的解导出大问题的解的方法，问题求解耗时会按问题规模呈幂级数增加。
为了节约重复求相同子问题的时间，引入一个数组，不管它们是否对最终解有用，把所有子问题的解存于该数组中，这就是动态规划法所采用的基本方法。以下先用实例说明动态规划方法的使用。
【问题】 求两字符序列的最长公共字符子序列
问题描述：字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一个严格递增下标序列<i0，i1，…，ik-1>，使得对所有的j=0，1，…，k-1，有xij=yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一个子序列。
考虑最长公共子序列问题如何分解成子问题，设A=“a0，a1，…，am-1”，B=“b0，b1，…，bm-1”，并Z=“z0，z1，…，zk-1”为它们的最长公共子序列。不难证明有以下性质：
（

❹ 描述算法的常用方法

1.什么是算法
从字面上来说，算法也就是用于计算的方法。是用来解决某些问题的方法。通过这个方法，可以达到想要的计算结果。它就像我们小时候学些的一些数学公式和解题步骤。
算法，一般有5个特征：

有穷性：
算法的执行步骤、时间、都是有限的。不会无休止的一直执行下去。
确切性：
算法的每一步都必须有明确的定义和描述。
输入：
一个算法应该有相应的输入条件，就像我们小时候做的应用题，已知什么什么。来求某个结果，已知部分便是输入条件。
输出：
算法必须有明确的结果输出。没有结果，那这个算法是没有任何意义的。
可行性：
算法的步骤必须是可行的，无法执行的则没有意义，也解决不了任何问题
2.算法的分类
按照算法的应用来分：算法可以分为基本算法、几何算法、加密/解密算法、查找算法、图标数据分析算法等。
按照算法的思路来分：算法可以分为递推算法、递归算法、穷举算法、分治算法等。

下面，我们就来讲我们的重点之一：也就是算法思想：

3.常用算法思想
穷举算法思想;
递推算法思想;
递归算法思想;
分治算法思想;
概率算法思想;

❺ hadoop中mapper用时间间隔做为key怎么写

从Map到Rece

MapRece其实是分治算法的一种实现，其处理过程亦和用管道命令来处理十分相似，一些简单的文本字符的处理甚至也可以使用Unix的管道命令来替代，从处理流程的角度来看大概如下：
cat input | grep | sort | uniq -c | cat > output # Input -> Map -> Shuffle & Sort -> Rece -> Output
简单的流程图如下：

对于Shuffle，简单地说就是将Map的输出通过一定的算法划分到合适的Recer中进行处理。Sort当然就是对中间的结果进行按key排序，因为Recer的输入是严格要求按key排序的。
Input->Map->Shuffle&Sort->Rece->Output只是从宏观的角度对MapRece的简单描述，实际在MapRece的框架中，即从编程的角度来看，其处理流程是Input->Map->Sort->Combine->Partition->Rece->Output。用之前的对温度进行统计的例子来讲述这些过程。
Input Phase

输入的数据需要以一定的格式传递给Mapper的，格式有多种，如TextInputFormat、DBInputFormat、SequenceFileInput等等，可以使用JobConf.setInputFormat来设置，这个过程还应该包括对输入的数据进行任务粒度划分(split)然后再传递给Mapper。在温度的例子中，由于处理的都是文本数据，输入的格式使用默认的TextInputFormat即可。
Map Phase

对输入的key、value对进行处理，输出的是key、value的集合，即map (k1, v1) -> list(k2, v2)，使用JobConf.setMapperClass设置自己的Mapper。在例子中，将（行号、温度的文本数据）作为key/value输入，经过处理后，从温度的文件数据中提取出日期中的年份和该日的温度数据，形成新的key/value对，最后以list(年, 温度)的结果输出，如[(1950, 10), (1960, 40), (1960, 5)]。
Sort Phase

对Mapper输出的数据进行排序，可以通过JobConf.setOutputKeyComparatorClass来设置自己的排序规则。在例子中，经过排序之后，输出的list集合是按年份进行排序的list(年, 温度)，如[(1950, 10), (1950, 5), (1960, 40)]。
Combine Phase

这个阶段是将中间结果中有相同的key的<key, value>对合并成一对，Combine的过程与Rece很相似，使用的甚至是Rece的接口。通过Combine能够减少<key, value>的集合数量，从而减少网络流量。Combine只是一个可选的优化过程，并且无论Combine执行多少次(>=0)，都会使Recer产生相同的输出，使用JobConf.setCombinerClass来设置自定义的Combine Class。在例子中，假如map1产生出的结果为[(1950, 0), (1950, 20), (1950, 10)]，在map2产生出的结果为[(1950, 15), (1950, 25)]，这两组数据作为Recer的输入并经过Recer处理后的年最高温度结果为(1950, 25)，然而当在Mapper之后加了Combine（Combine先过滤出最高温度），则map1的输出是[(1950, 20)]和map2的输出是[(1950, 25)]，虽然其他的三组数据被抛弃了，但是对于Recer的输出而言，处理后的年最高温度依然是(1950, 25)。
Partition Phase

把Mapper任务输出的中间结果按key的范围划分成R份（R是预先定义的Rece任务的个数），默认的划分算法是”(key.hashCode() & Integer.MAX_VALUE) % numPartitions”，这样保证了某一范围的key一定是由某个Recer来处理，简化了Recer的处理流程，使用JobConf.setPartitionClass来设置自定义的Partition Class。在例子中，默认就自然是对年份进行取模了。
Rece Phase

Recer获取Mapper输出的中间结果，作为输入对某一key范围区间进行处理，使用JobConf.setRecerClass来设置。在例子中，与Combine Phase中的处理是一样的，把各个Mapper传递过来的数据计算年最高温度。
Output Phase

Recer的输出格式和Mapper的输入格式是相对应的，当然Recer的输出还可以作为另一个Mapper的输入继续进行处理。

❻ 学习编程的基础知识，如何做

编程的基础知识包括：
小学、初中、高中基础课程，大学计算机科学专业所有基础课、专业基础课和专业课（杂课不用学）。
如果一般搂一下基础，找些快速入门的书比划比划，也能编。但是要想作为职业，绕不开上面那些知识，每门课涉及到的知识在实际工作中只要遇到，都是迈不过去的坎。

❼ ns结构流程图是什么

NS图是用于取代传统流程图的一种描述方式。 以 SP方法为基础，NS图仅含有下图 的5种基本成分，它们分别表示SP方法的几种标准控制结构。

NS图的优点:

首先，它强制设计人员按SP方法进行思考并描述他的设计方案，因为除了表示几种标准结构的符号之处，它不再提供其他描述手段，这就有效地保证了设计的质量，从而也保证了程序的质量;第二，NS图形象直观，具有良好的可见度。例如循环的范围、条件语句的范围都是一目了然的，所以容易理解设计意图，为编程、复查、选择测试用例、维护都带来了方便;第三，NS图简单、易学易用，可用于软件教育和其他方面。

NS图的缺点:

手工修改比较麻烦，这是有些人不用它的主要原因。

❽ pascal基础知识

一、算法的基础知识
1．用计算机解决问题的步骤：
① 分析问题
② 算法设计
③ 描述算法
④ 编程实现
从上面的求解问题过程可以看出，关键在于前三步的解决：第一步就是解决模型的数据结构，第二步是解决问题的算法，第三步是形式化地描写算法。
2．算法的定义：
算法是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算。算法可以理解为：程序（数据处理）+ 数据结构（数据组织）。
3．算法的性质：
① 有限性
② 确定性
③ 输入输出(可以没有输入，但一定有输出)
④ 可行性
常见的算法有：穷举法、迭代法、递推法、递归法、回溯法、深度及广度搜索法、动态规划、构造法等等。
2.N-S图：
1973年，美国学者I.Nassi和B.Shneiderman提出了一种用图形表示算法的方法，称为N-S流程图。N-S图包括顺序、选择和循环三种基本结构。
3.程序设计语言：
计算机中的语言分为低级语言和高级语言，而低级语言又分为机器语言和汇编语言。
机器语言是一种CPU的指令系统，它是CPU可以识别的一系列有0和1这种二进制代码组成的指令。它依赖于机器，不同类型的计算机有不同的机器语言，机器语言的程序有许多机器指令组成，每条指令由操作码和地址码组成，数据和指令都放在不同的地址单元中。
汇编语言它是一种符号语言，为了克服机器语言固有的缺陷，20世纪50年代中期出现，将难以记忆和辨别的机器语言操作码用有意义的英文单词作为“助记符”来代替0、1进行编程。
高级语言，不再面向机器，而是接近人类的自然语言。常见的还有C/C++，Pascal,Basic,java等。
数据类型、常量、变量及说明方法
数据类型确定了该类型数据项的表示、取值范围以及所能参与的运算。在pascal语言中，无论常量还是变量都必须属于一个确定的数据类型。
Pascal 提供了丰富的数据类型，可以分为三大类：
① 简单类型：分为标准类型（整型、实型、字符型和布尔型）和自定义类型（枚举型和子界型）
② 构造类型：分为数组类型、集合类型、记录类型和文件类型
③ 指针类型
这些数据类型中除了指针类型是动态数据类型外，其他的都是静态数据类型。另外，我们把整型、字符型、布尔型、枚举型和子界型称为顺序类型。

另：数据结构
-栈 队列
– 并查集
– 堆
– 字母树 线段树 平衡树 动态树
– 块状链表
– 后缀数组
– ……

栈
– 先进后出
* 队列
– 先进先出
* 常见的应用有哪些？
– 表达式求值
– 搜索
* 深搜
* 广搜
– 优化

* 集合用代表元表示
– representative?Getfather(x)
* 初始的时候，所有元素各自成为一个集合
– for i?1 to N
* father[i]?i
* 判断是否在同一集合
– 代表元是否相同
* return Getfather(x)=Getfather(y)
* 合并两个集合
– 将其中一集合的代表元指向另一集合代表元
* father[Getfather(x)]?y

并查集
* 如何寻找代表元？
– Getfather(x)
* if father[x]=x
– return x
* return Getfather(father[x])
* 如何优化？
– 路径压缩
* Getfather(x)
– if father[x]=x
>>return x
– father[x]?Getfather(father[x])
– return father[x]

* 用途
– 用于寻找最值
* 大根堆、小根堆
* 小根堆性质
– 是一棵完全二叉树
* i的父亲是谁？
– idiv 2
* i的左右儿子是谁？
– 2i和2i+1
– 树上的每棵子树，儿子的值不小于根
堆排序
– 建堆
– 取出根
– 删除根
– 反复取、删的过程
时间效率
– O(Nlog N)
块状数组
* 增加一下题目内容
– 询问区间最大值
– 询问区间和
– 询问区间内的和最大连续串
– 可以修改一个数
– 可以将一串连续的数变为一个值
– 可以将一串连续的数旋转一下
* 块状数组?块状链表
– 可以将一串连续的数翻转一下

可能有些难

❾ 怎样写流程图才能使raptor随机产生一个1到100的整数

import java.util.Random;
/**
*定义一个具有10个整形元素的数组，随机生成1——100之间的整数初始化数组元
*素：(List实现)
*（1）使用冒泡算法对数组元素进行排序，输出结果。
*（2）除了使用冒泡排序算法之外，请再给出至少3中不同的排序算法。
*/
public class paixu{
public static void main(String[]args){
int[]arr=new int[10];
Random r=new Random();
for(int i=0;i<10;++i){
arr<i>=r.nextInt(100)+1;
System.out.print(arr<i>+"");
}
System.out.println("");
int temp;
int len=arr.length;
for(int i=len-1;i>=1;i--){
for(int j=0;j<i;j++){
if(arr[j]>arr[j+1]){
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
for(int i=0;i<10;i++){
System.out.print(arr<i>+"");
}
}
}
链表法
package com.abc;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
/**
*定义一个具有10个整形元素的数组，随机生成1——100之间的整数初始化数组元
*素：(List实现)
*（1）使用冒泡算法对数组元素进行排序，输出结果。
*（2）除了使用冒泡排序算法之外，请再给出至少3中不同的排序算法。
*/
public class paixu{
public static void main(String[]args){
List<Integer>arr=new ArrayList<Integer>();
Random r=new Random();
for(int i=0;i<10;++i){
arr.add(r.nextInt(100)+1);
}
for(int i=0;i<10;i++){
System.out.print(arr.get(i)+"");
}
System.out.println("");
int temp;
int temp1;
int len=arr.size();
for(int i=len-1;i>=1;i--){
for(int j=0;j<i;j++){
if((int)(arr.get(j))>(int)(arr.get(j+1)))
{
temp=arr.get(j);
temp1=arr.get(j+1);
arr.set(j,temp1);
arr.set(j+1,temp);
}
}
}
for(int i=0;i<10;i++){
System.out.print(arr.get(i)+"-->");
}
}}



(9)分治算法流程图扩展阅读：
特征
使用DllImport属性调用Windows API
通过在“文件”菜单上单击“新建”，然后单击“项目”，打开一个新的“Windows应用程序”项目。出现“新建项目”对话框。
从Visual Basic项目模板的列表中选择“Windows应用程序”。将显示新项目。
将一个名为Button2的按钮添加到启动窗体上。
双击Button2打开窗体的代码视图。
要简化对DllImport的访问，请向启动窗口类的代码顶部添加一条Imports语句：
Visual Basic复制代码
Imports System.Runtime.InteropServices
在End Class语句之前为窗体声明一个空函数，并将函数命名为MoveFile。
将Public和Shared修饰符应用到函数声明中，并基于Windows API函数使用的参数来设置MoveFile的参数：
Visual Basic复制代码
Public Shared Function MoveFile(_
ByVal src As String,_
ByVal dst As String)_
As Boolean
'Leave the body of the function empty.
End Function
函数可以有任意一个有效的过程名；DllImport属性指定DLL中的名称。它还为参数和返回值处理互操作封送处理，因此可以选择与API使用的数据类型相似的Visual Studio数据类型。
将DllImport属性应用到空函数中。
第一个参数是包含要调用的函数的DLL的名称和位置。不必为位于Windows系统目录下的文件指定路径。
第二个参数是一个命名参数，指定Windows API中的函数名称。在本示例中，DllImport属性强制将MoveFile调用转发给KERNEL32.DLL中的MoveFileW。MoveFileW方法将文件从路径src复制到路径dst。

❿ 什么叫算法算法有哪几种表示方法

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

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

(10)分治算法流程图扩展阅读

算法中的“分治法”

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

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