发布时间 : 星期四 文章《算法分析与设计》期末复习题更新完毕开始阅读81608668f424ccbff121dd36a32d7375a517c616
.
答：
将规模为N的问题分解为k个规模较小的子问题，使这些子问题相互独立可分别求解，再将k个子问题的解合并成原问题的解。如子问题的规模仍很大，则反复分解直到问题小到可直接求解为止。
在分治法中,子问题的解法通常与原问题相同,自然导致递归过程。
5．请简述减治法的基本思路？ 答：
减治技术利用了一个问题给定实例的解和同样问题较小实例的解之间的某种关系。一旦建立了这种关系，既可以从顶至底（递归地），也可以从底至顶（非递归地）来运用该关系。
减治法有三种主要的变种： ? ? ?
6．请简述递归算法设计的基本思路？ 答：
递归的执行过程由分解过程和求值过程两部分构成。
实际上, 递归思路是把一个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决，再把这些“小问题”进一步分解成更小的“小问题”来解决，如此分解，直至每个“小问题”都可以直接解决(此时分解到递归出口)。
但递归分解不是随意的分解，递归分解要保证“大问题”与“小问题”相似，即求解过程与环境都相似。并且有一个分解的终点。从而使问题可解。
7．请简述变治法的基本思路？ 答：
变治法的技术基于变换思想。变治法分为两个阶段的工作：首先在“变”的阶段，出于这样或那样的原因，将问题的实例变得更容易求解；然后是“治”的阶段，对问题的实例进行求解。
根据对问题实例的变换方式不同，变治法有三种主要的类型： （1）实例化简——变换为同样问题的一个更简单或者更方便的实例； （2）改变表现——变换为同样实力的不同表现；
（3）问题化简——变换为另一个问题的实例，这种问题的算法是已知的。 8．请简述时空权衡法的基本思路？ 答：
时空权衡法的基本思路是对问题的部分或全部输入做预处理，然后对得到的额外信息使用额外的存储空间来存储。通过实现更快或更方便的数据存取，以加速后面问题的求解来提高算法的效率。
四、算法实现题
1．对于任意非负整数n，计算阶乘函数F(n) = n！的值。因为当n ≥ 1时，n！= 1×2×3×……×（n-1）×n = (n-1)！×n。并且根据定义，0！= 1，所以可以使用下面的递归算法计算n！：F(n) = F(n-1) × n。 .
减常数(如1)：:每此迭代规模减小n→n-1 减因子(如1/2)：每此迭代规模减半n→ n/2 减可变规模：每此迭代减小的规模不同
.
请编写Java应用程序，由键盘输入n的值，在屏幕上输出计算的n！的结果。 import java.io.*; public class FN {
static long f(int n) { }
public static void main(String args[]) throws IOException {
//输入N的值
byte[] buf = new byte[10];
System.out.println(\请输入一个整数：\System.in.read(buf); String str=new String(buf); int n=Integer.parseInt(str.trim()); //计算N！的值 long result = f(n); //输出结果
System.out.println(n + \long r = 1; if(n != 0) r = n * f(n-1); return r;
}
}
2．斐波那契数列：0，1，1，2，3，5，8，13，21，34，…… 这个数列可以用一个简单的递推式和两个初始条件来定义： 当n > 1时，F(n) = F(n-1) + F(n-2)
请编写Java应用程序，由键盘输入n的值代表要生成斐波那契数列的项数，在屏幕上输出n项斐波那契数列。 import java.io.*; public class Fb{ .
/*斐波那契数列算法*/ int f(int n){
int r; if(n <= 1)
r = n; F(0) = 0，F(1) = 1
.
}
3．编写基于Java语言的选择排序算法。 /***
* 功能：该算法用选择排序对给定的数组排序 * 输入：一个乱序的整数数组a[ ] * 输出：升序排列的整数数组a[ ] ***/
public void selectionSort (int a[ ]) {
int temp,min;
for(int i=0;i min = i; for(int j=i+1;j min = j; temp = a[i]; a[i] = a[min]; } public static void main(String args[]) throws IOException{ } System.out.println(\请输入所求斐波那契数列的项数：\byte buf[] = new byte[20]; System.in.read(buf); String t1 = new String(buf); int n = Integer.parseInt(t1.trim()); Fb f1 = new Fb(); int b; System.out.println(\输出包含\项的斐波那契数列：\for(int i = 0; i <= n; i++) { } System.out.println(); b = f1.f(i); System.out.print(b + \else r = f(n-1) + f(n-2); return r; . a[min] = temp; } 4．编写基于Java语言的冒泡排序算法。 /*** * 功能：该算法用冒泡排序对给定的数组排序 * 输入：一个乱序的整数数组a[ ] * 输出：升序排列的整数数组a[ ] ***/ public void bubbleSort(int a[ ]) { } 5．编写基于Java语言的顺序查找算法。 /*** * 功能：该算法实现顺序查找功能 * 输入：一个整数数组a[ ]和一个要查找的键值k * 输出：如果在数组中找到k，则返回对应数组元素的下标；如果在数组中找不到k，则返回-1 ***/ public int seqSearch(int a[ ],int k) { } . int i = 0; while((i < a.length ) && ( a[i] != k )) else return -1; i = i + 1; return i; if( i < a.length) int temp; for(int i=0;i for(int j=0;j if(a[j]>a[j+1]) { } temp = a[j+1]; a[j+1] = a[j]; a[j] = temp; }