算法实验报告(3)

算法设计与分析实验报告

if(load>n){ k++;

load=v[i-1];//load大于n所以加油点必在i-1 n=n+load; }

System.out.println(\最少加\次油\} }

public static void main(String []args){ qiyou s=new qiyou();

s.greedy(v, n, N);//改这个就能测试 } }

实验四 回溯法

一、实验目的

1．掌握能用回溯法求解的问题应满足的条件； 2．加深对回溯法算法设计方法的理解与应用； 3．锻炼学生对程序跟踪调试能力；

4．通过本次实验的练习培养学生应用所学知识解决实际问题的能力。

二、实验内容

1、对于一个n位正整数a，去掉其中任意k(k<=n)个数字后，剩下的数字按原次序排列可以组成一个新的

正整数。设计一个删数算法，使得剩下的数字组成的正整数最小

2、n皇后问题 三、实验要求。

（1）用回溯法算法设计方法求解问题； （2）上机实现所设计的算法；

（3）分析所设计的算法的时间/空间复杂性。

四、实验过程设计（算法设计过程）

1、一个n位数，删去k位后，也就是剩下一个 n-k位 数，那么这个数要最小，我们就要保证我们我们得出的数是所有删除后得到的数的最小值。问题转换一下，用回溯法的思想如果最后就剩下一位，结果就是这些数字的最小值，最后剩下两位在这个区间（从左往右数第一位，从右往左数第二位），且是其中的最小值，而次最高位在这个区间（刚才最高位+1，从右往左数第一位即是最后一位）；

2、n皇后问题中用完全n叉树表示解空间，约束place减去不满足行列和斜线约束的子树。递归方法backtrack（1）实现对整个解空间的回溯搜索。Backtrack（i）搜索解空间中第i层子树，sum记录当前已找到的可行方案数。

2015-2016学年 第一学期

算法设计与分析实验报告

五、实验结果分析

(1)

例如输入1 7 4 0 9 4 8 8 2 4 5 5 长度为12，删完剩下5.

时间复杂度:0（k*(n-k)）

（2）当a=8即8皇后问题时结果为： sum=98 时间复杂度为o(n!)

六、实验体会

在这个实验中给我印象最深的是n皇后问题，只有n大于三才能进行，并且还有递归和非递归两种形态，而且多个函数的关联最让我着迷，应用backtrack来进行回溯算法，用place来进行判断，环环相扣，使人深陷其中，通过这次实验让我提升了自己的动手能力和对回溯算法的理解能力，最重要的还是老师教的好。 七、附录：（源代码） (1)#include using namespace std ; const int K = 5 ; const int size = 12 ;

void GetMinBit( int * data,int length,int start,int end,int &bit ) {

if( data != NULL || length < 1 ) {

if( 0 <= start && start <= end && end < length ) { int min = *(data+start) ; bit = start;

for( int i=start ; i <= end ; i++ ) { if( *(data+i) < min ) {

2015-2016学年 第一学期

算法设计与分析实验报告

min = *(data+i); bit = i; } } } else

{ cout<<\ system(\ } } else

{ cout<<\ system(\ } }

int GetMinData(int * data,int length,int k ) { if( data != NULL || length < 1 ) {if( 0 <= k && k < length ) { int result = 0 ; int bit = -1 ; int end = k ;

while( end

GetMinBit( data,length,bit+1,end,bit );

result = result*10 + *(data+bit); end++ ; }

return result ; } else {

cout<<\ system(\ } } else {

cout<<\ system(\ } }

int main()

{ int * data = new int[size];

2015-2016学年 第一学期

算法设计与分析实验报告

for(int i= 0 ;i

*(data+i)=rand(); }

for(int j= 0 ;j

cout<<*(data+j)<<\ }

cout<

cout<<\ system(\ return 0; }

(2)递归public static long nQueen(int a) { n=a;sum=0; if(n<3) System.out.println(\皇后问题不可行！\ x=new int[n+1]; for(int i=0;i<=n;i++)x[i]=0; backtrack(1); return sum; } private static boolean place(int k) { for(int j=1;jn)sum++; else for(int i=1;i<=n;i++){x[t]=i;if(place(t))backtrack(t+1); } }

非递归public class NQueen2 { static int n; static int[]x; static long sum;

public static long nQueen(int a) { n=a;sum=0; if(n<3) System.out.println(\皇后问题不可行！\ x=new int [n+1];

2015-2016学年 第一学期

算法设计与分析实验报告

for(int i=0;i<=n;i++)x[i]=0; backtrack(); return sum; }

private static boolean place(int k) { for(int j=1;j

private static void backtrack() { x[1]=0; int k=1; while(k>0){ x[k]+=1; while((x[k]<=n)&&!(place(k)))x[k]+=1; if(x[k]<=n) if(k==n)sum++; else{k++;x[k]=0;} else k--; } } }

2015-2016学年 第一学期