java培训一

排序算法

1. 插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。

2. 选择排序(Selection Sort)的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。

3. 冒泡排序的基本思想是：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。

4. 快速排序实质上和冒泡排序一样，都是属于交换排序的一种应用。所以基本思想和上面的冒泡排序是一样的。

void bubbleSort(int[] numlist) // 冒泡排序算法

{

int temp;

for(int j=1;j<;j++)

for(int i=0;i<-j;i++)

if(numlist>numlist[i+1])

{

temp = numlist[i+1];

numlist[i+1] = numlist;

numlist = temp;

}

}

void selectionSort (int[] numlist) //选择排序算法 {

int temp;

for(int i=0;i<-1;i++)

for(int j=i+1;j<;j++)

if(numlist>numlist[j])

{

temp = numlist[j];

numlist[j] = numlist;

numlist = temp;

}

}

0

void insertSort (int[] numlist) //插入排序算法

{

int temp,in,out;

for(out=1;out<;out++)

{

temp=numlist[out];

in=out;

while(in>0 && numlist[in-1]>=temp)

{

numlist[in]=numlist[in-1];

--in;

}

numlist[in]=temp;

}

搜索算法

1. 题目如下：用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"与"5"不能相连。

2. 基本思路： 1 把问题归结为图结构的遍历问题。实际上6个数字就是六个结点，把六个结点连接成无向连通图，对于每一个结点求这个图形的遍历路径，所有结点的遍历路径就是最后对这6个数字的排列组合结果集。 2 显然这个结果集还未达到题目的要求。从以下几个方面考虑： 1. 3，5不能相连：实际要求这个连通图的结点3，5之间不能连通, 可在构造图结构时就满足改条件，然后再遍历图。 2. 不能有重复: 考虑到有两个2，明显会存在重复结果，可以把结果集放在TreeSet中过滤重复结果 3. 4不能在第三位: 仍旧在结果集中去除满足此条件的结果。 采用二维数组定义图结构，最后的代码是：

3. import or;

4. import t;

5.

6. public class TestQuestion {

7.

8. private String[] b = new String[]{"1", "2", "2", "3", "4", "5"};

9. private int n = ;

10. private boolean[] visited = new boolean[n];

11. private int[][] a = new int[n][n];

12. private String result = "";

13. private TreeSet set = new TreeSet();

14.

15. public static void main(String[] args) {

16. new TestQuestion().start();

17. }

18.

19. private void start() {

20.

21. // Initial the map a[][]

22. for (int i = 0; i < n; i++) {

23. for (int j = 0; j < n; j++) {

24. if (i == j) {

25. a[i][j] = 0;

26. } else {

27. a[i][j] = 1;

28. }

29. }

30. }

31.

32. // 3 and 5 can not be the neighbor.

33. a[3][5] = 0;

34. a[5][3] = 0;

35.

36. // Begin to depth search.

37. for (int i = 0; i < n; i++) {

38. irstSearch(i);

39. }

40.

41. // Print result treeset.

42. Iterator it = or();

43. while (t()) {

44. String string = (String) ();

45. // "4" can not be the third position.

46. if (f("4") != 2) {

47. n(string);

48. }

49. }

50. }

51.

52. private void depthFirstSearch(int startIndex) {

53. visited[startIndex] = true;

54. result = result + b[startIndex];

55. if (() == n) {

56. // Filt the duplicate value.

57. (result);

58. }

59. for(int j = 0; j < n; j++) {

60. if (a[startIndex][j] == 1 && visited[j] == false) {

61. depthFirstSearch(j);

62. } else {

63. continue;

64. }

65. }

66.

67. // restore the result value and visited value after listing a node.

68. result = ing(0, () -1);

69. visited[startIndex] = false;

70. }

71. }

2.一个n×n（1<=n<=100）的国际象棋棋盘上放置n个皇后，使其不能相互攻击，即任何两个皇后都不能处在棋盘的同一行、同一列、同一斜线上，试问共有多少种摆法？

3. 枚举法(通常也称穷举法)是指在一个有穷的可能的解的集合中，枚举出集合中的每一个元素，用题目给定的约束条件去判断其是否符合条件，若满足条件，则该元素即为整个问题的解；否则就不是问题的解。

【枚举算法解题必须满足下列条件】

⑴ 可预先确定解元素的个数n，且问题的规模不是很大；

⑵ 对于每个解变量A1，A2，…An的可能值必须为一个连续的值域。

【枚举算法实现】

通常使用嵌套的FOR结构循环语句枚举每个变量的取值，在最里层的循环中判断是否满足给定的条件，若满足则输出一个解。

【枚举算法优化】

⑴ 减少枚举的变量。

在使用枚举法之前，先考虑一下解元素之间的关联，将那些能由已枚举解元素推算出来的变量直接用计算表达式代替。

⑵ 减少枚举变量的值域。

通过各枚举变量间的数学关系定义解元素的值域，在保证不遗漏的情况下越小越好。

⑶ 分解约束条件。

将拆分的约束条件嵌套在相应的循环体间，即尽可能根据约束条件减少变量个数和缩小值域。

习题：

练习1】将1~9这九个数字填入九个空格中。每一横行的三个数字组成一个三位数。如果要使第二行的三位数是第一行的两倍，第三行的三位数是第一行的三倍，应这样填数。如下图所示。

【练习2】一根长29cm的尺子，只允许在上面刻七个刻度，要能用它量出1~29cm的各种长度。试问这刻度应该怎么选择？

【练习3】有4个学生，上地理课时提出我国四大淡水湖的排序如下。

甲：洞庭湖最大，洪泽湖最小，鄱阳湖第三；

乙：洪泽湖最大，洞庭湖最小，鄱阳湖第二，太湖第三；

丙：红泽湖最小，洞庭湖第三；

丁：鄱阳湖最大，太湖最小，洪泽湖第二，洞庭湖第三；

对于各个湖泊应处的地位，每个人只说对了一个。

根据以上情况，编一个程序，让计算机判断各个湖泊应处在第几位。

5. 深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。在深度优先搜索中，对于最新发现的结点，如果它还有以此为起点而未搜过的边，就沿着边继续搜索下去。当结点v的所有边都已被探寻过，搜索将回溯到发现结点v有那条边的始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个过程反复进行直到所有结点都被发现为止

6. 宽度优先搜索算法（又称广度优先搜索算法）是最简单的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijksta单源最短路径算法和Prim最小生成树算法都采用了与宽度优先搜索类似的思想。

宽度优先搜索的核心思想是：从初始结点开始，应用算符生成第一层结点，检查目标结点是否在这些后继结点中，若没有，再用产生式规则将所有第一层的结点逐一扩展，得到第二层结点，并逐一检查第二层结点中是否包含目标结点。若没有，再用算符逐一扩展第二层所有结点……，如此依次扩展，直到发现目标结点为止。

【习题】有两个无刻度的量杯A和B，其容积分别为m升和n升(m>n)，现在允许用量杯从水缸里取水或将水倒回水缸里，而且两个量杯中的水也可以相互倾倒，试设计计算机程序求出在m升的量杯中准确量得k升(

k

【习题】【八数码问题】

九宫格中有8个数码，其中只有一个空，规则是只能把一个数码移动到空的格子中，要求从一个初始状态移动到一个目标状态所要花费的最少步数。如下图

初始状态

2

1

7

8

6

3

4

5

目标状态

1

8

7

【算法分析】

2

6

5

3

4

解决此类问题的办法是宽度搜索，深度搜索耗时太大无法接受。当需要移动的步数很多时，普通的宽度搜索仍旧无法满足需要，需要对其进行优化

【习题】【染色问题】

给定一张无向图，要求对图进行染色，有边相连的点不能染同一种颜色。求最少需要几种颜色可以染完。

递归

1.写一个方法，输入任意一个整数，返回它的阶乘

Java code

/**

*获得任意一个整数的阶乘

*@param n

*@returnn!

*/

public int factorial(int num)

{

//递归

if(num == 1)

{

return 1;

}

return num*factorial(num-1);

}2. 2.写一个方法，用二分查找法判断任意整数在任意整数数组里面是否存在，若存在就返回它在数组中的索引位置，不存在返回-1

**

*二分查找特定整数在整型数组中的位置(递归)

*@param dataset

*@param data

*@param beginIndex

*@param endIndex

*@return index

*/

public int binarySearch(int[] dataset,int data,int beginIndex,int

endIndex){

int midIndex = (beginIndex+endIndex)/2;

//如果查找的数要比开始索引的数据要小或者是比结束索引的书要大，或者开始查找的索引值大于结束的索引值返回-1没有查到

if(data

dataset[endIndex]||beginIndex>endIndex){

return -1;

0000800

}

if(data

return binarySearch(dataset,data,beginIndex,midIndex-1);

}else if(data>dataset[midIndex])

{

return binarySearch(dataset,data,midIndex+1,endIndex);

}else {

return midIndex;

}

}

/**

*二分查找特定整数在整型数组中的位置(非递归)

*@param dataset

*@param data

*@return index

*/

public int binarySearch(int[] dataset ,int data)

{

int beginIndex = 0;

int endIndex = - 1;

int midIndex = -1;

if(data

dataset[endIndex]||beginIndex>endIndex){

return -1;

}

while(beginIndex <= endIndex) {

midIndex = (beginIndex+endIndex)/2;

if(data

endIndex = midIndex-1;

} else if(data>dataset[midIndex]) {

beginIndex = midIndex+1;

}else {

return midIndex;

}

}

return -1;

}

0