算法设计.docx
《算法设计.docx》由会员分享，可在线阅读，更多相关《算法设计.docx（32页珍藏版）》请在冰点文库上搜索。
算法设计
常熟理工学院
《算法设计与分析》实验指导与报告书
____2014-2015______学年第__2__学期
专业：
信息与计算科学
学号：
040612127
姓名：
杨俊
实验地点：
N6-505
指导教师：
唐志强
数学与统计学院
实验目录
实验1算法基础2
实验2排序问题5
实验3最近对问题8
实验4Warshall算法和Floyd算法11
实验5最优二叉查找树14
实验6Huffman编码17
实验7装载问题20
实验8综合实验（实验考核）23
实验1算法基础
实验目的
1．了解算法的基本构造和分析方法，会用大O符号分析算法的时间复杂性，
理解相同的问题可由不同的算法解决，算法的思路不同，时间复杂性也不同；
2.理解递归算法和非递归算法的区别，对简单的问题能分别设计递归算法和非递归算法；
3.会用JAVA语言实现算法。
预习内容
1．什么是算法的？
算法的复杂度分析指什么？
算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。
通俗点说，就是计算机解题的过程。
在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。
前者是推理实现的算法，后者是操作实现的算法。
算法分析的目的在于选择合适算法和改进算法。
一个算法的评价主要从时间复杂度和空间复杂度来考虑。
2．递归算法和非递归算法的区别？
递归算法是一种直接或者间接地调用自身的算法。
在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。
递归算法解决问题的特点：
（1）递归就是在过程或函数里调用自身。
（2）在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
（3）递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。
所以一般不提倡用递归算法设计程序。
（4）在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。
递归次数过多容易造成栈溢出等。
所以一般不提倡用递归算法设计程序。
实验内容
1.设计出求斐波那契数列的两种非递归算法。
2．给定已经排好序的n个元素的数组，设计二分搜索方法的递归算法。
3.求两个自然数m和n的最大公约数（GreatestCommonDivisor）。
（1）设计出尽可能多的的求最大公约数的算法；
（2）采用JAVA语言实现算法，利用计数法记录基本语句的执行次数；
（3）采用大O符号分析算法的时间复杂性；
实验提示：
实验题3
（1）欧几里得算法
（2）分解质因数算法
将m分解质因数；将n分解质因数；提取m和n中的公共质因数；将m和n中的公共质因数相乘，乘积作为结果输出；
（3）stein算法
如果An=Bn,那么An（或Bn）*Cn是最大公约数,算法结束
如果An=0，Bn是最大公约数，算法结束
如果Bn=0，An是最大公约数，算法结束
设置A1=A、B1=B和C1=1
如果An和Bn都是偶数，则An+1=An/2，Bn+1=Bn/2，Cn+1=Cn*2（注意，乘2只要把整数左移一位即可，除2只要把整数右移一位即可）
如果An是偶数，Bn不是偶数，则An+1=An/2，Bn+1=Bn，Cn+1=Cn
如果Bn是偶数，An不是偶数，则Bn+1=Bn/2，An+1=An，Cn+1=Cn
如果An和Bn都不是偶数，则An+1=|An-Bn|/2，Bn+1=min（An,Bn），Cn+1=Cn
实验源程序（可续页）
1..importjava.util.Scanner;
publicclassFibonacci{
/**
*@paramargs
*/
publicstaticvoidmain（String[]args）{
System.out.println（"请输入项数：
"）;
Scannerin=newScanner（System.in）;
intn=in.nextInt（）;
//System.out.println（fibonacci（n））;
longstart=System.currentTimeMillis（）;
System.out.println（Fibonacci（n））;
longfinish=System.currentTimeMillis（）;
System.out.println（finish-start）;
}
/*publicstaticintfibonacci（intn）
{
if（n<=1）return1;
returnfibonacci（n-1）+fibonacci（n-2）;
}*/
/*publicstaticintfibonacci（intn）
{
return（int）（1/Math.sqrt（5）*（Math.pow（（1+Math.sqrt（5））/2,n+1）-Math.pow（（1-Math.sqrt（5））/2,n+1）））;
}
*/
publicstaticintFibonacci（intn）
{
inta=1;intb=1;
for（inti=2;i{
intc=a+b;a=b;b=c;
}returnb;
}
}
2.importjava.util.Scanner;
publicclassBinarySearch{
/**
*@paramargs
*/
publicstaticvoidmain（String[]args）{
int[]a={1,3,5,7,9,11,13,15};
System.out.println（"请输入查找的数：
"）;
Scannerin=newScanner（System.in）;
intb=in.nextInt（）;
intresult=binarysearch（a,b,0,a.length-1）;
}
publicstaticintbinarysearch（int[]a,intb,intleft,intright）
{
if（left>=right）
return-1;
intmiddle=（left+right）/2;
if（b==a[middle]）returnmiddle;
elseif（b>a[middle]）returnbinarysearch（a,b,middle+1,right）;
elsereturnbinarysearch（a,b,left,middle-1）;
}
}
3.1）.importjava.util.Scanner;
publicclasspTest_1{
publicstaticinttime=0;
publicstaticvoidmain（String[]args）{
//TODOAuto-generatedmethodstub
Scanners=newScanner（System.in）;
System.out.println（"请输入第一个数：
"）;
intx=s.nextInt（）;
System.out.println（"请输入第二个数：
"）;
inty=s.nextInt（）;
System.out.println（"最大公约数：
"+f（x,y））;
System.out.println（"执行次数：
"+time）;
}
publicstaticintf（inta,intb）{
intt=0;
while（a%2==0&&b%2==0）{
a=a/2;
b=b/2;
t++;
time++;
}
while（a%2==0）{
a=a/2;
time++;
}
while（b%2==0）{
b=b/2;
time++;
}
while（a!
=0&&b!
=0）{
inttemp=Math.abs（a-b）;
b=Math.min（a,b）;
a=temp;
time++;
}
if（a==0）
returnb<returna<}
}
2）.
publicclasspTest_2{
publicstaticinttime=0;
publicstaticvoidmain（String[]args）{
//TODOAuto-generatedmethodstub
Scanners=newScanner（System.in）;
System.out.println（"请输入第一个数：
"）;
intx=s.nextInt（）;
System.out.println（"请输入第二个数：
"）;
inty=s.nextInt（）;
System.out.println（"最大公约数：
"+f（x,y））;
System.out.println（"执行次数：
"+time）;
}
publicstaticintf（inta,intb）{
inttemp;
while（a%b!
=0）{
temp=a%b;
a=b;
b=temp;
time++;
}
returnb;
}
}
3）.importjava.util.Scanner;
publicclasspTest_3{
publicstaticinttime=0;
publicstaticvoidmain（String[]args）{
//TODOAuto-generatedmethodstub
Scanners=newScanner（System.in）;
System.out.println（"请输入第一个数：
"）;
intx=s.nextInt（）;
System.out.println（"请输入第二个数：
"）;
inty=s.nextInt（）;
System.out.println（"最大公约数：
"+f（x,y））;
System.out.println（"执行次数：
"+time）;
}
publicstaticintf（inta,intb）{
inttemp;
if（areturnf（b,a）;
while（a!
=b）{
temp=a-b;
if（tempa=b;
b=temp;
}
else
a=temp;
time++;
}
returnb;
}
}
4）.importjava.util.Scanner;
publicclasspTest_4{
/**
*@paramargs
*/
publicstaticvoidmain（String[]args）{
//TODOAuto-generatedmethodstub
Scanners=newScanner（System.in）;
System.out.println（"请输入第一个数：
"）;
intx=s.nextInt（）;
System.out.println（"请输入第二个数：
"）;
inty=s.nextInt（）;
System.out.println（"最大公约数：
"+f（x,y））;
}
publicstaticintf（inta,intb）{
if（areturnf（b,a）;
if（b==0）
returna;
if（a%2==0&&b%2==0）
return2*f（a/2,b/2）;
if（a%2==0）
returnf（a/2,b）;
if（b%2==0）
returnf（a,b/2）;
returnf（b,a-b）;
}
}
实验结果及分析
教师评分
实验2排序问题
实验目的
1．了解分治法的基本思想，掌握分治策略的效率分析方法；
2.掌握合并排序问题和快速排序问题的分治算法的设计思路；
3.会用JAVA语言实现算法。
预习内容
1．分治策略的基本思想是什么？
算法的复杂度分析的递推关系是？
分治的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。
找出各部分的解，然后把各部分的解组合成整个问题的解。
算法分析中计算复杂性常用递归关系来表达，递归方程的求解有助于分析算法设计的好坏。
常用的递归方程的求解方法包括生成函数法、特征方程法，递推法等。
递归树方法和主方法给出了递归方程计算复杂度的渐进表示。
2．分治策略算法设计的基本过程？
分治法的基本步骤
分治法在每一层递归上都有三个步骤：
分解：
将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
解决：
若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
合并：
将各个子问题的解合并为原问题的解。
实验内容
1.合并排序问题
（1）试给出n个整型元素的合并排序递归算法和非递归算法，并程序实现；
（2）改写1中的算法，使其对各种类型数据具有通用性；
（3）分析算法的效率。
2.快速排序问题
（1）给出快速排序的递归算法，并程序实现；
（2）你能将
（1）中的递归算法改为非递归形式吗？
给出设计思路。
实验提示：
第一题
（2）考虑利用comparable接口；
（3）利用递推关系讨论
第二题
（2）核心思想：
将每次分治的两个序列的高位和低位入栈每次都从栈中获取一对高位和低位，分别处理。
处理过程是：
选取高位作为基准位置，从低位开始向高位遍历，如果比基准元素小，那么和第i个交换，如果有交换，那么i++，等一遍遍历完成后，如果i的位置不等于基准位置，那么所选的基准位置的值不是最大的而这时候i的位置之前的元素都比基准值小，那么i的位置应该是基准值，将i所在位置的值和基准位置进行交换。
这时候，在i的左右就将序列分成两部分了，一部分比i所在位置值小，一部分比i所在位置值大的，然后再次将前面一部分和后面一部分的高位和低位分别入栈，再次选择基准位置，直到所选择的区间大小小于2，就可以不用入栈了。
实验源程序（可续页）
1.
（1）递归
.publicclassmergesort{
publicstaticvoidmain（String[]args）{
//TODOAuto-generatedmethodstub
Comparable[]a={12,8,15,6,56,13,25,32,16};
mergesort（a,0,a.length-1）;
for（inti=0;i<=a.length-1;i++）
{
System.out.println（"排好后的的数组为：
"）;
System.out.println（a[i]）;
}
}
publicstaticvoidmergesort（Comparable[]a,intleft,intright）
{
if（left{
inti=（left+right）/2;
mergesort（a,left,i）;
mergesort（a,i+1,right）;
Comparable[]b=newComparable[a.length];
merge（a,b,left,i,right）;
copy（a,b,left,right）;
}
}
publicstaticvoidcopy（Comparable[]a,Comparable[]b,intleft,intright）
{
for（inti=left;i<=right;i++）
a[i]=b[i];
}
privatestaticvoidmerge（Comparable[]a,Comparable[]b,intleft,intmid,intright）{
//TODOAuto-generatedmethodstub
inti=left;
intj=mid+1;
intk=1;
while（（i<=mid）&&（j<=right））
{
if（a[i].compareTo（a[j]）<=0）
b[k++]=a[j];
else
b[k++]=a[i];
if（i>mid）
for（intq=j;q<=right;q++）
b[k++]=a[q];
else
for（intq=i;q<=mid;q++）
b[k++]=a[q];
}
}
}
非递归
publicstaticvoidmergeSort（Comparable
Comparable
ints=1;
while（smergePass（a,b,s）;
s+=s;
mergePass（b,a,s）;
s+=s;
}
}
publicstaticvoidmergePass（Comparable
inti=0;
while（i<=x.length-2*s）{
merge（x,y,i,i+s-1,i+2*s-1）;
i=i+2*s;
}
if（i+smerge（x,y,i,i+s-1,x.length-1）;
else
for（intj=i;jy[j]=x[j];
}
}
publicstaticvoidmerge（Comparable
inti=1;
intj=M+1;
intk=1;
while（i<=M&&j<=R）{
if（c[i].compareTo（c[j]）<=0）{
d[k++]=c[i++];
}
else
d[k++]=c[j++];
}
if（i>M）{
for（intq=j;q<=R;q++）{
d[k++]=c[q];
}
}
else{
for（intq=i;q<=M;q++）{
d[k++]=c[q];
}
}
（2）
（3）.分解：
计算中间位置O
（1）
解决：
求解两个规模为n/2的子问题，2T（n/2）
合并：
n个元素O（n）
T（n）=2T（n/2）+O（n）-->T（n）=O（n*Log（n））
2.
（1）packagealgorithm;
classArrayIns{
privatelong[]theArray;
privateintnElems;
publicArrayIns（intmax）{
theArray=newlong[max];
nElems=0;
}
publicvoidinsert（longvalue）{
theArray[nElems]=value;
nElems++;
}
publicvoiddisplay（）{
System.out.print（"A="）;
for（intj=0;jSystem.out.print（theArray[j]+""）;
System.out.println（""）;
}
publicvoidquickSort（）{
recQuickSort（0,nElems-1）;
}
publicvoidrecQuickSort（intleft,intright）{
if（right-left<=0）
return;
else{
longpivot=theArray[right];
intpartition=partitionIt（left,right,pivot）;
recQuickSort（left,partition-1）;
recQuickSort（partition+1,right）;
}
}
publicintpartitionIt（intleft,intright,longpivot）{
intleftPtr=left-1;
intrightPtr=right;
while（true）{
while（theArray[++leftPtr];
while（rightPtr>0&&theArray[--rightPtr]>pivot）
;
if（leftPtr>=rightPtr）
break;
else
swap（leftPtr,rightPtr）;
}
swap（leftPtr,right）;
returnleftPtr;
}
publicvoidswap（intdex1,intdex2）{
longtemp=theArray[dex1];
theArray[dex1]=theArray[dex2];
theArray[dex2]=temp;
}
}
ClassQuickSort1{
升级会员 