ifX(i)=X(k)//在同一列有两个皇后//
orABS(X(i)-X(k))=ABS(i-k)
//在同——条斜角线上//
thenreturn(false)
endif
i←i+1
repeat
return(true)//满足约束//
endPLACE
(3)N皇后问题递归算法分析
使用递归算法使,反复的调用判断函数,判断后在决定位置。
核心算法如下:
publicvoidsetposition(intn)//n表示在第n行,table[n]表示列数
{
for(inti=0;i<=5;i++)//i表示在第i列上放置皇后
{
x[n]=i;
if(place(n)==false)//如果没有皇后在同一列或斜线上(因为是按行依次放置故不可能在同一行上,又因为是每一行是从左到右放置故不可能出现右斜线上有皇后)
{
if(n==5)//棋盘满时输出方案
{
count++;
System.out.println("第"+count+"种解:
");
for(intj=0;j<=5;j++){
System.out.print(x[j]+1+"");
}System.out.println("");
//print();
}
else//一个棋盘未放满时继续放置
setposition(n+1);
}
}
}
三、例子说明
经上机操作,各个经典问题的算法实现实现如下:
1、MaxMin问题
比较10个数字的大小,10,23,45,11,757,2,1236,768,1,-9
比较得出最大值为1236,最小值为-9。
2、矩阵连乘
给定6个矩阵A(30*35),B(35*15),C(15*5),D(5*10),E(10*20)G(20*25)。
3、背包问题
给定3个背包:
三个物品的价值分别为60,120,100,三个物品的质量分别是10,30,20,背包容量为50。
得到装入物品的比例分别为1,2/3,1,总重量为50,最大价值为240.
4、最优装载
船的称重量为20,给定10个物品,重量分别是:
1.0f,5.0f,2.0f,2.0f,4.0f,8.0f,3.0f,1.0f,6.0f,2.0f
5、N皇后问题(非递归)
给定4皇后问题,得到4种解。
6、N皇后问题(递归)
给定6皇后问题,得到4种解。
四、心得体会
学习了栾老师的算法课,解决很多问题,老师说程序=算法+数据结构,首先老师教的知识对于逻辑思维能力有很大帮助,它可以培养我们思考分析问题能力,所谓算法简单来说,就是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,,之前学习,学习了算法的时间空间复杂度分析,之后讲的就是分治法,任何一个可用计算机求解的问题所需要的计算时间都与其规模有关.问题的规模越小,越容易直接求解,解题所需要的时间也越少,分治法的设计思想就是将一个难以解决的大问题,分割成为规模小的问题,分别解决.之后有动态规划问题各种问题,算法是一门基础学科应该学好.对于自己在以后的学习会有很大的帮助.
五、算法对应的例子代码
1、求最大值最小值
/*使用分治法求最大值最小值T(n)=3n/2-2*/
publicclassMaxMin{
staticintcount=0;
publicstaticvoidmain(Stringargs[]){
//实例化对象
MaxMinmaxmin=newMaxMin();
//创建数组
int[]array=newint[]{10,23,45,11,757,2,1236,768,1,-9};
//取得最小值
intmax=maxmin.getMax(array,0,array.length-1);
intmin=maxmin.getMin(array,0,array.length-1);
//输出
System.out.println("最大值是:
"+max);
System.out.println("最小值是:
"+min);
}
/*求最大值*/
publicstaticintgetMax(int[]array,inti,intj){
intMax1=0;
intMax2=0;
if(i==j){
returnMax1=Max2=array[j];
}elseif(i==(j-1)){
Max1=array[i];
Max2=array[j];
returnMax1>Max2?
Max1:
Max2;
}
else{
intmid=(i+j)/2;
Max1=getMax(array,i,mid);
Max2=getMax(array,mid,j);
//count++;
//System.out.println(count);
returnMax1>Max2?
Max1:
Max2;
}
}
/*求最小值*/
publicstaticintgetMin(int[]array,inti,intj){
intMin1=0;
intMin2=0;
if(i==j){
returnMin1=Min2=array[j];
}elseif(i==(j-1)){
Min1=array[i];
Min2=array[j];
returnMin1>Min2?
Min2:
Min1;
}else{
intmid=(i+j)/2;
Min1=getMin(array,i,mid);
Min2=getMin(array,mid,j);
returnMin1>Min2?
Min2:
Min1;
}
}
}
2、矩阵连乘问题
/*矩阵连乘问题,i,r,k的三重循环,时间复杂度为O(n立方)*/
publicclassMatrixChainOrder{
int[]p;//矩阵维数
int[][]m;//最少乘次数
int[][]s;//分割点
intlength;
publicMatrixChainOrder(int[]p,int[][]m,int[][]s){
this.p=p;
this.length=p.length/2;
this.m=m;
this.s=s;
init();
clac();
printM();
}
publicvoidinit(){//m初始化
for(inti=0;im[i][i]=0;
}
}
publicvoidclac(){
for(inti=1;ifor(intj=0;jintr=j+i;//重复计算子问题,长度由1,到length
intt=Integer.MAX_VALUE;//定义当前最大值
for(intk=j;kinttemp=m[j][k]+m[k+1][r]+p[j*2]*p[k*2+1]*p[r*2+1];
if(t>temp){
t=temp;
m[j][r]=temp;
}
}
}
}
}
publicvoidprintM(){
for(inti=0;ifor(intj=0;jSystem.out.print(m[i][j]+"\t");
}
System.out.println();
}
}
publicstaticvoidmain(Stringargs[]){
intp[]={30,35,35,15,15,5,5,10,10,20,20,25};
intlength=6;
int[][]m=newint[6][6];
int[][]s=newint[6][6];
newMatrixChainOrder(p,m,s);
}
}
3、背包问题
/*利用贪心算法,对背包问题的java实现*/
publicclassKnapsack{
privatefloatm;//背包容量
float[]v;//三个物品的价值
float[]w;//三个物品的质量
float[]x;//往背包装东西的比例
intn;//物品个数
double[]p_w_v;//每个物品的单位重量价值
publicKnapsack(){
this.m=50.0f;//背包容量为50
this.v=newfloat[]{60.0f,120.0f,100.0f};//三个物品的价值分别为60,120,100
this.w=newfloat[]{10.0f,30.0f,20.0f,};//三个物品的质量分别是10,30,20,
this.x=newfloat[3];//往背包装东西的比例
this.n=3;//三个物品
this.p_w_v=newdouble[n];//每个物品的单位重量价值
}
//对物品的单位重量价值进行排序
publicvoidsort(intn,float[]v,float[]w)throwsException{
for(inti=0;ip_w_v[i]=v[i]/w[i];//单位重量价值
}
print(p_w_v);
System.out.println("");
Sort(p_w_v,w,v);
print(p_w_v);
}
publicvoidprint(doublea[]){//打印输出数组
intlen=a.length;
for(inti=0;iSystem.out.print(a[i]+"");
}
}
publicvoidprint(Stringstr){//打印输出数组
System.out.print(str+"\n");
}
publicvoidSort(double[]a,float[]b,float[]c){//冒泡排序,实现排序功能
intlen=a.length;//获得数组长度
doubletemp;//临时变量,用于交换值
floatw_temp;
floatv_temp;
for(inti=0;ifor(intj=0;jif(a[j+1]>a[j]){//如果后一下值比前一个值大,则交换两个值的大小,
//以下几行代码是实现数值交换的
temp=a[j+1];//从大到小排序
w_temp=w[j+1];
v_temp=v[j+1];
a[j+1]=a[j];
w[j+1]=w[j];
v[j+1]=v[j];
w[j]=w_temp;
v[j]=v_temp;
}
}
}
}
//贪心算法核心思想
publicvoidknapsack()throwsException{
sort(n,v,w);
inti;
for(i=0;ix[i]=0;
}
floatc=m;
for(i=0;iif(w[i]>c){
break;
}
x[i]=1;
c-=w[i];
}
if(ix[i]=c