算法设计与分析实验报告.doc

算法设计与分析实验报告

算法设计与分析报告学生姓名编号专业课指导教师完成时间目录

一.课程内容3

二.算法分析3

1.分治法3(1)分治法的核心思想3(2)最大最小算法分析3

2.动态规划4(1)动态规划的核心思想4(2)矩阵乘法算法分析5

3、贪婪方法5(1)贪婪方法核心思想5(2)背包问题算法分析6(3)装载问题算法分析6

4、回溯法7(1)回溯法核心思想7(2)N皇后问题非递归算法分析7(3)N皇后问题递归算法分析8

三.实施例9的说明

1.最大最小问题9

2.矩阵乘法9

3.背包问题10

4.最佳负载10

5，n皇后问题(非递归)11

6.皇后问题(递归)11

四.经验和体验11

第五，算法对应于示例代码12

1.求最大值和最小值12

2.矩阵乘法问题13

3.背包问题14

4.装载问题17

5，N皇后问题(非递归)18

6.皇后问题(递归)20

一、课程内容

1、分治法，寻找最大值和最小值，最大最小值算法；

2.动态规划、矩阵乘法和求最小乘法数；

3、贪婪方法，1)背包问题，2)装载问题；

4.n皇后问题的回溯法、循环结构算法和递归结构算法。

二、算法分析

1.分而治之(1)当需要解决输入规模为n且n值相当大的问题时，分而治之的核心思想通常很难直接解决

如果问题可以把n个输入分成k个不同的子集，就可以得到k 个不同的独立可解子问题，其中1在包含n个不同元素的集合中同时找到它的最大和最小元素。分而治之战略的设计理念；

如果max1和min1是i1中最大和最小的元素，max2和min2是i2中最大和最小的元素，max1和max2中最大的元素是i1中最大的元素，min1和min2中较小的元素是i1中最小的元素，则将任意实例I=(n，a(1)，…，a(n))分成两个实例。核心算法如下:

程序maxmin(i，j，fmax，fmin)全局n，a[1:n]案例{ i=j:

Fmax←fmin←a[i] *只有一个元素* i=j-

一.课程内容3

二.算法分析3

1.分治法3(1)分治法的核心思想3(2)最大最小算法分析3

2.动态规划4(1)动态规划的核心思想4(2)矩阵乘法算法分析5

3、贪婪方法5(1)贪婪方法核心思想5(2)背包问题算法分析6(3)装载问题算法分析6

4、回溯法7(1)回溯法核心思想7(2)N皇后问题非递归算法分析7(3)N皇后问题递归算法分析8

三.实施例9的说明

1.最大最小问题9

2.矩阵乘法9

3.背包问题10

4.最佳负载10

5，n皇后问题(非递归)11

6.皇后问题(递归)11

四.经验和体验11

第五，算法对应于示例代码12

1.求最大值和最小值12

2.矩阵乘法问题13

3.背包问题14

4.装载问题17

5，N皇后问题(非递归)18

6.皇后问题(递归)20

一、课程内容

1、分治法，寻找最大值和最小值，最大最小值算法；

2.动态规划、矩阵乘法和求最小乘法数；

3、贪婪方法，1)背包问题，2)装载问题；

4.n皇后问题的回溯法、循环结构算法和递归结构算法。

二、算法分析

1.分而治之(1)当需要解决输入规模为n且n值相当大的问题时，分而治之的核心思想通常很难直接解决

如果问题可以把n个输入分成k个不同的子集，就可以得到k 个不同的独立可解子问题，其中1在包含n个不同元素的集合中同时找到它的最大和最小元素。分而治之战略的设计理念；

如果max1和min1是i1中最大和最小的元素，max2和min2是i2中最大和最小的元素，max1和max2中最大的元素是i1中最大的元素，min1和min2中较小的元素是i1中最小的元素，则将任意实例I=(n，a(1)，…，a(n))分成两个实例。核心算法如下:

程序maxmin(i，j，fmax，fmin)全局n，a[1:n]案例{ i=j:

Fmax←fmin←a[i] *只有一个元素* i=j: ifa [i]

fmin←a[i]否则fmax←a[I]；

fmin←a[j]其他:

Mid ←分为两部分*-省略部分-stem . out . println()；}打印()；它不是最后一列，所以寻找下一列K；x[k]=' 0；'找到的值超出界限，

已退回到前一列k-；判断女王是否与布尔位(intk)='='冲突(intj=' 0)；j=5；j)k。j)如果((数学abs(j -数学ABS(x[j]x[k))| |(x[j]='='返回false真实；(int I x[I]=' 0；的公共静态void main(字符串[)参数黄厚='新'皇后1()；黄厚.回溯()；}}

6.n皇后问题(递归)*回溯n皇后问题，递归算法* class queen private int[]x=' new '[6]；count queen()set position(0)；Setposition(int n) n表示行n，table[n]表示列数i) i表示放置皇后x[n]=' I；'如果(place(n)='=false ')如果在同一列或对角线上没有皇后(不可能在同一行，因为它是一个接一个放置的，也不可能在右对角线上有皇后，因为每一行都是从左到右放置的)，如果(n='=' 5)当棋盘满时输出方案计数；出去。println(‘solution :’)；系统输出打印(x[j]1 ' ')；} system . out . println(')；当一个棋盘未满时，继续放置设定位置(n1)；n .如果(x[I]='=x[n]' math . ABS(x[I]x[n])='=' math . ABS(I n))返回1 main(字符串参数[)新皇后()，当放置的皇后在同一列上有一个皇后或在左斜线上有一个皇后；} }单词数据div ≤n，